Subset feedback vertex sets in chordal graphs

Abstract Given a graph G = ( V , E ) and a set S ⊆ V , a set U ⊆ V is a subset feedback vertex set of ( G , S ) if no cycle in 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 ) 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.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.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.8638 n ) running time. We also obtain that a chordal graph G has at most 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.5848 n on this graph class. For arbitrary graphs, the gap is substantially wider, as the best known upper and lower bounds are 1.8638 n and 1.5927 n , respectively.