| Title: | The Graph Sandwich Problem for a coNP Property |
| Authors: | Marcus Schaefer |
| Abstract: | If F ⊂ G ⊂ F' we say that the graph G is sandwiched between graphs F and F'. The graph sandwich problem consists in finding such a graph G in a particular class or with a special property. We show that there is a coNP-complete graph property for which the graph sandwich problem is complete for the second level of the polynomial time hierarchy. |
| Full Paper: | [ps, pdf] |