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$ – Thinh D. Nguyen 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$ – Thinh D. Nguyen 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$ – 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.

| cite | improve this answer | |
  • 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

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.

| cite | improve this answer | |
  • 1
    $\begingroup$ Note that $W$ should be in unary representation, so the reduction you've suggested isn't polynomial. $\endgroup$ – dave Aug 13 '18 at 10:11
  • $\begingroup$ @dave, thanks. I did miss that "in unary" part. Now I am confused. Can you give an example of "a number W in unary"? $\endgroup$ – John L. Aug 13 '18 at 10:42
  • $\begingroup$ 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$. $\endgroup$ – dave Aug 13 '18 at 11:36
  • $\begingroup$ I see. In order to represent a unary number $W$, an arbitrarily chosen symbol representing 1 is repeated $W$ times. $\endgroup$ – John L. Aug 13 '18 at 11:45
  • $\begingroup$ Right, so the running time of an efficient (polynomial) algorithm for the problem can contain a $poly(W)$ factor. $\endgroup$ – dave Aug 13 '18 at 12:54

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.