Skip to main content
Computer Science

Return to Question

added 185 characters in body
Source Link
Dee
Dee
  • 141
  • 7

We define the following languages:

LPATH = {<G, a, b, k>|G is an undirected graph that contains a simple path of length at least k from a to b}.

UNIQUE-PATH = {<G, a, b>| G is an undirected graph. The longest simple path from a to b in G is unique}.

Assuming LPATH ∈ P, prove that UNIQUE-PATH ∈ P.

Any idea I had resulted in me getting stuck at the part where I needed to differentiate if an edge was needed to the path or not (so I could delete it and see if the path was unique). I would appreciate any ideas you might have regarding this one.

We define the following languages:

LPATH = {<G, a, b, k>|G is an undirected graph that contains a simple path of length at least k from a to b}.

UNIQUE-PATH = {<G, a, b>| G is an undirected graph. The longest simple path from a to b in G is unique}.

Assuming LPATH ∈ P, prove that UNIQUE-PATH ∈ P.

I would appreciate any ideas you might have regarding this one.

We define the following languages:

LPATH = {<G, a, b, k>|G is an undirected graph that contains a simple path of length at least k from a to b}.

UNIQUE-PATH = {<G, a, b>| G is an undirected graph. The longest simple path from a to b in G is unique}.

Assuming LPATH ∈ P, prove that UNIQUE-PATH ∈ P.

Any idea I had resulted in me getting stuck at the part where I needed to differentiate if an edge was needed to the path or not (so I could delete it and see if the path was unique). I would appreciate any ideas you might have regarding this one.

Source Link
Dee
Dee
  • 141
  • 7

UNIQUE-PATH in P assuming LPATH is in P

We define the following languages:

LPATH = {<G, a, b, k>|G is an undirected graph that contains a simple path of length at least k from a to b}.

UNIQUE-PATH = {<G, a, b>| G is an undirected graph. The longest simple path from a to b in G is unique}.

Assuming LPATH ∈ P, prove that UNIQUE-PATH ∈ P.

I would appreciate any ideas you might have regarding this one.