World's most popular travel blog for travel bloggers.

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

, ,
Problem Detail:

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.

###### Answered By : Yuval Filmus

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.