Petr Golovach is a research professor at the Department of Informatics, University of Bergen. His main research interests are in the areas of  Discrete Mathematics and Theoretical Computer Sciences. His research spans a broad range of topics in graph theory, algorithms on graphs and matroids, clustering algorithms, complexity, parameterized complexity, enumeration algorithms.

Petr Golovach was one of the organizers of Dagstuhl Seminar 18381 “Algorithmic enumeration: output-sensitive, input-sensitive, parameterized, approximative” in 2018. He have been a program commitee member of various international workshops and conferences (STACS 2020, IPEC 2019, WG 2019 and 2016, WEPA 2018, SWAT 2014), and he is selected to be a program commitee chair of IPEC 2021.

Teaching courses 

At Syktyvkar State University (Russia) - 1991-2007:

• Programming,
• Discrete mathematics, 
• Combinatorial algorithms,
• Graph theory,
• Matroid theory,
• Computational complexity.

At Durham University (UK) - 2009-2011:

• Advanced theory of computation,
• Formal aspects of computer science.

At University of Bergen:

 Advanced theory of computation,

• Advanced algorithms techniques (INF 334) - 2015,
• Selected topics in Algorithms and Complexity, Enumeration algorithms (INF 339) - 2018.

Supervision (at Uiniversity of Bergen)

PhD students:

Nidhi Purohit, Matrix Clustering with Size Constraints.  

Master students:

Øyving Stette Haarberg, Complexity of Edge-Editing to a Connected Graph of Bounded Degree - 2019

Andreas Steinvik, Kernelization for Balanced Graph Clustering - 2020

2025

• Clément Dallard; Fedor Fomin; Petr Golovach et al. (2025). Computing Tree Decompositions with Small Independence Number. (external link)
• Matthias Bentert; Fedor Fomin; Petr Golovach et al. (2025). Packing Short Cycles. (external link)
• Fedor Fomin; Petr Golovach; Tanmay Nitin Inamdar et al. (2025). Parameterized Geometric Graph Modification with Disk Scaling. (external link)
• Matthias Bentert; Fedor Fomin; Petr Golovach et al. (2025). Fault-Tolerant Matroid Bases. (external link)
• Matthias Bentert; Fedor Fomin; Petr Golovach et al. (2025). When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations. (external link)
• Fedor Fomin; Petr Golovach; Danil Sagunov et al. (2025). Edge Clique Partition and Cover Beyond Independence. (external link)
• Fedor Fomin; Petr Golovach; Tanmay Inamdar et al. (2025). Hybrid k-Clustering: Blending k-Median and k-Center. (external link)
• Matthias Bentert; Fedor Fomin; Petr Golovach (2025). Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths. (external link)
• Petr Golovach; Stavros G. Kolliopoulos; Giannos Stamoulis et al. (2025). Finding irrelevant vertices in linear time on bounded-genus graphs. (external link)
• Aritra Banik; Fedor Fomin; Petr Golovach et al. (2025). Multivariate Exploration of Metric Dilation. (external link)
• Matthias Bentert; Petr Golovach; Tanmay Inamdar et al. (2025). Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems. (external link)
• Fedor Fomin; Petr Golovach; Danil Sagunov et al. (2025). Tree Containment above Minimum Degree Is FPT. (external link)
• Fedor Fomin; Petr Golovach; Tuukka Korhonen et al. (2025). Fixed-Parameter Tractability of Hedge Cut. (external link)
• Benjamin Bergougnoux; Nello Blaser; Michael Ralph Fellows et al. (2025). On the parameterized complexity of lineal topologies (depth-first spanning trees) with many or few leaves. (external link)

2023

• Emmanuel Sam; Michael Ralph Fellows; Frances Rosamond et al. (2023). On the Parameterized Complexity of the Structure of Lineal Topologies (Depth-First Spanning Trees) of Finite Graphs: The Number of Leaves. (external link)
• Fedor Fomin; Petr Golovach; Tanmay Nitin Inamdar et al. (2023). Kernelization for Spreading Points. (external link)
• Fedor Fomin; Petr Golovach; Danil Sagunov et al. (2023). Turán's Theorem Through Algorithmic Lens. (external link)
• Matthias Bentert; Pål Grønås Drange; Fedor Fomin et al. (2023). Two-sets cut-uncut on planar graphs. (external link)
• Christophe Crespelle; Pål Grønås Drange; Fedor Fomin et al. (2023). A survey of parameterized algorithms and the complexity of edge modification. (external link)
• Fedor Fomin; Pierre Fraigniaud; Petr Golovach (2023). Parameterized Complexity of Broadcasting in Graphs. (external link)
• Petr Golovach; Giannos Stamoulis; Dimitrios M. Thilikos (2023). Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable. (external link)
• Fedor Fomin; Petr Golovach; Tuukka Matias Aleksanteri Korhonen et al. (2023). Computing Paths of Large Rank in Planar Frameworks Deterministically. (external link)
• Fedor Fomin; Petr Golovach; Dimitrios M. Thilikos (2023). Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs. (external link)
• Fedor Fomin; Petr Golovach; William Alexandre Lochet et al. (2023). Detours in directed graphs. (external link)
• Sayan Bandyapadhyay; Fedor Fomin; Petr Golovach et al. (2023). Lossy Kernelization of Same-Size Clustering. (external link)
• Fedor Fomin; Petr Golovach; Tanmay Nitin Inamdar et al. (2023). FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges. (external link)
• Fedor Fomin; Petr Golovach; Danil Sagunov et al. (2023). Approximating Long Cycle Above Dirac's Guarantee. (external link)
• Sayan Bandyapadhyay; Fedor Fomin; Petr Golovach et al. (2023). How to find a good explanation for clustering?. (external link)
• Emmanuel Sam; Benjamin Bergougnoux; Petr Golovach et al. (2023). Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves. (external link)
• Fedor Fomin; Petr Golovach; Tuukka Korhonen et al. (2023). Fixed-Parameter Tractability of Maximum Colored Path and Beyond. (external link)
• Petr Golovach; Giannos Stamoulis; Dimitrios M. Thilikos (2023). Combing a Linkage in an Annulus. (external link)
• Sayan Bandyapadhyay; Fedor Fomin; Petr Golovach et al. (2023). Parameterized Complexity of Feature Selection for Categorical Data Clustering. (external link)
• Emmanuel Jean Paul Pierre Arrighi; Fedor Fomin; Petr Golovach et al. (2023). Kernelizing Temporal Exploration Problems. (external link)
• Fedor Fomin; Petr Golovach; Ignasi Sau et al. (2023). Compound Logics for Modification Problems. (external link)
• Fedor Fomin; Petr Golovach; Fahad Panolan et al. (2023). Diverse collections in matroids and graphs. (external link)
• Fedor Fomin; Petr Golovach; Nidhi Purohit (2023). Parameterized complexity of categorical clustering with size constraints. (external link)
• Fedor Fomin; Petr Golovach; Tuukka Matias Aleksanteri Korhonen et al. (2023). Shortest Cycles With Monotone Submodular Costs. (external link)
• Fedor Fomin; Petr Golovach; Giannos Stamoulis et al. (2023). An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL. (external link)
• Petr Golovach; Giannos Stamoulis; Dimitrios M. Thilikos (2023). Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes. (external link)

2021

• Eduard Eiben; Fedor Fomin; Petr Golovach et al. (2021). EPTAS for k-means Clustering of Affine Subspaces. (external link)
• Sayan Bandyapadhyay; Fedor Fomin; Petr Golovach et al. (2021). Parameterized Complexity of Feature Selection for Categorical Data Clustering. (external link)
• Fedor Fomin; Petr Golovach; Kirill Simonov (2021). Parameterized k-Clustering: Tractability island. (external link)
• Fedor Fomin; Petr Golovach (2021). Kernelization of Whitney Switches. (external link)
• Fedor Fomin; Petr Golovach (2021). Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs. (external link)
• Fedor Fomin; Pierre Fraigniaud; Petr Golovach (2021). Present-Biased Optimization. (external link)
• Christoph Brause; Petr Golovach; Barnaby Martin et al. (2021). Partitioning H-Free Graphs of Bounded Diameter. (external link)
• Fedor Fomin; Petr Golovach; William Alexandre Lochet et al. (2021). Parameterized Complexity of Directed Spanner Problems. (external link)
• Petr Golovach; Christian Komusiewicz; Dieter Kratsch et al. (2021). Refined notions of parameterized enumeration kernels with applications to matching cut enumeration. (external link)
• Fedor Fomin; Petr Golovach; Nidhi Purohit (2021). Parameterized Complexity of Categorical Clustering with Size Constraints. (external link)
• Fedor Fomin; Petr Golovach; Tanmay Nitin Inamdar et al. (2021). ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space. (external link)
• Fedor Fomin; Petr Golovach; Fahad Panolan et al. (2021). Diverse Collections in Matroids and Graphs. (external link)
• Fedor Fomin; Petr Golovach; Dimitrios M. Thilikos (2021). Parameterized Complexity of Elimination Distance to First-Order Logic Properties. (external link)
• Fedor Fomin; Petr Golovach; Dimitrios M. Thilikos (2021). Can Romeo and Juliet Meet? or Rendezvous Games with Adversaries on Graphs. (external link)
• Steven Chaplick; Fedor Fomin; Petr Golovach et al. (2021). Kernelization of Graph Hamiltonicity: Proper H-Graphs. (external link)
• Christoph Brause; Petr Golovach; Barnaby Martin et al. (2021). Acyclic, Star, and Injective Colouring: Bounding the Diameter. (external link)

2016

• Petr Golovach; Pinar Heggernes; Mamadou M. Kanté et al. (2016). Enumerating minimal dominating sets in chordal bipartite graphs. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch (2016). Enumeration and maximum number of minimal connected vertex covers in graphs. (external link)
• Petr Golovach; Daniël Paulusma; Erik Jan van Leeuwen (2016). Induced disjoint paths in circular-arc graphs in linear time. (external link)
• Manfred Cochefert; Jean-François Couturier; Petr Golovach et al. (2016). Parameterized algorithms for finding square roots. (external link)
• Tatjana V. Abramovskaya; Fedor Fomin; Petr Golovach et al. (2016). How to hunt an invisible rabbit on a graph. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch (2016). Enumerating minimal connected dominating sets in graphs of bounded chordality. (external link)
• Petr Golovach; Dieter Kratsch; Daniël Paulusma et al. (2016). A linear kernel for finding square roots of almost planar graphs. (external link)
• Konrad K. Dabrowski; Petr Golovach; Pim van 't Hof et al. (2016). Editing to Eulerian graphs. (external link)
• Rajesh Chitnis; Fedor Fomin; Petr Golovach (2016). Parameterized complexity of the anchored k-core problem for directed graphs. (external link)
• Ivan Bliznets; Fedor Fomin; Petr Golovach et al. (2016). Parameterized Complexity of Superstring Problems. (external link)
• Fedor Fomin; Petr Golovach; Nikolay Karpov et al. (2016). Parameterized complexity of secluded connectivity problems. (external link)
• Fedor Fomin; Petr Golovach; Fahad Panolan et al. (2016). Editing to connected f-degree graph. (external link)
• Petr Golovach; Dieter Kratsch; Daniël Paulusma et al. (2016). Squares of low clique number. (external link)
• Petr Golovach; Dieter Kratsch; Daniël Paulusma et al. (2016). Finding cactus roots in polynomial time. (external link)
• Petr Golovach; George B. Mertzios (2016). Graph editing to a given degree sequence. (external link)

2018

• Petr Golovach; Pinar Heggernes; Paloma Thomé de Lima et al. (2018). Finding connected secluded subgraphs. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch (2018). Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs. (external link)
• Fedor Fomin; Petr Golovach; Torstein J. Strømme et al. (2018). Partial Complementation of Graphs. (external link)
• Fedor Fomin; Petr Golovach; Fahad Panolan (2018). Parameterized low-rank binary matrix approximation. (external link)
• Fedor Fomin; Petr Golovach; Daniel Lokshtanov et al. (2018). Covering Vectors by Spaces: Regular Matroids. (external link)
• Petr Golovach; Pinar Heggernes; Mamadou Moustapha Kanté et al. (2018). Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. (external link)
• Petr Golovach; Daniel Lokshtanov; Saket Saurabh et al. (2018). Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth. (external link)
• Fedor Fomin; Petr Golovach; Dimitrios M. Thilikos (2018). Structured connectivity augmentation. (external link)
• Fedor Fomin; Petr Golovach; Daniel Lokshtanov et al. (2018). Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring. (external link)
• Petr Golovach; Pinar Heggernes; Athanasios Konstantinidis et al. (2018). Parameterized Aspects of Strong Subgraph Closure. (external link)
• Fedor Fomin; Petr Golovach; Jean-Florent Raymond (2018). On the tractability of optimization problems on H-graphs. (external link)
• Manfred Cochefert; Jean-François Couturier; Petr Golovach et al. (2018). Computing square roots of graphs with low maximum degree. (external link)

2022

• Fedor Fomin; Petr Golovach; Tanmay Nitin Inamdar et al. (2022). Exact Exponential Algorithms for Clustering Problems. (external link)
• Fedor Fomin; Pierre Fraigniaud; Petr Golovach (2022). Present-biased optimization. (external link)
• Petr Golovach; Paloma T. Lima; Charis Papadopoulos (2022). Graph Square Roots of Small Distance from Degree One Graphs. (external link)
• Fedor Fomin; Petr Golovach; Danil Sagunov et al. (2022). Algorithmic Extensions of Dirac's Theorem. (external link)
• Petr Golovach; Daniël Paulusma; Erik Jan van Leeuwen (2022). Induced Disjoint Paths in AT-free graphs. (external link)
• Fedor Fomin; Petr Golovach; Dimitrios M. Thilikos (2022). Parameterized Complexity of Elimination Distance to First-Order Logic Properties. (external link)
• Petr Golovach; Meirav Zehavi (2022). Special Issue Dedicated to the 16th International Symposium on Parameterized and Exact Computation. (external link)
• Christoph Brause; Petr Golovach; Barnaby Martin et al. (2022). Acyclic, star, and injective colouring: bounding the diameter^∗. (external link)
• Fedor Fomin; Petr Golovach; William Alexandre Lochet et al. (2022). Detours in Directed Graphs. (external link)
• Sayan Bandyapadhyay; Fedor Fomin; Petr Golovach et al. (2022). How to Find a Good Explanation for Clustering?. (external link)
• Christoph Brause; Petr Golovach; Barnaby Martin et al. (2022). Partitioning H-free graphs of bounded diameter. (external link)
• Sayan Bandyapadhyay; Fedor Fomin; Petr Golovach et al. (2022). Lossy Kernelization of Same-Size Clustering. (external link)
• Sayan Bandyapadhyay; Fedor Fomin; Petr Golovach et al. (2022). Lossy Kernelization of Same-Size Clustering. (external link)
• Fedor Fomin; Petr Golovach; Danil Sagunov et al. (2022). Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms. (external link)
• Christophe Dominique Crespelle; Petr Golovach (2022). Cyclability in graph classes. (external link)
• Fedor Fomin; Petr Golovach; Danil Sagunov et al. (2022). Longest Cycle Above Erdös-Gallai Bound. (external link)
• Fedor Fomin; Petr Golovach; Tanmay Nitin Inamdar et al. (2022). (Re)packing Equal Disks into Rectangle. (external link)
• Sayan Bandyapadhyay; Fedor Fomin; Petr Golovach et al. (2022). FPT Approximation for Fair Minimum-Load Clustering. (external link)

2009

• Petr Golovach; M. Kaminski; Daniel Paulusma et al. (2009). Induced Packing of Odd Cycles in a Planar Graph. (external link)
• Fedor Fomin; Petr Golovach; Dimitrios Thilikos (2009). Contraction Bidimensionality: The Accurate Picture. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch et al. (2009). Bandwidth on AT-Free Graphs. (external link)
• Hajo Broersma; Fedor Fomin; Petr Golovach et al. (2009). Three Complexity Results on Coloring Pk-Free Graphs. (external link)
• Fedor Fomin; Petr Golovach; Dimitrios Thilikos (2009). Approximating Acyclicity Parameters of Sparse Hypergraphs. (external link)
• Fedor Fomin; Petr Golovach; Jan Kratochvil et al. (2009). Sort and Search: Exact algorithms for generalized domination. (external link)
• Petr Golovach; Jan Kratochvil; Ondra Suchy (2009). Parameterized Complexity of Generalized Domination Problems. (external link)
• Jiří Fiala; Petr Golovach; Jan Kratochvil (2009). Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover. (external link)
• Petr Golovach; Pinar Heggernes (2009). Choosability of P5-free graphs. (external link)
• Petr Golovach; Dimitrios M. Thilikos (2009). Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms. (external link)
• Anthony Bonato; Petr Golovach; Gena Hahn et al. (2009). The capture time of a graph. (external link)

2012

• Fedor Fomin; Petr Golovach; Daniel Lokshtanov (2012). Cops and robber game without recharging. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch et al. (2012). An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs. (external link)
• Fedor Fomin; Petr Golovach; Jesper Nederlof et al. (2012). Minimizing Rosenthal potential in multicast games. (external link)
• Fedor Fomin; Petr Golovach; Pawel Pralat (2012). Cops and robber with constraints. (external link)
• Petr Golovach; Daniel Paulusma; Bernard Ries (2012). Coloring Graphs Characterized by a Forbidden Subgraph. (external link)
• Petr Golovach; Pinar Heggernes; Pim van 't Hof et al. (2012). How to Eliminate a Graph. (external link)
• Petr Golovach; Daniel Paulusma; Song Jian (2012). Closing Complexity Gaps for Coloring Problems on H-Free Graphs. (external link)
• Petr Golovach; Dieter Kratsch; Daniel Paulusma (2012). Detecting Induced Minors in AT-Free Graphs. (external link)
• Fedor Fomin; Serge Gaspers; Petr Golovach et al. (2012). k-Gap Interval Graphs. (external link)
• Petr Golovach; Pinar Heggernes; Rodica Mihai (2012). Edge search number of cographs. (external link)
• Petr Golovach; Pim van 't Hof; Daniel Paulusma (2012). Obtaining planarity by contracting few edges. (external link)
• Hans L. Bodlaender; Fedor Fomin; Petr Golovach et al. (2012). Parameterized complexity of the spanning tree congestion problem. (external link)

2019

• Petr Golovach; Pinar Heggernes; Dieter Kratsch et al. (2019). Enumeration of Minimal Connected Dominating Sets for Chordal Graphs. (external link)
• Steven Chaplick; Fedor Fomin; Petr Golovach et al. (2019). Kernelization of graph hamiltonicity: Proper H-graphs. (external link)
• Fedor Fomin; Petr Golovach; Dimitrios M Thilikos (2019). Modification to planarity is fixed parameter tractable. (external link)
• Petr Golovach; Dieter Kratsch; Mathieu Liedloff et al. (2019). Enumeration and maximum number of maximal irredundant sets for chordal graphs. (external link)
• Fedor Fomin; Petr Golovach; Daniel Lokshtanov et al. (2019). Spanning circuits in regular matroids. (external link)
• Fedor Fomin; Petr Golovach; Kirill Simonov (2019). Parameterized k-Clustering: Tractability Island. (external link)
• Fedor Fomin; Petr Golovach; Daniel Lokshtanov et al. (2019). Going Far From Degeneracy. (external link)
• Petr Golovach; Dimitrios M. Thilikos (2019). Clustering to Given Connectivities. (external link)
• Fedor Fomin; Petr Golovach; Fahad Panolan et al. (2019). Refined Complexity of PCA with Outliers. (external link)
• Fedor Fomin; Petr Golovach; Dimitrios M. Thilikos (2019). On the parameterized complexity of graph modification to first-order logic properties. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch et al. (2019). Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2. (external link)
• Christophe Dominique Crespelle; Carl Feghali; Petr Golovach (2019). Cyclability in Graph Classes. (external link)
• Fedor Fomin; Petr Golovach; Daniel Lokshtanov et al. (2019). Approximation Schemes for Low-rank Binary Matrix Approximation Problems. (external link)
• Fedor Fomin; Petr Golovach; Fahad Panolan et al. (2019). Editing to connected F-degree graph. (external link)
• Petr Golovach; Matthew Johnson; Barnaby Martin et al. (2019). Surjective H-colouring: New hardness results. (external link)
• Fedor Fomin; Petr Golovach; Daniel Lokshtanov et al. (2019). Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals. (external link)
• Petr Golovach; Dieter Kratsch; Mathieu Liedloff et al. (2019). Enumeration and maximum number of minimal dominating sets for chordal graphs. (external link)

2020

• Fedor Fomin; Petr Golovach; Jean-Florent Raymond (2020). On the Tractability of Optimization Problems on H-Graphs. (external link)
• Fedor Fomin; Petr Golovach; Lars Jaffke et al. (2020). Diverse Pairs of Matchings. (external link)
• Petr Golovach; Paloma T. Lima; Charis Papadopoulos (2020). Graph Square Roots of Small Distance from Degree One Graphs. (external link)
• Petr Golovach; Pinar Heggernes; Paloma T. Lima et al. (2020). Finding connected secluded subgraphs. (external link)
• Fedor Fomin; Petr Golovach; Fahad Panolan (2020). Parameterized low-rank binary matrix approximation. (external link)
• Fedor Fomin; Petr Golovach; Pranabendu Misra et al. (2020). On the Complexity of Recovering Incidence Matrices. (external link)
• Fedor Fomin; Petr Golovach; Fahad Panolan et al. (2020). Low-Rank Binary Matrix Approximation in Column-Sum Norm. (external link)
• Fedor Fomin; Petr Golovach; Daniel Lokshtanov et al. (2020). Going Far from Degeneracy. (external link)
• Fedor Fomin; Petr Golovach; Giannos Stamoulis et al. (2020). An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL. (external link)
• Fedor Fomin; Petr Golovach; William Lochet et al. (2020). Parameterized Complexity of Directed Spanner Problems. (external link)
• Fedor Fomin; Petr Golovach; Daniel Lokshtanov et al. (2020). Parameterization Above a Multiplicative Guarantee. (external link)
• Fedor Fomin; Petr Golovach; Torstein J. F. Strømme et al. (2020). Subgraph Complementation. (external link)
• Petr Golovach; R. Krithika; Abhishek Sahu et al. (2020). Graph Hamiltonicity Parameterized by Proper Interval Deletion Set. (external link)
• Petr Golovach; Giannos Stamoulis; Dimitrios Thilikos (2020). Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable. (external link)
• Fedor Fomin; Petr Golovach (2020). Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs. (external link)
• Fedor Fomin; Petr Golovach (2020). Kernelization of Whitney Switches. (external link)
• Petr Golovach; Pinar Heggernes; Athanasios L. Konstantinidis et al. (2020). Parameterized Aspects of Strong Subgraph Closure. (external link)
• Steven Chaplick; Petr Golovach; Tim Hartmann et al. (2020). Recognizing Proper Tree-Graphs. (external link)
• Fedor Fomin; Petr Golovach; Kirill Simonov (2020). Parameterized complexity of PCA. (external link)

2014

• Petr Golovach; Daniël Paulusma; Jian Song (2014). Coloring graphs without short cycles and long induced paths. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch et al. (2014). An incremental polynomial time Algorithm to enumerate all minimal edge dominating sets. (external link)
• Konrad K. Dabrowski; Petr Golovach; Pim van 't Hof et al. (2014). Editing to Eulerian graphs. (external link)
• Fedor Fomin; Petr Golovach (2014). Long circuits and large euler subgraphs. (external link)
• Fedor Fomin; Petr Golovach; Daniel Lokshtanov et al. (2014). Almost optimal lower bounds for problems parameterized by clique-width. (external link)
• Petr Golovach; Pinar Heggernes; Nathan Lindzey et al. (2014). Recognizing Threshold Tolerance Graphs in O(n^2) Time. (external link)
• Rémy Belmonte; Petr Golovach; Pim van 't Hof et al. (2014). Parameterized complexity of three edge contraction problems with degree constraints. (external link)
• Vinicius dos Santos; Petr Golovach; Pinar Heggernes et al. (2014). On Recognition of Threshold Tolerance Graphs and their Complements. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch et al. (2014). Subset feedback vertex sets in chordal graphs. (external link)
• Petr Golovach; Daniël Paulusma; Marcin Kaminski et al. (2014). Lift-contractions. (external link)
• Rémy Belmonte; Petr Golovach; Pinar Heggernes et al. (2014). Detecting fixed patterns in chordal graphs in polynomial time. (external link)
• Manu Basavaraju; Fedor Fomin; Petr Golovach et al. (2014). Parameterized algorithms to preserve connectivity. (external link)
• Petr Golovach; Daniël Paulusma; Jian Song (2014). Closing complexity gaps for coloring problems on H-free graphs. (external link)
• Fedor Fomin; Petr Golovach (2014). Parameterized complexity of connected even/odd subgraph problems. (external link)
• Konrad K. Dabrowski; Petr Golovach; Daniël Paulusma (2014). Colouring of graphs with Ramsey-type forbidden subgraphs. (external link)
• Petr Golovach; Daniel Paulusma (2014). List coloring in the absence of two subgraphs. (external link)
• Petr Golovach (2014). Editing to a Graph of Given Degrees. (external link)
• Petr Golovach; Marcin Kaminski; Spyridon Maniatis et al. (2014). The parameterized complexity of graph cyclability. (external link)
• Manu Basavaraju; Fedor Fomin; Petr Golovach et al. (2014). Connecting vertices by independent trees. (external link)
• Peter Biro; Matthijs Bomhoff; Petr Golovach et al. (2014). Solutions for the stable roommates problem with payments. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch et al. (2014). Finding clubs in graph classes. (external link)
• Petr Golovach; Daniël Paulusma; Erik Jan van Leeuwen (2014). Induced disjoint paths in circular-arc graphs in linear time. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch et al. (2014). An exact algorithm for Subset Feedback Vertex Set on chordal graphs. (external link)

2008

• Fedor Fomin; Petr Golovach; Jan Kratochvil (2008). On tractability cops and robbers game. (external link)
• Jiri Fiala; Petr Golovach; Jan Kratochvil (2008). Computational complexity of the distance constrained labeling problem for trees. (external link)
• Feodor Dragan; Fedor Fomin; Petr Golovach (2008). Spanners in sparse graphs. (external link)
• Jiri Fiala; Petr Golovach; Jan Kratochvil (2008). Distance constrained labeling of trees. (external link)
• Feodor Dragan; Fedor Fomin; Petr Golovach (2008). A PTAS for the sparsest spanners problem on apex-minor-free graphs. (external link)
• Petr Golovach; Jan Kratochvil (2008). Generalized domination in degenerate graphs: a complete dichotomy of computational complexity. (external link)
• Fedor Fomin; Petr Golovach; Alex Hall et al. (2008). How to guard a graph?. (external link)
• Petr Golovach; Yngve Villanger (2008). Parameterized complexity for domination problems on degenerate graphs. (external link)
• Jiri Fiala; Petr Golovach (2008). Complexity of the packing coloring problem for trees. (external link)

2017

• Konrad K. Dabrowski; Petr Golovach; Pim van 't Hof et al. (2017). Editing to a planar graph of given degrees. (external link)
• Petr Golovach; Dieter Kratsch; Mohamed Yosri Sayadi (2017). Enumeration of maximal irredundant sets for claw-free graphs. (external link)
• Fedor Fomin; Petr Golovach; Dimitrios M. Thilikos (2017). Structured Connectivity Augmentation. (external link)
• Petr Golovach; Dieter Kratsch; Daniël Paulusma et al. (2017). Finding Cactus Roots in Polynomial Time. (external link)
• Petr Golovach; Dieter Kratsch; Daniel Paulusma et al. (2017). A linear kernel for finding square roots of almost planar graphs. (external link)
• Petr Golovach; Pinar Heggernes; Mamadou Moustapha Kanté et al. (2017). Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. (external link)
• Remy Belmonte; Fedor Fomin; Petr Golovach et al. (2017). Metric Dimension of Bounded Tree-length Graphs. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch et al. (2017). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. (external link)
• Petr Golovach; Pinar Heggernes; Nathan Lindzey et al. (2017). On recognition of threshold tolerance graphs and their complements. (external link)
• Petr Golovach; Dieter Kratsch; Mathieu Liedloff et al. (2017). Enumeration and maximum number of maximal irredundant sets for chordal graphs. (external link)
• Petr Golovach (2017). Editing to a connected graph of given degrees. (external link)
• Petr Golovach; Matthew Johnson; Barnaby Martin et al. (2017). Surjective H-colouring: New hardness results. (external link)
• Petr Golovach; Matthew Johnson; Daniël Paulusma et al. (2017). A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. (external link)
• Petr Golovach; George B. Mertzios (2017). Graph editing to a given degree sequence. (external link)
• Petr Golovach; Daniël Paulusma; Iain Stewart (2017). Graph editing to a fixed target. (external link)
• Petr Golovach; Pinar Heggernes; Mamadou Moustapha Kanté et al. (2017). Minimal dominating sets in interval graphs and trees. (external link)
• Fedor Fomin; Petr Golovach; Daniel Lokshtanov et al. (2017). Spanning Circuits in Regular Matroids. (external link)
• Petr Golovach; Marcin Kamiński,; Spyridon Maniatis et al. (2017). The parameterized complexity of graph cyclability. (external link)
• Fedor Fomin; Petr Golovach; Daniel Lokshtanov et al. (2017). Covering vectors by spaces: Regular matroids. (external link)

2013

• Petr Golovach; Pinar Heggernes; Pim van 't Hof et al. (2013). Choosability on H-free graphs. (external link)
• Manfred Cochefert; Jean-francois Couturier; Petr Golovach et al. (2013). Sparse Square Roots. (external link)
• Fedor Fomin; Petr Golovach; Janne Korhonen (2013). On the Parameterized Complexity of Cutting a Few Vertices from a Graph. (external link)
• Petr Golovach; Pinar Heggernes; Pim van 't Hof et al. (2013). Modifying a Graph Using Vertex Elimination. (external link)
• Rajesh Chitnis; Fedor Fomin; Petr Golovach (2013). Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs. (external link)
• Rémy Belmonte; Petr Golovach; Pim van 't Hof et al. (2013). Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch et al. (2013). An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets. (external link)
• Hajo Broersma; Fedor Fomin; Petr Golovach et al. (2013). Three complexity results on coloring Pk-free graphs. (external link)
• Hajo Broersma; Petr Golovach; Viresh Patel (2013). Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. (external link)
• Petr Golovach; Daniël Paulusma; Iain Stewart (2013). Graph Editing to a Fixed Target. (external link)
• Hajo Broersma; Jiri Fiala; Petr Golovach et al. (2013). Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. (external link)
• Rajesh Chitnis; Fedor Fomin; Petr Golovach (2013). Preventing unraveling in social networks gets harder. (external link)
• Petr Golovach; Pim van 't Hof; Daniël Paulusma (2013). Obtaining planarity by contracting few edges. (external link)
• Petr Golovach; Dieter Kratsch; Daniël Paulusma (2013). Detecting induced minors in AT-free graphs. (external link)
• Fedor Fomin; Petr Golovach (2013). Long Circuits and Large Euler Subgraphs. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch et al. (2013). Cliques and Clubs. (external link)
• K. Dabrowski; Petr Golovach; Daniël Paulusma (2013). Colouring of Graphs with Ramsey-Type Forbidden Subgraphs. (external link)
• Petr Golovach; Daniël Paulusma (2013). List Coloring in the Absence of Two Subgraphs. (external link)

2015

• Konrad K Dabrowski; Petr Golovach; Pim van'T Hof et al. (2015). Editing to a planar graph of given degrees. (external link)
• Jean-François Couturier; Petr Golovach; Dieter Kratsch et al. (2015). List coloring in the absence of a linear forest. (external link)
• Fedor Fomin; Petr Golovach; Jesper Nederlof et al. (2015). Minimizing Rosenthal potential in multicast games. (external link)
• Hajo Broersma; Jiří Fiala; Petr Golovach et al. (2015). Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs665. (external link)
• Ivan Bliznets; Fedor Fomin; Petr Golovach et al. (2015). Parameterized complexity of superstring problems. (external link)
• Remy Belmonte; Fedor Fomin; Petr Golovach et al. (2015). Metric dimension of bounded width graphs. (external link)
• Petr Golovach; Daniël Paulusma; Bernard Ries (2015). Coloring graphs characterized by a forbidden subgraph. (external link)
• Fedor Fomin; Petr Golovach; Nikolay Karpov et al. (2015). Parameterized complexity of secluded connectivity problems. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch et al. (2015). An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. (external link)
• Petr Golovach; Pinar Heggernes; Pim van' t Hof et al. (2015). Hadwiger number of graphs with small chordality. (external link)
• Petr Golovach; Pinar Heggernes; Pim van 't Hof et al. (2015). Hadwiger number of graphs with small chordality. (external link)
• Petr Golovach; Daniël Paulusma; Erik Jan van Leeuwen (2015). Induced disjoint paths in claw-free graphs. (external link)
• Petr Golovach (2015). Editing to a Graph of Given Degrees. (external link)
• Petr Golovach; Pinar Heggernes; Mamadou Kante et al. (2015). Output-polynomial enumeration on graphs of bounded (local) linear mim-width. (external link)
• Petr Golovach; Clement Requile; Dimitrios M. Thilikos (2015). Variants of plane diameter completion. (external link)
• Petr Golovach; Pinar Heggernes; Pim van 't Hof et al. (2015). Modifying a graph using vertex elimination. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch (2015). Enumerating minimal connected dominating sets in graphs of bounded chordality. (external link)
• Petr Golovach; Petr A Golovach; Pim van'T Hof et al. (2015). Editing to a Connected Graph of Given Degrees. (external link)

2011

• Fedor Fomin; Petr Golovach; Erik Jan van Leeuwen (2011). Spanners of bounded degree graphs. (external link)
• Fedor Fomin; Petr Golovach; Jan Kratochvil et al. (2011). Branch and Recharge: Exact Algorithms for Generalized Domination. (external link)
• Feodor F. Dragan; Fedor Fomin; Petr Golovach (2011). Spanners in sparse graphs. (external link)
• Fedor Fomin; Petr Golovach; Dimitrios M. Thilikos (2011). Approximating width parameters of hypergraphs with excluded minors. (external link)
• Fedor Fomin; Petr Golovach; Daniel Lokshtanov (2011). Guard games on graphs: Keep the intruder out!. (external link)
• Fedor Fomin; Petr Golovach; Alex Hall et al. (2011). How to Guard a Graph?. (external link)
• Feodor F. Dragan; Fedor Fomin; Petr Golovach (2011). Approximation of minimum weight spanners for sparse graphs. (external link)
• Petr Golovach; Pinar Heggernes; Dieter Kratsch et al. (2011). Bandwidth on AT-free graphs. (external link)
• Fedor Fomin; Petr Golovach; Dimitrios M. Thilikos (2011). Contraction obstructions for treewidth. (external link)

2010

• Fedor Fomin; Petr Golovach; Jan Kratochvil et al. (2010). Pursuing a fast robber on a graph. (external link)
• Jiří Fiala; Petr Golovach (2010). Complexity of the packing coloring problem for trees. (external link)
• Fedor Fomin; Petr Golovach; Daniel Lokshtanov et al. (2010). Intractability of clique-width parameterizations. (external link)

2024

• Fedor Fomin; Petr Golovach; Danil Sagunov et al. (2024). Approximating Long Cycle Above Dirac’s Guarantee. (external link)
• Tatiana Belova; Yuriy Dementiev; Fedor Fomin et al. (2024). How to Guide a Present-Biased Agent Through Prescribed Tasks?. (external link)
• Fedor Fomin; Petr Golovach; Tanmay Inamdar et al. (2024). Hybrid k-Clustering: Blending k-Median and k-Center. (external link)
• Fedor Fomin; Petr Golovach; Tanmay Inamdar et al. (2024). FPT approximation and subexponential algorithms for covering few or many edges. (external link)
• Fedor Fomin; Petr Golovach; Tuukka Korhonen et al. (2024). Fixed-Parameter Tractability of Maximum Colored Path and beyond. (external link)
• Fedor Fomin; Petr Golovach; Lars Jaffke et al. (2024). Diverse Pairs of Matchings. (external link)
• Fedor Fomin; Petr Golovach; Danil Sagunov et al. (2024). Tree Containment Above Minimum Degree is FPT. (external link)
• Fedor Fomin; Petr Golovach; Tuukka Korhonen et al. (2024). Shortest Cycles with Monotone Submodular Costs. (external link)
• Fedor Fomin; Petr Golovach; Tanmay Inamdar et al. (2024). (Re)packing Equal Disks into Rectangle. (external link)
• Fedor Fomin; Pierre Fraigniaud; Petr Golovach (2024). Parameterized complexity of broadcasting in graphs. (external link)
• Matthias Bentert; Pål Grønås Drange; Fedor Fomin et al. (2024). Two-Sets Cut-Uncut on Planar Graphs. (external link)
• Matthias Bentert; Michael Ralph Fellows; Petr Golovach et al. (2024). Breaking a Graph into Connected Components with Small Dominating Sets. (external link)
• Aritra Banik; Fedor Fomin; Petr Golovach et al. (2024). Cuts in Graphs with Matroid Constraints. (external link)
• Clement Dallard; Fedor Fomin; Petr Golovach et al. (2024). Computing Tree Decompositions with Small Independence Number. (external link)
• Fedor Fomin; Petr Golovach; Tuukka Korhonen et al. (2024). Stability in Graphs with Matroid Constraints. (external link)
• Fedor Fomin; Petr Golovach; Danil Sagunov et al. (2024). LONGEST CYCLE ABOVE ERDŐS–GALLAI BOUND. (external link)

2007

• Hajo Broersma; Fedor Fomin; Petr Golovach et al. (2007). Backbone colorings for graphs: Tree and path backbones. (external link)
• Petr Golovach; Fedor Fomin; Jan Kratochvil et al. (2007). Branch and Recharge: Exact Algorithms for Generalized Domination. (external link)
• Petr Golovach; Jan Kratochvil (2007). Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs. (external link)

2026

• Matthias Bentert; Fedor Fomin; Petr Golovach et al. (2026). When Does FTP Become FPT?. (external link)

See a complete overview of publications in Cristin.

Petr Golovach has  more that 100 papers in peer reviewed journals (including high rated academic journals like J. Comb. Theory, Ser. B,  SIAM J. Computing, SIAM J. Discrete Math., J. of Graph Theory, Algorithmica, J. Comput. Syst. Sci.) and more than 100 papers in refereed conference proceedings (including leading Theoretical Computer Science conferences like SODA, ICALP, ESA, STACS).