2021/03/04 by Charis Papadopoulos, Papadopoulos, Charis, Spyridon Tzimas +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2103.03035
openalex publication_date 2021/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A typical example that behaves computationally different in subclasses of chordal graphs is the Subset Feedback Vertex Set (SFVS) problem: given a vertex-weighted graph G=(V,E) and a set S⊆ V, the Subset Feedback Vertex Set (SFVS) problem asks for a vertex set of minimum weight that intersects all cycles containing a vertex of S. SFVS is known to be polynomial-time solvable on interval graphs, whereas SFVS remains \NP-complete on split graphs and, consequently, on chordal graphs. Towards a better understanding of the complexity of SFVS on subclasses of chordal graphs, we exploit structural properties of a tree model in order to cope with the hardness of SFVS. Here we consider variants of the leafage that measures the minimum number of leaves in a tree model. We show that SFVS can be solved in polynomial time for every chordal graph with bounded leafage. In particular, given a chordal graph on n vertices with leafage ℓ, we provide an algorithm for SFVS with running time nO(ℓ). We complement our result by showing that SFVS is \W[1]-hard parameterized by ℓ. Pushing further our positive result, it is natural to consider a slight generalization of leafage, the vertex leafage, which measures the smallest number among the maximum number of leaves of all subtrees in a tree model. However, we show that it is unlikely to obtain a similar result, as we prove that SFVS remains \NP-complete on undirected path graphs, i.e., graphs having vertex leafage at most two. Moreover, we strengthen previously-known polynomial-time algorithm for SFVS on rooted path graphs that form a proper subclass of undirected path graphs and graphs of mim-width one.