0
$\begingroup$

Let $G(V,E), |V| = n, $ be a (undirected) graph and a coloring function $f: V\rightarrow \{1,2,3...s \}$ which assigns to each vertex a color, such that in total there are $n/s$ vertices of each of the $s$ colors.

Starting from a given vertex $a$, the task is to find out if there is a path in the graph, such that it contains all the s colors which are nevertheless represented only once in the path. I guess one way to handle this is to assign to each vertex a list or eventually a dictionary of all colors it is connected to but it's own color. In that case one would have to consider each vertex starting from $a$ such that in it's list of colors it contains at least one color. But as far as I can see it will lead to a brute force algorithm.

Can one do better than this ? Thanks for any help.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The problem is NP-hard: it is as hard as Hamiltonian path, when $s=n$ and $f$ is a bijection. Therefore, you shouldn't expect any efficient algorithm that always works. You could study algorithms for the Hamiltonian path problem and try generalizing them to your situation (e.g., using a SAT solver).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks. One might use dynamic programming (Bellman-Held-Karp) in the case of the Hamiltonian path problem that aims at finding a path through all the vertices which is different from the problem above in that we need to consider a subset $S \subset V, |S| = s$ satisfying the required property. You are suggesting to adapt this to the problem above by using a SAT solver. I do not have any experience with the SAT solver. $\endgroup$
    – user153345
    Sep 6, 2022 at 9:36
  • $\begingroup$ @user153345 I can second trying SAT solvers for this. They've worked nicely for me in practice, especially if you precolor a large clique first. Just google it, you will find lots of material to get you started. $\endgroup$
    – Juho
    Sep 6, 2022 at 10:17
  • $\begingroup$ Thanks. What do you mean by precoloring a large clique first ? Can you suggest any google link ? $\endgroup$
    – user153345
    Sep 6, 2022 at 10:36

Your Answer

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

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