Consider the following language:

ULONGER$-$CYCLE $=\{$G$,$ k$|$ G is a graph, k an integer, and G has a simple cycle of length $>$ k$\}.$

Question $21(1$ point$)$

To show that ULONGER$-$CYCLE is NP$-$hard, it suffices to show that

X is polynomially many$-$one reducible to ULONGER$-$CYCLE for some NP$-$complete X$.$

Question $21$ options:

True

False

Question $22(1$ point$)$

To show that ULONGER$-$CYCLE is NP$-$hard, it suffices to show that

ULONGER$-$CYCLE is polynomially many$-$one reducible to X for some NP$-$complete X$.$

Question $22$ options:

True

False

Question $23(2$ points$)$

Consider the following list of NP$-$complete languages. Select the language that would be most helpful in proving that ULONGER$-$CYCLE is NP$-$hard.

Recall that:

A clique C in a graph is a subset of the vertices such that every

two vertices in C are adjacent.

A Hamiltonian cycle in a graph G is a cycle that goes through each

vertex exactly once.

An independent set I in a graph is a subset of the vertices such

that no two vertices in I are adjacent.

Question $23$ options:

CLIQUE $=\{$G$,$ k$|$ G is a graph, k is an integer, and G has a clique of size k$\}.$

INDEPENDENT$-$SET $=\{$G$,$ k$|$ G is a graph, k is an integer, and G has an independent set of size k$\}.$

SAT $=\{\backslash$phi $|\backslash$phi is a satisfiable boolean formula$\}$

UHAMCYCLE $=\{$G$|$ G is a graph with a Hamiltonian cycle $\}.$

Question $24(4$ points$)$

Describe a reduction that shows that ULONGER$-$CYCLE is NP$-$hard. You must reduce to or from the language selected in the last question. $($You do not have to show that your reduction is correct.$)$

Question $24$ options:

Question $25(2$ points$)$

Is ULONGER$-$CYCLE NP$-$complete? Briefly explain your answer.