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:

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

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? 

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

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

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

h)    Give the result of g).