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:

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Nonpartisan Feedback Vertex Set

  • Nidhi Purohit,
  • Souvik Saha,
  • Saket Saurabh,
  • Anannya Upasana

摘要

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: