An Arboricity-Sensitive Algorithm for the $K_r-e$-Free Graph Sandwich Problem

Abstract

For a fixed integer $r\ge 4$, the $K_r-e$-free graph sandwich problem asks whether, given graphs $G_1\subseteq G_2$ on the same vertex set, there is an induced-$K_r-e$-free graph $H$ between them. We give a deterministic algorithm taking $O(n+\alpha (G_2{)}^{r-3}{m}_2)$ time and space, where $m_2=|E(G_2)|$ and $\alpha (G_2)$ is the arboricity of $G_2$. In particular, the diamond-free case takes $O(n+\alpha (G_2)m_2)$ time. This improves the direct $O(n^r{m}_2)$ implementation of the previously known forced-edge closure. Our implementation maintains components of common neighborhoods indexed by $(r-3)$-cliques. A filtered frontier supports their merges within the clique-listing bound, while completion events avoid repeatedly searching for affected cliques. On feasible instances the output is contained in every feasible sandwich, independently of processing order. Applying the closure to $(G,K_n)$ gives an $O(n^{r-1})$-time bound for partitioned and nonpartitioned probe $K_r-e$-free recognition, improving the $O(n^{r+2})$ bound obtained from the direct sandwich closure. We also describe a direct static recognizer based on the same local characterization.

10 pages. Expanded implementation details and complexity justification; clarified the word-RAM model, clique-event processing, and the discussion of previous probe recognition algorithms. No change to the main results