On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
- PDF / 3,273,596 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 70 Downloads / 183 Views
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest Konrad K. Dabrowski1 · Carl Feghali2 · Matthew Johnson1 · Giacomo Paesani1 · Daniël Paulusma1 · Paweł Rzążewski3 Received: 5 August 2019 / Accepted: 26 March 2020 © The Author(s) 2020
Abstract A graph is H-free if it contains no induced subgraph isomorphic to H. We prove new complexity results for the two classical cycle transversal problems Feedback Vertex Set and Odd Cycle Transversal by showing that they can be solved in polynomial time on (sP1 + P3 )-free graphs for every integer s ≥ 1. We show the same result for the variants Connected Feedback Vertex Set and Connected Odd Cycle Transversal. We also prove that the latter two problems are polynomial-time solvable on cographs; this was already known for Feedback Vertex Set and Odd Cycle Transversal. We complement these results by proving that Odd Cycle Transversal and Connected Odd Cycle Transversal are NP-complete on (P2 + P5 , P6 )-free graphs. Keywords Odd cycle transversal · Feedback vertex set · H-free graph · Connected transversal
* Konrad K. Dabrowski [email protected] Carl Feghali [email protected] Matthew Johnson [email protected] Giacomo Paesani [email protected] Daniël Paulusma [email protected] Paweł Rzążewski [email protected] 1
Department of Computer Science, Durham University, Durham, UK
2
Department of Informatics, University of Bergen, Bergen, Norway
3
Faculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, Poland
13
Vol.:(0123456789)
Algorithmica
1 Introduction Graph transversal problems play a central role in Theoretical Computer Science. To define the notion of a graph transversal, let H be a family of graphs, G = (V, E) be a graph and S ⊆ V be a subset of vertices of G. The graph G − S is obtained from G by removing all vertices of S and all edges incident to vertices in S. We say that S is an H-transversal of G if G − S is H-free, that is, if G − S contains no induced subgraph isomorphic to a graph of H . In other words, S intersects every induced copy of every graph of H in G. Let Cr and Pr denote the cycle and path on r vertices, respectively. Then S is a vertex cover, feedback vertex set, or odd cycle transversal if S is an H-transversal for, respectively, H = {P2 } (that is, G − S is edgeless), H = {C3 , C4 , …} (that is, G − S is a forest), or H = {C3 , C5 , C7 , …} (that is, G − S is bipartite). Usually the goal is to find a transversal of minimum size in some given graph. In this paper we focus on the decision problems corresponding to the three transversals defined above. These are the Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal problems, which are to decide whether a given graph has a vertex cover, feedback vertex set or odd cycle transversal, respectively, of size at most k for some given positive integer k. Each of these three problems is well studied and is well known to be NP-complete. We may add furthe
Data Loading...
