2019/01/08 by Philip, Geevarghese, Rajan, Varun, Saurabh, Saket +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1901.02209
In the Subset Feedback Vertex Set (Subset-FVS) problem the input is 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 \OhStar(2.076k) time \footnoteThe \(\OhStar()\) notation hides polynomial factors.% for Subset-FVS in Chordal % Graphs [Wahlström, Ph.D. Thesis], and (ii) a kernel of size O(k3). We improve both these results for Subset-FVS on split graphs; we derive (i) a kernel of size O(k2) which is the best possible unless \NP ⊆ \coNP/\sf poly, and (ii) an algorithm which solves the problem in time O^*(2k). Our algorithm, in fact, solves Subset-FVS on the more general class of chordal graphs, also in O^*(2k) time.