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?

  • $\begingroup$ This is a follow-up of this: cs.stackexchange.com/questions/96177/… $\endgroup$ Aug 12 '18 at 11:15
  • $\begingroup$ 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). $\endgroup$
    – D.W.
    Aug 13 '18 at 13:37
  • $\begingroup$ 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. $\endgroup$ Aug 13 '18 at 14:44
  • 1
    $\begingroup$ 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$. $\endgroup$
    – D.W.
    Aug 13 '18 at 15:16
  • $\begingroup$ 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. $\endgroup$ 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.

  • 1
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Aug 13 '18 at 16:53

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.