Complexity of “half cycle”

Question

I'm working on the following problem:

HALFCYCLE (HALFC):

Input:

A directed graph $G = (V,E)$.

Output:

Whether the longest cycle in $G$ has length $ \lfloor |V|/2 \rfloor$.

Prove that if $\mathsf{PH} \ne \mathsf{coNP}$ then HALFCYCLE is not NP-complete.

I have no idea how to solve this implication.

Answer 1

Show that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$, and so the polynomial hierarchy collapses to NP.

How do you prove that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$? There are two options:

1. Show that coSAT reduces to HALFCYCLE. Since HALFCYCLE is NP-complete, in particular it is in NP, and so coSAT is in NP, implying NP=coNP.
2. Show that HALFCYCLE is in coNP. Since HALFCYCLE is NP-hard, in particular SAT reduces to HALFCYCLE, and so SAT is in coNP, implying NP=coNP.

(You can replace SAT with any NP-hard problem, and coSAT with any coNP-hard problem.)

Good luck!