Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.