1
$\begingroup$

I have a directed, colored graph (each node has a color), and I want to find if a path from node A to node B exists such that the path goes through each color at MOST once.

I think this problem can be formulated using network flow. Somehow a penalty can be placed on nodes of the same color that makes the flow 0 or infinity if a node is repeated.

Thanks!

$\endgroup$
  • 2
    $\begingroup$ Your problem looks really similar to an exercise from the 'Algorithm Design' book by Kleinberg & Tardos. The exercise in question is 8.12 and the goal is to prove NP Completeness. So try thinking about a possible reduction. $\endgroup$ – jjohn Nov 8 '15 at 1:37
  • $\begingroup$ Thats interesting. I'm pretty sure the problem is in P, but I'll look into that. $\endgroup$ – PK5144 Nov 8 '15 at 2:50
  • $\begingroup$ @jjohn Note how different the question "I'd like to have an algorithm for X" is from "What is the complexity of X". In particular, proving NP-hardness does not answer the first one. $\endgroup$ – Raphael Nov 8 '15 at 7:45
  • $\begingroup$ It's not for HW... However, I do think that the problem is NOT NP-Hard or NP-Complete. $\endgroup$ – PK5144 Nov 8 '15 at 9:07
  • 1
    $\begingroup$ @PK5144 So are you interested in just a hardness proof, or do you also want some algorithm for solving the problem? (A non-polynomial one, that is). $\endgroup$ – Juho Nov 9 '15 at 12:15
2
$\begingroup$

I understand from your question that you are asking for a polynomial-time algorithm for solving the problem. It is unlikely there is one for the problem.

Taking the hint of @jjohn, this is exactly the same problem as in the Kleinberg-Tardos book, Exercise 8.12. They call the problem evasive path. Here, color classes represent different zones, and you must get from $s$ to $t$ visiting each zone at most once.

There are at least two straightforward reductions. The other one is from directed Hamiltonian path, and the other one from set partitioning, i.e. exact cover. If you still care about solving the problem, you can do it in $O^*(2^k)$-time, where $k$ is the number of colors.

$\endgroup$
  • $\begingroup$ What is the reduction from directed hamiltonian path to evasive path? $\endgroup$ – user774025 Feb 27 '16 at 23:01

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.