1
$\begingroup$

Given a graph consists of two-colored nodes(e.g. white and black) and a starting node, and every time you visit a node, its color is switched(from black to white, or, white to black), how to find the minimum path such that all nodes are converted to black (or white, since it is equivalent)?

$\endgroup$

closed as unclear what you're asking by Juho, Evil, Discrete lizard, Thomas Klimpel, Luke Mathieson Feb 3 at 0:30

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ What have you tried? Where did you get stuck? Why should this problem be considered interesting (i.e., why are you trying to solve this and not some other problem)? $\endgroup$ – dkaeae Jan 18 at 8:32
1
$\begingroup$

This problem is $NP$-complete, there is a quite simple reduction from Hamiltonian Path. Therefore, there's (likely) no way to solve this problem efficiently in general, so the solution method will need to be tailored to the inputs you are interested in solving (brute force for small instances, heuristic methods for large instances, specialized methods for instances with special structure,...).

$\endgroup$
  • $\begingroup$ Would you mind expanding on the reduction from the Hamiltonian Path problem? $\endgroup$ – RcnSc Jan 18 at 8:37
  • 1
    $\begingroup$ @RcnSc Construct an instance where all the nodes initially have the same color, and go from there. $\endgroup$ – Juho Jan 18 at 8:40
  • $\begingroup$ Perhaps I am overlooking something here, but I am not immediately convinced. There are graphs that have no Hamiltonian path, but do have a path where every vertex is visited an odd number of times? $\endgroup$ – Hendrik Jan Jan 18 at 13:43
  • $\begingroup$ @HendrikJan The question asks for the shortest path. $\endgroup$ – Tom van der Zanden Jan 18 at 13:48

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