arXiv preprint ·
An Arboricity-Sensitive Algorithm for the $K_r-e$-Free Graph Sandwich Problem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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+α(G_2)^{r-3}m_2)$ time and space, where $m_2=|E(G_2)|$ and $α(G_2)$ is the arboricity of $G_2$. In particular, the diamond-free case takes $O(n+α(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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Witness Set in Weak Visibility Polygons is Polynomial-Time Solvable
Local Representatives and Shortest Completions for Next-to-Shortest Paths in Directed Graphs
FPT Isomorphism Test for $F$-Free Tournaments
Counting and Covering in Nearest-Neighbour Representations of Boolean Functions
On the Offline Version of the Time-Optimal k-Server Problem
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.