# Restricting longest path with 2-coloring to paths of at most constant length

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

### c-ZPath(cZP)

$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.

• 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.) – Raphael Jan 29 '14 at 20:35
• 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? – 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.