0
$\begingroup$

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.

1 Answers 1

0

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}$.

  • 0
    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}$.2011-02-16