I am trying to create a polynomial time algorithm for a problem defined as follows:


$c$ is an integer constant $\geq 1$

Input: An undirected graph $G=(V,E)$.

Question: Can the vertices in $G$ be colored with two colors such that

  1. no edge’s endpoint vertices have the same color and

  2. there is a path in this colored version of $G$ with $\geq c$ edges in which no vertex or edge repeats and the vertex-colors alternate for the entire length of the path?

I understand that the coloring can be checked by a simple breadth first search in polynomial time.

My problem is with the path of length $c$. My professor stated that the reason that this is not NP-complete and analogous to the longest path problem is because $c$ is a constant. I fail to see why this restriction causes it to differ from longest path. If anyone could clarify this for me I'd be really greatful.

  • 1
    $\begingroup$ Naive attempt first: how many paths of that length are there? (Note that when your professor says "this is not NP-complete but in P" they pretend to know that P $\neq$ NP.) $\endgroup$ – Raphael Jan 29 '14 at 20:35
  • $\begingroup$ Your professor is right. To help you out here: imagine we replace the constant $c$ with the number $3$ (say). Do you now see why there exists a polynomial-time algorithm? What if we replaced $c$ with $7$? Could you prove there is a polynomial-time algorithm in this case, too? $\endgroup$ – D.W. Jan 30 '14 at 2:51

If you want to check whether a graph has a path of length $c$, you can go over all ordered sequences of $c+1$ vertices, and check whether all the edges in the corresponding path exist. On a RAM machine, this is an $O(n^{c+1})$ algorithm. When $c$ is constant, this is polynomial time.


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.