1
$\begingroup$

Given a graph $G=(V,E)$, metric spaces $\delta:E\rightarrow \mathbb{Z}^{+}$ and $w:E\rightarrow \mathbb{Z}^{+}$, terminal vertices $s,t\in V$, do there exists $s\rightarrow t$ path $P=(V_{p},E_{p})$ such that $\sum_{e\in E_{p}} w(e) \leq W$ and $\sum_{e\in E_{p}} \delta(e) \leq K$, where $W,K\in Z^{+}$.

This is Weight constrained Shortest Path Problem, and known to be NP-complete for undirected as well as directed even acyclic graphs. as long as $\delta$ and $w$ is not equal for all edges. Now if we move weight from edges to vertices and change $\leq$ of total weight constraint to $=$ then the new problem is:

Given a directed acyclic graph $G=(V,E)$, metric spaces $\delta:E\rightarrow \mathbb{Z}^{+}$ and $w:V\rightarrow \mathbb{Z}^{+}$, terminal vertices $s,t\in V$, do there exists $s\rightarrow t$ path $P=(V_{p},E_{p})$ such that $\sum_{v\in V_{p}} w(v) = W$ and $\sum_{e\in E_{p}} \delta(e) \leq K$.

Is this problem known ? is this solvable in P time ? or this is NP-complete too ? I think even if we replace $\mathbb{Z}^{+}$ with $\mathbb{R}^{+}$ it will not change nature of the problem.

If we set $W=\vert V \vert$ then it tries to reach all the vertices which looks like hamiltonian path problem, but it is a DAG.

Update

I was trying to reduce it from Subset Sum as suggested by @D.W.

Given $X=\{1,2,3\}$ of size $\vert X \vert = n$ I can convert that to a graph of $n^{2}+n+2$ vertices. We can make $n$ layers of $X$ and connect every vertex with all vertices of next layer except itself. Keep a vertex with 0 weight on each layer. As show below.

enter image description here

But this reduction has 2 restrictions.

  1. Every Layer is not complete bipartite (e.g. $2_{i}$ does not connect to $2_{i+1}$).
  2. Every layer must have a vertex with 0 weight.

Now this does not prove the second problem for General purpose DAG. I can not connect $x_{i}\rightarrow x_{i+1}$ because that will change the original problem. So if there is a DAG that looks very similar to this one but have $n^{2}$ edges between each layer and have no 0 weight vertex this reduction does not apply to that graph.

Also in this formulation I can take the same element twice $1_{1}\rightarrow 2_{2}\rightarrow 1_{3}$ which will add to $4$. Which I should not be allowed

$\endgroup$
  • 1
    $\begingroup$ Have you tried reducing from subset-sum? $\endgroup$ – D.W. Feb 6 '18 at 8:05
  • $\begingroup$ Yes that was a typo, Thanks. The problem is with the acyclic. But if the problem is known I don't need to reduce. Also I don't think I can reduce the second one from first one. I thought I will check the proof for the first one but that is a private communication. $\endgroup$ – Neel Basu Feb 6 '18 at 9:37
  • $\begingroup$ I suggest you try reducing from subset-sum. The reduction looks immediate to me, if I'm not missing something, but I'll let you check the details. $\endgroup$ – D.W. Feb 6 '18 at 13:08
  • $\begingroup$ Yes I understand why it looks immediate each element will be translated to a vertex of a complete graph. The only thing I am afraid of is to prove it for DAG and remove the complete graph restriction. I am not sure how far I can go with vertex splitting to get rid of that. I will try tonight. $\endgroup$ – Neel Basu Feb 6 '18 at 15:35
  • $\begingroup$ Thanks. Partial Success. But the DAG generated after reduction is not a general DAG. Please check update. $\endgroup$ – Neel Basu Feb 6 '18 at 19:22
1
$\begingroup$

Check the definition of reduction again. A reduction that works for general dags is a perfectly valid reduction. It meets all of the conditions in the definition. I suggest working through the definition -- that should help you see what is going on.

Or, to put it another way: The problem for "general DAG" is at least as hard as the problem for "a particular type of DAG", so if you've proved the problem is NP-hard for a particular type of DAG, you've also proven it is NP-hard for general DAGs, too.

$\endgroup$
  • $\begingroup$ Definition requires P-time transformation of Input $I_{x}\rightarrow I_{y}$. Now how can I defy this argument ? if $Y$ is chain of complete bipartite graphs (with no infinite edge cost allowed) then how will that transform function generate $I_{y}$ ? $\endgroup$ – Neel Basu Feb 7 '18 at 8:19
  • $\begingroup$ Also is this even correct ? because I can take the same element twice $1_{1}\rightarrow 2_{2}\rightarrow 1_{3}$ which will add to $4$. Which I should not be allowed. This may lead to a scenario when there is no such subset in the original problem but there is a path in the reduced problem. Also number of solutions not preserved. $\endgroup$ – Neel Basu Feb 7 '18 at 11:57

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.