Min-Chih Lin

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

For a fixed integer $r\geq4$, 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)$...