8
$\begingroup$

This is task from the German IT contest ("Bundeswettbewerb Informatik"), but since the deadline is past, asking this question is no cheating.

Given a vertex-weighted, directed graph $G=(V, E)$ and values $c_v$, find a subset of nodes $V_{res}\subseteq V$ that maximizes $$\sum_{v \in V_{res}} c_v$$ subject to $$\forall (u,v) \in E: u \in V_{res} \implies v \in V_{res}$$ Is this problem NP-hard?

I could prove that the problem is in P if every node has either no parents or no children by showing that in this case, it can be solved by Vertex Cover on bipartite graphs, but I failed in finding a reduction that proofes the NP-hardness of the original problem.

Can somebody give me a hint how to do this?

PS: In the contest, the task was only to find an algorithm that solves this problem, the original (German) definition is task 1 of this document: http://www.bundeswettbewerb-informatik.de/fileadmin/templates/bwinf/aufgaben/bwinf35/aufgaben352.pdf

$\endgroup$
  • 5
    $\begingroup$ Without loss of generality, you can focus on the case of a dag (directed acyclic graph). In a general directed graph, decompose into strongly connected components; then you'll either take all the nodes in a component, or none of them; so you can form the meta-graph (with one vertex per component) and solve the problem on the meta-graph. $\endgroup$ – D.W. May 22 '17 at 2:08
  • $\begingroup$ @D.W. , I assume you intend to topologically sort the DAG, but it is not clear to me as what exactly your next step will be? For each vertex in the meta-graph to sum the weight of all of its decedents? $\endgroup$ – Eric_ Jun 4 '17 at 17:31
  • $\begingroup$ @Eric_, alas, I don't have a next step in mind. I'm just saying that if you can find an algorithm to solve this for an arbitrary DAG, you can use that to solve it for an arbitrary directed graph. Maybe that gives someone some ideas for how to approach the problem -- or maybe not. I don't know how to solve it myself, I'm afraid. $\endgroup$ – D.W. Jun 4 '17 at 23:07
1
$\begingroup$

The problem is polynomial-time solvable, suggested in Lemma 1 of the paper Computational Complexity of Some Maximum Average Weight Problems with Precedence Constraints.

Basically the idea is to write a linear program on variables $x_i\in[0,1]$, where $x_u-x_v\leq 0$ if $(u,v)\in E$. The signed adjacency matrix is totally unimodular, so we can compute the integral optimum.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.