• An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL 

      Fomin, Fedor; Golovach, Petr; Stamoulis, Giannos; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2020)
      In general, a graph modification problem is defined by a graph modification operation ⊠ and a target graph property 𝒫. Typically, the modification operation ⊠ may be vertex removal, edge removal, edge contraction, or edge ...
    • Approximating Acyclicity Parameters of Sparse Hypergraphs 

      Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios (Conference object; Peer reviewed; Journal article, 2009)
      The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized ...
    • Clustering to Given Connectivities 

      Golovach, Petr; Thilikos, Dimitrios M. (Peer reviewed; Journal article, 2019)
      We define a general variant of the graph clustering problem where the criterion of density for the clusters is (high) connectivity. In Clustering to Given Connectivities, we are given an n-vertex graph G, an integer k, and ...
    • Connecting Vertices by Independent Trees 

      Basavaraju, Manu; Fomin, Fedor; Golovach, Petr; Saurabh, Saket (Conference object, 2014)
      We study the paramereteized complexity of the following connectivity problem. For a vertex subset U of a graph G, trees T1, . . . , Ts of G are completely independent spanning trees of U if each of them contains U , and ...
    • Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals 

      Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (Peer reviewed; Journal article, 2019)
      Perturbed graphic matroids are binary matroids that can be obtained from a graphic matroid by adding a noise of small rank. More precisely, an r-rank perturbed graphic matroid M is a binary matroid that can be represented ...
    • Cyclability in Graph Classes 

      Crespelle, Christophe Dominique; Feghali, Carl; Golovach, Petr (Peer reviewed; Journal article, 2019)
      A subset T subseteq V(G) of vertices of a graph G is said to be cyclable if G has a cycle C containing every vertex of T, and for a positive integer k, a graph G is k-cyclable if every subset of vertices of G of size at ...
    • Diverse Pairs of Matchings 

      Fomin, Fedor; Golovach, Petr; Jaffke, Lars; Philip, Geevarghese; Sagunov, Danil (Journal article; Peer reviewed, 2020)
      We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse ...
    • Editing to Eulerian Graphs 

      Dabrowski, Konrad K.; Golovach, Petr; van' t Hof, Pim; Paulusma, Daniël (Conference object, 2014)
      We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let ea, ed and vd denote the operations edge addition, edge deletion and ...
    • Enumerating minimal connected dominating sets in graphs of bounded chordality 

      Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter (Conference object; Peer reviewed; Journal article, 2015)
      Listing, generating or enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration ...
    • Going Far from Degeneracy 

      Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)
      An undirected graph $G$ is $d$-degenerate if every subgraph of $G$ has a vertex of degree at most $d$. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy $d>1$ contains a cycle of length at ...
    • Going Far From Degeneracy 

      Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Peer reviewed; Journal article, 2019-09-06)
      An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erd\H{o}s and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least ...
    • Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable 

      Golovach, Petr; Thilikos, Dimitrios; Stamoulis, Giannos (Journal article; Peer reviewed, 2020)
      For a finite collection of graphs F, the F-TM-Deletion problem has as input an n-vertex graph G and an integer k and asks whether there exists a set S ⊆ V(G) with |S| ≤ k such that G \ S does not contain any of the graphs ...
    • Kernelization of Whitney Switches 

      Fomin, Fedor; Golovach, Petr (Journal article; Peer reviewed, 2020)
      A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs G and H are 2-isomorphic, or equivalently, their cycle matroids are isomorphic, if and only if G can be transformed into H by a series of operations ...
    • Low-Rank Binary Matrix Approximation in Column-Sum Norm 

      Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Simonov, Kirill (Journal article; Peer reviewed, 2020)
      We consider 𝓁₁-Rank-r Approximation over {GF}(2), where for a binary m× n matrix 𝐀 and a positive integer constant r, one seeks a binary matrix 𝐁 of rank at most r, minimizing the column-sum norm ‖ 𝐀 -𝐁‖₁. We show ...
    • Modification to planarity is fixed parameter tractable 

      Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M (Peer reviewed; Journal article, 2019)
      A replacement action is a function L that maps each k-vertex labeled graph to another k-vertex graph. We consider a general family of graph modification problems, called L-Replacement to C, where the input is a graph G and ...
    • On the Complexity of Recovering Incidence Matrices 

      Fomin, Fedor; Golovach, Petr; Misra, Pranabendu; Ramanujan, M.S. (Journal article; Peer reviewed, 2020)
      The incidence matrix of a graph is a fundamental object naturally appearing in many applications, involving graphs such as social networks, communication networks, or transportation networks. Often, the data collected about ...
    • On the Tractability of Optimization Problems on H-Graphs 

      Fomin, Fedor; Golovach, Petr; Raymond, Jean-Florent (Journal article; Peer reviewed, 2020)
      For a graph H, a graph G is an H-graph if it is an intersection graph of connected subgraphs of some subdivision of H. H-graphs naturally generalize several important graph classes like interval graphs or circular-arc ...
    • Parameterization Above a Multiplicative Guarantee 

      Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)
      Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given ...
    • Parameterized Complexity of Directed Spanner Problems 

      Fomin, Fedor; Golovach, Petr; Lochet, William; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2020)
      We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance ...
    • Parameterized complexity of PCA 

      Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Journal article; Peer reviewed, 2020)
      We discuss some recent progress in the study of Principal Component Analysis (PCA) from the perspective of Parameterized Complexity.