6
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ This is a follow-up of this: cs.stackexchange.com/questions/96177/… $\endgroup$
    – Thinh D. Nguyen
    Commented Aug 12, 2018 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. ♦
    Commented Aug 13, 2018 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$
    – Thinh D. Nguyen
    Commented Aug 13, 2018 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. ♦
    Commented Aug 13, 2018 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$
    – Thinh D. Nguyen
    Commented Aug 13, 2018 at 15:28

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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. ♦
    Commented Aug 13, 2018 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.