The P4-sparse Graph Sandwich Problem

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