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