The P4-sparse Graph Sandwich Problem

The P 4 -sparse Graph Sandwich Problem asks, given two graphs G 1 = ( V , E 1 ) and G 2 = ( V , E 2 ) , whether there exists a graph G = ( V , E ) such that E 1 ⊆ E ⊆ E 2 and G is P 4 -sparse. In this paper we present a polynomial-time algorithm for solving the Graph Sandwich Problem for P 4 -sparse graphs.