Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G$ represent an undirected graph, let $a$ and $b$ represent vertices and let $k$ represent a non-negative integer.

I have two languages:

$L_1 = \left \{ \left \langle G, a, b, k \right \rangle \mid G \text{ contains a path of at most } k \text{ from } a \text{ to } b \right \}$, and
$L_2 = \left \{ \left \langle G, a, b, k \right \rangle \mid G \text{ contains a path of at least } k \text{ from } a \text{ to } b \right \}.$

I want to show that $L_1$ is in P.

I have thought that I could show it in $\text{Satisfiability}$, but I am unsure of what I am doing: $$(a \vee \lnot b )\wedge (b \vee \lnot a)\wedge(k \vee \lnot a) \wedge (k \vee \lnot b)\wedge (a \vee \lnot k) \wedge (b \vee \lnot k)$$
If someone could walk me through this, that would be great, because I don't think I can use $\text{2-COL}$ to $\text{2-SAT reducibility}$ on this instance of $G$.

Secondly, I want to show that $L_2$ is NP-complete.
Now I understand that I can use the fact that $\text{Hamiltonian-Path}$ is NP-complete, but any further guidance would be gratefully appreciated.

share|cite|improve this question
up vote 0 down vote accepted

In order to show that a problem is in $\mathbf{P}$, you need to provide a polynomial-time algorithm for it. Check out the shortest path problem.

It's not clear what you mean by "a path of at least $k$" - it seems that $(G,a,b,k) \in L_2$ if $a,b$ are in the same connected component of $G$ and $(G,a,b,k-1) \notin L_1$, so that $L_2$ is also in $\mathbf{P}$.

share|cite|improve this answer
Sorry, I had my mind in a twist, I think I can use $\text{Dijikstra's algorithm}$ for proving $L_1$ is in P. As for $L_2$, I can do a reduction from my aforementioned $\text{Hamiltonian Path}$. – braedy. Feb 16 '11 at 1:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.