World's most popular travel blog for travel bloggers.

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

, , No Comments
Problem Detail: 

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.

Asked By : Tolon
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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback