# Examples of $\Sigma_2^p$ complete problems?

I need a list of $\Sigma_2^p$ complete languages. There are two such problems listed in the Complexity Zoo, namely:

• Minimum equivalent DNF. Given a DNF formula F and integer k, is there a DNF formula equivalent to F with k or fewer occurences of literals?
• Shortest implicant. Given a formula F and integer k, is there a conjunction of k or fewer literals that implies F?

Another basic $\Sigma_2^p$ complete problem:

• $\Sigma_i \text{SAT}$. Given a quantified boolean formula $\varphi$ of the form $\varphi = \exists \vec{u} \forall \vec{v}\, \phi(\vec{u}, \vec{v})$, is $\varphi$ valid?

However, I am hopefully looking for a problem which makes use of graphs (e.g. a clique related problem).

• Take a look at this compendium: ovid.cs.depaul.edu/documents/phcom.pdf Jun 30 '14 at 15:51
• This looks extremely useful. Thanks a lot! Jun 30 '14 at 15:53
• @HuckBennett: good survey! Why don't you turn it into an answer? Jun 30 '14 at 16:02

See David Defossez, Complexity of clique-coloring odd-hole-free graphs. J. Graph Theory 62, 2 (October 2009), 139-156, and some recent improvements (2013): Hélio B. Macêdo Filho, Raphael C. S. Machado, Celina M. H. de Figueiredo, Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3 (the problem is still $\Sigma_2^p$-complete for weakly chordal graphs, and for perfect graphs having cliques of size at least 3).