Certifying Induced Subgraphs in Large Graphs

Abstract

We introduce I/O-efficient certifying algorithms for the recognition of bipartite, split, threshold, bipartite chain, and trivially perfect graphs.
When the input graph is a member of the respective class, the certifying algorithm returns a certificate that characterizes this class.
Otherwise, it returns a forbidden induced subgraph as a certificate for non-membership.
On a graph with $n$ vertices and $m$ edges, our algorithms take $\mathcal O(\text{sort}(n + m))$ I/Os in the worst case for split, threshold and trivially perfect graphs.
In the same complexity bipartite and bipartite chain graphs can be certified with high probability.
We provide implementations and an experimental evaluation for split and threshold graphs.