Blar i Bergen Open Research Archive på forfatter "Golovach, Petr"

Acyclic, star, and injective colouring: bounding the diameter∗
Brause, Christoph; Golovach, Petr; Martin, Barnaby; Ochem, Pascal; Paulusma, Daniël; Smith, Siani (Journal article; Peer reviewed, 2022)We examine the effect of bounding the diameter for a number of natural and wellstudied variants of the COLOURING problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest ... 
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 ... 
An Algorithmic MetaTheorem for Graph Modification to Planarity and FOL
Fomin, Fedor; Golovach, Petr; Stamoulis, Giannos; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)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 deletion, edge deletion, edge contraction, or ... 
Approximating Acyclicity Parameters of Sparse Hypergraphs
Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios (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 ... 
Approximating Long Cycle Above Dirac's Guarantee
Fomin, Fedor; Golovach, Petr; Simonov, Kirill; Sagunov, Danil (Journal article; Peer reviewed, 2023)Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better ... 
Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)We introduce the rendezvous game with adversaries. In this game, two players, Facilitator and Divider, play against each other on a graph. Facilitator has two agents and Divider has a team of k agents located in some ... 
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 ... 
Combing a Linkage in an Annulus
Golovach, Petr; Stamoulis, Giannos; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)A linkage in a graph 𝐺 of size 𝑘 is a subgraph 𝐿 of 𝐺 whose connected components are 𝑘 paths. The pattern of a linkage of size 𝑘 is the set of 𝑘 pairs formed by the endpoints of these paths. A consequence of the ... 
Compound Logics for Modification Problems
Fomin, Fedor; Golovach, Petr; Sau, Ignasi; Stamoulis, Giannos; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)We introduce a novel modeltheoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with ... 
Computing Paths of Large Rank in Planar Frameworks Deterministically
Fomin, Fedor; Golovach, Petr; Korhonen, Tuukka Matias Aleksanteri; Stamoulis, Giannos (Journal article; Peer reviewed, 2023)A framework consists of an undirected graph G and a matroid M whose elements correspond to the vertices of G. Recently, Fomin et al. [SODA 2023] and Eiben et al. [ArXiV 2023] developed parameterized algorithms for computing ... 
Connecting Vertices by Independent Trees
Basavaraju, Manu; Fomin, Fedor; Golovach, Petr; Saurabh, Saket (Journal article; Peer reviewed, 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 ... 
Cyclability in graph classes
Crespelle, Christophe Dominique; Golovach, Petr (Journal article; Peer reviewed, 2022)A subset T ⊆ 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 set of vertices of size at most k is cyclable. ... 
Detours in Directed Graphs
Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Sagunov, Danil; Simonov, Kirill; Saurabh, Saket (Journal article; Peer reviewed, 2022)We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, ... 
Detours in directed graphs
Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Sagunov, Danil; Saurabh, Saket; Simonov, Kirill (Journal article; Peer reviewed, 2023)We study two “above guarantee” versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, ... 
Diverse Collections in Matroids and Graphs
Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Journal article; Peer reviewed, 2021)We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the Weighted Diverse ... 
Diverse collections in matroids and graphs
Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Journal article; Peer reviewed, 2023)We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the Weighted Diverse Bases problem consists of a matroid M, a weight function ω : ... 
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 (Journal article; Peer reviewed, 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 ...