Feedback Vertex Set with vertex partitions?

Question

I've encountered this problem in a program analysis project I'm working on, where I've got a bunch of functions defined in terms of each other, and because I'm using SMT which doesn't support recursion, I'd like to define as many functions outright as possible, so that fewer are left to be solved by the SMT solver.

In terms of pure graph theory, my problem is this:

Given:

• A directed (possibly cyclic) graph $G=(V,E)$
• A partitioning of $V$ into disjoint subsets $V_1, \ldots, V_k$

I want to choose:

• $v_i \in V_i$ for each $1 \leq i \leq k$ that minimizes the feedback-vertex number of the subgraph of $G$ induced by $\{v_1,, \ldots v_k \}$

I'm fairly guessing the problem is $NP$-hard, because of its reliance on the Feedback Vertex Set problem. If we assume that our $V_i$ sets are small, say with a maximum size $M$, then there are at most $M^k$ combinations to try.

I'm wondering:

• Has this problem (or anything similar) been studied before?
• Is this problem $NP$-hard, or does it fall into one of the subsets of feedback-vertex that is tractable (e.g. chordal graphs, convex-bipartite, etc.)
• Does anyone know of a way to reduce the Feedback Vertex Set problem to this? It's solvable in $O(1.7548^n)$ time, so if I can translate my problem into this one it's entirely possible it's solvable for small inputs. But for all I know, my problem is harder than Feedback-vertex.
• Are there any approximation algorithms that can be adapted to my variant of the problem, that are maybe not optimal, but would give near-optimal results quickly

Answer 1

Your problem reduces to Feedback Vertex Set by turning every subset $V_i$ into a clique, and creating one additional vertex $v_i$ for each subset $V_i$ that is adjacent to all vertices in $V_i$. It might be easier to think in terms of the complement problem, Maximum Induced Forest.

Since $V_i\cup \{v_i\}$ is a clique, we can select at most two vertices from this set to be in our solution (to Maximum Induced Forest). We can assume $v_i$ is always in the solution, since if less than two vertices of $V_i$ are in the solution we can safely include $v_i$, and if exactly two vertices of $V_i$ are in the solution then $v_i$ is not, but we can swap one of these two vertices (from $V_i$) with $v_i$.

A solution to Maximum Induced Forest thus selects at most one vertex from each set $V_i$ such that the result is a acyclic, and these are exactly the vertices we should select in a solution to the original problem (from the sets $V_i$ from which no vertices are selected, we can just arbitrarily select a vertex, and this vertex will be in our feedback vertex set). Conversely, it is easy to see how a solution to the original problem corresponds to a Maximum Induced Forest/Feedback Vertex Set in the graph created in this reduction.

This gives you a $O(1.7548^{n+k})$-time algorithm. If you allow parallel edges you can (instead of creating this additional vertex $v_i$) double up the edges in every clique, which has the same effect (and may give a faster algorithm, if your algorithm for solving feedback vertex set allows for parallel edges).

The problem is $NP$-hard. We can reduce from Feedback Vertex Set. To decide whether a graph has a Feedback Vertex set of size at most $s$, we create $s$ cliques of size $n+1$. We can force that one vertex of this clique is always in the solution (by including it in a singleton set $V_i$). We then create for each vertex $v$ in the original graph a set $V_i$ that contains $v$, and one vertex from each of the $s$ cliques. In at most $s$ of these sets $V_i$, we can select a vertex from each clique, but in the remaining $n-s$ sets we must select a vertex from the original graph. Therefore, we can find a solution to the original problem with feedback vertex set number $0$ if and only if the input graph had feedback vertex set number of at most $s$.