Listing maximal H-free subgraphs

Given two graphs G and H, where H is the forbidden subgraph or pattern, G is called H-free if no vertex subset V′⊆V(G) induces a subgraph G[V′] isomorphic to H. In the edge-induced version of the notion, G is called H-free if no edge subset E′⊆E(G) induces a subgraph G[E′] isomorphic to H. The goal is to list all the inclusion-maximal subgraphs of G that are H-free, according to both the edge-induced and vertex-induced versions. Apart from its theoretical interest, the problem has application in data modeling, as it corresponds to data cleaning/repairing tasks, where the entire dataset is inconsistent with respect to the constraints given in H, and maximal consistent portions are sought. Several output-sensitive algorithms for the vertex-induced version are presented, which depend on the constraints on H and on G. As for the edge-induced version, we show how output-sensitive algorithms are possible for specific cases, but an efficient general technique is unlikely to exist as simply certifying a solution can be co-NP-complete.