# 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/… 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. 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. 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