Question

Let G represent an undirected graph. Also let

$\mathit{S}\mathit{P}\mathit{A}\mathit{T}\mathit{H}\mathbf{=}\mathbf{\{}\mathbf{́}\mathit{a}\mathit{G}\mathbf{,}\mathit{a}\mathbf{,}\mathit{b}\mathbf{,}\mathit{k}\mathbf{~}\mathit{n}\mathbf{\mid }\mathit{G}\mathbf{ }\mathit{c}\mathit{o}\mathit{n}\mathit{t}\mathit{a}\mathit{i}\mathit{n}\mathit{s}\mathbf{ }\mathit{a}\mathbf{ }\mathit{s}\mathit{i}\mathit{m}\mathit{p}\mathit{l}\mathit{e}\mathbf{ }\mathit{p}\mathit{a}\mathit{t}\mathit{h}\mathbf{ }\mathit{o}\mathit{f}\mathbf{ }\mathit{l}\mathit{e}\mathit{n}\mathit{g}\mathit{t}\mathit{h}\mathbf{ }\mathit{a}\mathit{t}\mathit{m}\mathit{o}\mathit{s}\mathit{t}\mathbf{ }\mathit{k}\mathbf{ }\mathit{f}\mathit{r}\mathit{o}\mathit{m}\mathbf{ }\mathit{a}\mathbf{ }\mathit{t}\mathit{o}\mathbf{ }\mathit{b}\mathbf{\}}\mathbf{,}\mathit{a}\mathit{n}\mathit{d}$

$\mathit{L}\mathit{P}\mathit{A}\mathit{T}\mathit{H}\mathbf{=}\mathbf{\{}\mathbf{́}\mathit{a}\mathit{G}\mathbf{,}\mathit{a}\mathbf{,}\mathit{b}\mathbf{,}\mathit{k}\mathbf{~}\mathit{n}\mathbf{\mid }\mathit{G}\mathbf{ }\mathit{c}\mathit{o}\mathit{n}\mathit{t}\mathit{a}\mathit{i}\mathit{n}\mathit{s}\mathbf{ }\mathit{a}\mathbf{ }\mathit{s}\mathit{i}\mathit{m}\mathit{p}\mathit{l}\mathit{e}\mathbf{ }\mathit{p}\mathit{a}\mathit{t}\mathit{h}\mathbf{ }\mathit{o}\mathit{f}\mathbf{ }\mathit{l}\mathit{e}\mathit{n}\mathit{g}\mathit{t}\mathit{h}\mathbf{ }\mathit{a}\mathit{t}\mathit{l}\mathit{e}\mathit{a}\mathit{s}\mathit{t}\mathbf{ }\mathit{k}\mathbf{ }\mathit{f}\mathit{r}\mathit{o}\mathit{m}\mathbf{ }\mathit{a}\mathbf{ }\mathit{t}\mathit{o}\mathbf{ }\mathit{b}\mathbf{\}}\mathbf{.}$

a) Show that SPATH? P.

b) Show that LPATH is NP-complete.

Short answer

a)$SPATH+1\in P.$

b) The LPATH is NP-complete.

Step-by-step solution

To construct a DTM M to decide SPATH

a)

P is class of languages that are decidable in polynomial time on a deterministic single $-$ tape Turing machine. We have to construct an deterministic Turing machine $(D T M)$ to decide SPATH in polynomial time.

Let M be the DTM to decide SPATH in polynomial time.

The algorithm of M is as follows:

$M=\text{'}\text{'}on input \$⟨G,a,b,k⟩\$where m-node graph G has nodes a and b:$

Place a mark "o" on node a.

for each$ifrom0tom:$

If an $edge\left(s,t\right)$is found connecting s marked as "$i$" to an unmarked node$t$ , mark node$t$ with "$i+1^{\text{'}\text{'}}\$.$

If$b$ is marked with a value at most$k$ , accept. Otherwise reject.

This algorithm is similar to PATH algorithm. Here we additionally need to keep the track of length of the shortest paths discovered. That will be done in polynomial time

$\$O\left(\left|V\right|+\left|E\right|\right)\$.$

Hence, we constructed a DTM M to decide SPATH in polynomial time.

Therefore,$SPATH+1\in P\$.$

Step 2:To Explain LPATH language

(b)

NP - complete: A language B is NP-complete if it satisfies two conditions.

$\$B\$isinNP$and

Every A in NP is polynomial time reducible to B.

To show$LPATH is NP-complete, we need show \$LPATH\in NP\$ and \$ UHAMPATH{⩽}_{P}LPATH$

$LPATH\in NP:$We know that "NP is the class of languages that have polynomial time verifies.

We construct a verifies$\vee \$for\$LPATH$as follows:

:$V=\$\text{'}\text{'}on input\$⟨G,a,b,k,c⟩\$,where c is a path$

Check is a non - repeated sequence of nodes in G

Check the first term of c is a and last is b.

Check the length of c is larger than or equal to k.

If c satisfies the conditions, accept.

Otherwise, reject

This verifier v can finish in $O\left(ICI\right)$where $\left|c\right|$is the length of $c$.

So,$LPATH\in NP.$

Therefore, the LPATH is NP-complete.