Browsing Bergen Open Research Archive by Author "Golovach, Petr"
Now showing items 120 of 28

An Algorithmic MetaTheorem 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 nvertex 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 rrank 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 kcyclable 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, 20190906)An undirected graph G is ddegenerate 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 FTMDeletion problem has as input an nvertex 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 2connected graphs G and H are 2isomorphic, or equivalently, their cycle matroids are isomorphic, if and only if G can be transformed into H by a series of operations ... 
LowRank Binary Matrix Approximation in ColumnSum Norm
Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Simonov, Kirill (Journal article; Peer reviewed, 2020)We consider 𝓁₁Rankr 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 columnsum 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 kvertex labeled graph to another kvertex graph. We consider a general family of graph modification problems, called LReplacement 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 HGraphs
Fomin, Fedor; Golovach, Petr; Raymond, JeanFlorent (Journal article; Peer reviewed, 2020)For a graph H, a graph G is an Hgraph if it is an intersection graph of connected subgraphs of some subdivision of H. Hgraphs naturally generalize several important graph classes like interval graphs or circulararc ... 
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 fixedparameter 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 tspanner problems on directed graphs. For a positive integer t, a multiplicative tspanner 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.