Subset feedback vertex sets in chordal graphs ?
Given a graph G=(V,E) G = ( V , E ) and a set S?V S ? V , a set U?V U ? V is a subset feedback vertex set of (G,S) ( G , S ) if no cycle in G[V?U] G [ V ? U ] contains a vertex of S. The Subset Feedback Vertex Set problem takes as input G, S, and an integer k , and the question is whether (G,S) ( G , S ) has a subset feedback vertex set of cardinality or weight at most k . Both the weighted and the unweighted versions of this problem are NP-complete on chordal graphs, even on their subclass split graphs. We give an algorithm with running time O(1.6708n) O ( 1.6708 n ) that enumerates all minimal subset feedback vertex sets on chordal graphs on n vertices. As a consequence, Subset Feedback Vertex Set can be solved in time O(1.6708n) O ( 1.6708 n ) on chordal graphs, both in the weighted and in the unweighted case. As a comparison, on arbitrary graphs the fastest known algorithm for these problems has O(1.8638n) O ( 1.8638 n ) running time. We also obtain that a chordal graph G  has at most 1.6708n 1.6708 n minimal subset feedback vertex sets, regardless of S . This narrows the gap with respect to the best known lower bound of 1.5848n 1.5848 n on this graph class. For arbitrary graphs, the gap is substantially wider, as the best known upper and lower bounds are 1.8638n 1.8638 n and 1.5927n 1.5927 n , respectively.
subset feedback vertex set chordal graph maximum number of minimal subset feedback vertex sets exact exponential-time algorithm