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] |