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

Min Chih Lin; Nat\'an Vekselman

En palabras de los autores

For a fixed integer $r \geq 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 + α (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.

Resultado principalEl resumen no menciona limitaciones.

An Arboricity-Sensitive Algorithm for the Kr​−e-Free Graph Sandwich Problem

En palabras de los autores

Más de Algoritmos y complejidad ese día

Smoothed Analysis of Inconsistent A*

Hardness of Online Directed Steiner Network

Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams

Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time

Parameter-Free Triangle Counting

An Arboricity-Sensitive Algorithm for the $K_{r} - e$ -Free Graph Sandwich Problem