Classifying subset feedback vertex set for \(H\)-free graphs (Q6549683)

This paper is concerned with establishing computational complexity dichotomies for variants of the subset feedback vertex set problem. The dichotomies are established for \(H\)-free graphs, for suitabley chosen \(H\).\N\NThe feedback vertex set is one of the classical combinatorial optimization problems studied in the literature. In this problem, we are given a graph \(G\) (directed or undirected) and the goal is to find the smallest cardinality subset of vertices such that every cycle in \(G\) intersects at least one of these vertices.\N\NIn the weighted version, the vertices are weighted and the goal is to find the minimum-weight subset of vertices whose removal knocks off all the cycles in the graph.\N\NBoth the above problems are NP-hard. The authors study a generalization of the traditional feedback vertex set problem by providing a subset of vertices \(T\) and requiring us to find the smallest subset of vertices which intersect every cycle that intersects \(T\). The weighted version is defined similarly.\N\NThe paper uses the following notation scheme:\N\begin{itemize}\N\item[1.] \(P_r\) refers to the path graph on \(r\) vertices.\N\item[2.] \(G_1+G_2\) refers to the disjoint union of two vertex-disjoint graphs \(G_1\) and \(G_2\).\N\item[3.] \(s\cdot G\) refers to \(s\) disjoint copies of the graph \(G\).\N\item[4.] A graph \(G\) is said to be \(H\)-free if \(G\) does not contain \(H\) as an induced subgraph. In other words, \(G\) cannot be transformed into \(H\) using a sequence of vertex deletions.\N\end{itemize}\N\NThe main contributions of the paper are as follows:\N\begin{itemize}\N\item[1.] For a graph \(H\), the weighted subset feedback vertex set on \(H\)-free graphs is polynomial-time solvable if \(H \subseteq 2\cdot P_1+P_4\), and is NP-hard otherwise.\N\item[2.] For a graph \(H\), the subset feedback vertex set on \(H\)-free graphs is polynomial-time solvable if \(H \subseteq s\cdot P_1+P_4\) for every \(s \ge 0\), and is NP-hard otherwise.\N\end{itemize}\N\NThe exposition is lucid and coherent. All the lemmata building up to the main theorems are neatly laid out and explained. The paper makes a valuable contribution to the literature.