• 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 ...
    • 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 (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 ...
    • 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 ...
    • Parameterized complexity of secluded connectivity problems 

      Fomin, Fedor; Golovach, Petr; Karpov, Nikolay; Kulikov, Alexander S (Conference object; Peer reviewed; Journal article, 2015)
      The Secluded Path problem introduced by Chechik et al. in [ESA 2013] models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of ...
    • Parameterized complexity of the spanning tree congestion problem 

      Bodlaender, Hans L.; Fomin, Fedor; Golovach, Petr; Otachi, Yota; van Leeuwen, Erik Jan (Peer reviewed; Journal article, 2012-09)
      We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class ...
    • Parameterized k-Clustering: Tractability Island 

      Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Peer reviewed; Journal article, 2019)
      In k-Clustering we are given a multiset of n vectors X subset Z^d and a nonnegative number D, and we need to decide whether X can be partitioned into k clusters C_1, ..., C_k such that the cost sum_{i=1}^k min_{c_i in R^d} ...
    • Refined Complexity of PCA with Outliers 

      Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Simonov, Kirill (Conference object; Peer reviewed; Journal article, 2019)
      Principal component analysis (PCA) is one of the most fundamental procedures in exploratory data analysis and is the basic step in applications ranging from quantitative finance and bioinformatics to image analysis and ...
    • Subgraph Complementation 

      Fomin, Fedor; Golovach, Petr; Strømme, Torstein J. F.; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2020-02)
      A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is there ...
    • Variants of plane diameter completion 

      Golovach, Petr; Requile, Clement; Thilikos, Dimitrios M. (Conference object; Peer reviewed; Journal article, 2015)
      The Plane Diameter Completion problem asks, given a plane graph G and a positive integer d, if it is a spanning subgraph of a plane graph H that has diameter at most d. We examine two variants of this problem where the ...