Hey guys, this quick problem popped into my head:
You are given a DAG, where each node has an integer value (which may be negative). You can choose an arbitrary subset of nodes, as long as this constraint holds: if you pick a node, you also have to pick all nodes reachable from that node. Obtain the maximum possible value sum.
It feels like an NP problem to me, but I couldn't prove it. Anyone heard about it? Any ideas on how to solve it?
-- Removed
What do you mean by this question? It's not decision problem to begin with.
Corresponding formulation of decision problem is probably the following: "Given a DAG, is it possible to choose proper set of vertices with a sum being at least $$$k$$$?" Yes, this problem lies in $$$\text{NP}$$$ because you can use this set as a certificate.
But, I believe, you're actually asking if this problem is $$$\text{NP-complete}$$$. I think the answer is no:
Consider optimization problem on $$$n$$$ variables $$$x_1, \dots, x_n$$$. For each arc $$$u \to v$$$ we maintain inequality $$$x_u \leq x_v$$$ and additionally we maintain inequalities $$$0 \leq x_k \leq 1$$$. Aim is to maximize $$$a_1 x_1 + a_2 x_2 + \dots + a_n x_n$$$. It seems to me that this instance of linear programming should solve off the problem. Indeed there should always be a solution such that for each variable either $$$x_k=0$$$ or $$$x_k=1$$$ holds.
My reasoning is not very strict but it seems that all vertices of polyhedron satisfying these inequalities also satisfy either $$$x_k=0$$$ or $$$x_k=1$$$ for all variables $$$x_k$$$ and it is known that solution to linear programming problem is always found in one of vertices of mentioned polyhedron.
(Someone more experienced with LP required here)
I am not sure if I am more experienced in LP than you, but I believe what you say is correct.
A formal proof of what you claim can be deduced from the fact that the incidence matrix of every directed graph is totally unimodular.
Could you please elaborate a little bit how the fact that the incidence matrix of every directed graph is totally unimodular helps with the proof?
Sure, I will try to summarize what I thought after reading his comment.
If I understand correctly, he wants to show that the solution for the linear programming problem (where the $$$x_k \in [0,1] \subseteq \mathbb{R}$$$) coincides with the solution of the integer linear programming problem (where the $$$x_k \in$$$ $$$\lbrace 0,1 \rbrace$$$), since the latter is a clear model of the problem.
For every arc $$$u \rightarrow v$$$, we have the inequality $$$x_u \leq x_v$$$ that can be rewritten as $$$x_u - x_v \leq 0$$$.
Hence, if we write the problem in a somewhat canonical fashion, we would say that we want to $$$\text{maximize } c^tx$$$, subject to $$$Ax \leq b$$$. Here $$$c = (a_1, \dots, a_n)$$$ and $$$x = (x_1,\dots, x_n)$$$ are column vectors and $$$ b $$$ is a column vector of as many zeroes as arcs we have in the DAG. Also, $$$A$$$ is the incidence matrix of the graph. Since $$$b$$$ is integral and $$$A$$$ is totally unimodular, every extreme point in the region $$$Ax \leq b$$$ is integral (this is not trivial, but it is a "known" result, see here for example ). The linear programming problem (with $$$x_k \in [0,1] \subseteq \mathbb{R}$$$) has an optimum in an extreme point. Since this extreme point has to be integral, the solution to both problems coincide.
The reason why this is relevant to the original question of this post is that the linear programming problem can be solved in polynomial time, whereas we probably cannot solve integer linear programming in polynomial time.
I hope this helps you understand what I meant in my previous comment.
Yeah, now it's clear. Thanks for the detailed explanation!
What you trying to prove is this problem is in P. This doesn't prove that it is not NP-complete, only that it is not NP-complete unless P=NP.
Don't take it seriously, I'm just continuing this "it's not a decision problem, NP and NP-complete are different things".
Closure Problem
Famous problem. It can be reduced to min-cut so can be solved in polynomial time in maxflow algorithms.
It is a simple problem using Max-Flow algorithm.
For this problem, we can abstract it into a model: selecting a point must pay a certain amount of cost, to find the maximum value of the choice.
We can set up the source point S, connect the profitable point to it, and the flow is the value of that point. If there is a dependency between two points, then there is an infinite flux of edges between them. Finally, T is established to connect all the points that need to pay the cost to other points, and the flow is the cost.
In this way, a cut can represent a selection. So obviously, the minimum cut can represent the choice of the maximum.
We can solve it in polynomial time complexity.
Orz FST-OIer