Languages

The Longest Simple Cycle (LSC) problem determines the longest path <v₀, v₁, ..., v_k> of a directed graph such that v₀=v_k and <v₁, ..., v_k> are distinct.

a)    For the Longest Simple Cycle (LSC) problem, give the language LSC_L:

    LSC_L = {<G> :

G=(V, E) is an directed graph }

b)    Define the instance of LSC_L for the graph at right.

V={1,2,3,4}

E={(1,2),(2,4),(4,4),(4,3),(3,2),(3,1)}

G=<V,E>

c)    LSC_L's I - is the set of all problem instances of the LSC_L. Define a problem instance for the graph at right. (G)

d)    LSC_L's S - is the set of all LSC_L solutions. What is S? 

{<1,2,4,3>, <2,4,3,1>, <4,3,1,2>, <3,1,2,4>}

e)    For the Longest Simple Cycle (LSC) decision problem, give the language LSC_LD:

LSC_LD = { <G, k>

G=(V, E) is an directed graph
k ≥ 0 an integer and there exists a simple cycle in G consisting of at least k edges }

f)    Define the instance of LSC_LD for the graph at right and a problem instance.

V={1,2,3,4}

E={(1,2),(2,4),(4,4),(4,3),(3,2),(3,1)}

G=<V,E>

g)    Define a problem instance of LSC_LD for the graph at right.  (G, 4)

h)    Give the result of g).   1