# Path in an edge-weighted undirected graph

Is it an $NP$-hard problem?

You're given an undirected graph $G(V,E)$ with edge weight $w: E \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$ in unary.

Does there exist a path in $G$ with overall product of edge weights equal $W$ and that does not visit any vertex $v$ more than $\mathrm{max}$-$\mathrm{visit}(v)$ times?

• This is a follow-up of this: cs.stackexchange.com/questions/96177/… – Thinh D. Nguyen Aug 12 '18 at 11:15
• It can be solved in $O(|E|^{\lg W} \cdot |V| \cdot |E|)$ time. Any path must alternate between an edge of weight $\ge 2$, and a path of edges of weight $1$, and an edge of weight $\ge 2$, and a path of edges of weight $1$, etc. Moreover any such path must contain at most $\lg W$ edges whose weight is $\ge 2$. So, enumerate all possibilities for a sequence of $\lg W$ such edges. For a single such possibility, you can figure out whether it's possible to fill out the paths of weight-$1$ edges in a way that respects the constraints using network flow (takes $O(|V|\cdot|E|)$ time per possibility). – D.W. Aug 13 '18 at 13:37
• A flow is not exact since you can re-use edges. But maybe strange enough, it is equivalent to the simple path case. Well, very clever an idea. Thanks for your comment. – Thinh D. Nguyen Aug 13 '18 at 14:44
• I don't follow why you can't use network flow for this. Suppose we want to fill in $k$ gaps. You create a new source node, with $k$ edges, one from the source to the beginning of each gap, and a new sink node, with $k$ edges, one from the end of each gap to the sink. Each of those $2k$ edges has capacity 1, and all other edges have capacity $\infty$. Put capacities on the vertices equal to max-visit (this can be enforced by splitting each vertex $v$ into two vertices $v_{in},v_{out}$ with an edge of capacity max-visit($v$)). Check whether there exists a flow of value $k$. – D.W. Aug 13 '18 at 15:16
• We are not working with directed graph. In fact, if your flow idea work for undirected graph, the classic work of Robertson and Seymour becomes absurd. – Thinh D. Nguyen Aug 13 '18 at 15:28

As D.W., point out in his comment. This problem is not $NP$-hard unless $NP\subseteq QuasiPoly$. The idea is that any such path must not contain more than $\log(n)$ edge of weight > 1.

Enumerate every such sequences of edges (with edge-weight > 1). There are ${O(n^2)}^{\log(n)}$ sequences like that.

For each sequence, to turn it into a solution, we need to fill in the "gap" with weight-1 edges.

This one is a little bit different from his comment. A flow is not the exact idea. What we need is the $k$ vertex-disjoint paths from classical work of Robertson and Seymour.

If the above description is not satisfying enough. Just note that we may split each vertex $v$ into a $\text{max-visit}(v)$-clique, and remember to connect each pair of cliques according to the original edges.

• Why do we need to fill the gaps with vertex-disjoint paths? It seems any paths will be fine; no need for them to be vertex-disjoint. What am I missing? – D.W. Aug 13 '18 at 16:53

This answer misses "$W$ as a unary" in the original question! It serves as a possible answer to a different question only. Be sure to check other answers.

Just set $w$ to be equal to 2 everywhere and $W=2^{|V|}$. We've reduced Hamiltonian path to our problem. So, this is a NP-hard problem in terms of $|V|$ (when we assume $\ln W$ and other parameters in the problem are given in polynomial of $|V|$ of degree less than a given constant greater than 1)

This answer is similar to the OP's answer to his previous question.

• Note that $W$ should be in unary representation, so the reduction you've suggested isn't polynomial. – dave Aug 13 '18 at 10:11
• @dave, thanks. I did miss that "in unary" part. Now I am confused. Can you give an example of "a number W in unary"? – John L. Aug 13 '18 at 10:42
• I'm not sure what are you asking for. But if you are asking what unary is, so an example for $|V|=3$, $2^{|V|}=2^3=8$ in unary would be $11111111$. – dave Aug 13 '18 at 11:36
• I see. In order to represent a unary number $W$, an arbitrarily chosen symbol representing 1 is repeated $W$ times. – John L. Aug 13 '18 at 11:45
• Right, so the running time of an efficient (polynomial) algorithm for the problem can contain a $poly(W)$ factor. – dave Aug 13 '18 at 12:54