2
$\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$
6
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 12:15

2 Answers 2

3
$\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$
2
  • $\begingroup$ What is the reduction from directed hamiltonian path to evasive path? $\endgroup$
    – user774025
    Feb 27, 2016 at 23:01
  • $\begingroup$ Give each vertex its own color? $\endgroup$ Apr 24, 2022 at 10:39
0
$\begingroup$

This is NPC and we can reduce a $k$-SAT problem (usually $3$-SAT) to this.

Firstly given a $3$-SAT problem, we can construct a full-connected directed graph: a source node $s$, a sink node $t$ and some layers. Each layer comes from a clause in the SAT problem and have $3$ (or $k$) nodes.

Then we let each pair of nodes form a zone/color if they are oppositie, i.e., $x$ and $\bar{x}$. So it's easy to see that we can find such a path from $s$ to $t$, if and only if there is a solution for the SAT problem.

$\endgroup$

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.