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
no edge’s endpoint vertices have the same color and
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.