Nonpartisan Feedback Vertex Set
摘要
The problem of finding a feedback vertex set in a graph \((G = V, E)\) involves finding a subset \(S\subseteq V\) such that the graph \(G[V \setminus S]\) is a forest. In the Feedback Vertex Set problem, the objective is to find a feedback vertex set S of size at most k. Motivated by the ever-growing study of graph problems with fairness constraints, we focus on the Fair Feedback Vertex Set problem, which is an extension of the Feedback Vertex Set problem for vertex colored graphs. The input to this problem is an undirected graph G with vertices partitioned into sets \(\{V_1,\ldots , V_r\}\) , or alternatively, the vertices are colored with r colors. Additionally, there are budgets specified for the number of vertices that can be selected from each color class, represented by integers \(c_1, \ldots , c_r\) . The goal is to find a feedback vertex set for G that includes at most \(c_i\) vertices from \(V_i\) . The Connected Fair Feedback Vertex Set problem is an extension of Fair Feedback Vertex Set where the graph induced on the solution vertices needs to be connected. We obtain the following results for these problems: