Subset Feedback Vertex Set in Chordal and Split Graphs
| Autor: | Varun Rajan, Saket Saurabh, Geevarghese Philip, Prafullkumar Tale |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030174019 CIAC |
| DOI: | 10.1007/978-3-030-17402-6_30 |
| Popis: | In the Subset Feedback Vertex Set (Subset-FVS) problem the input consists of a graph G, a subset \(T\) of vertices of \(G\) called the “terminal” vertices, and an integer k. The task is to determine whether there exists a subset of vertices of cardinality at most k which together intersect all cycles which pass through the terminals. Subset-FVS generalizes several well studied problems including Feedback Vertex Set and Multiway Cut. This problem is known to be NP-Complete even in split graphs. Cygan et al. proved that Subset-FVS is fixed parameter tractable (FPT) in general graphs when parameterized by k [SIAM J. Discrete Math (2013)]. In split graphs a simple observation reduces the problem to an equivalent instance of the 3-Hitting Set problem with same solution size. This directly implies, for Subset-FVS restricted to split graphs, (i) an FPT algorithm which solves the problem in \(\mathcal {O}^{\star } (2.076^k)\) time (The \(\mathcal {O}^{\star } ()\) notation hides polynomial factors.) [Wahlstrom, Ph.D. Thesis], and (ii) a kernel of size \(\mathcal {O}(k^3)\). We improve both these results for Subset-FVS on split graphs; we derive (i) a kernel of size \(\mathcal {O}(k^2)\) which is the best possible unless Open image in new window , and (ii) an algorithm which solves the problem in time \(\mathcal {O}^*(2^k)\). Our algorithm, in fact, solves Subset-FVS on the more general class of chordal graphs, also in \(\mathcal {O}^*(2^k)\) time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|