Polynomial Treedepth Bounds in Linear Colorings
- PDF / 1,994,880 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 6 Downloads / 181 Views
Polynomial Treedepth Bounds in Linear Colorings Jeremy Kun1 · Michael P. O’Brien2 · Marcin Pilipczuk3 · Blair D. Sullivan2 Received: 18 July 2018 / Accepted: 11 August 2020 © The Author(s) 2020
Abstract Low-treedepth colorings are an important tool for algorithms that exploit structure in classes of bounded expansion; they guarantee subgraphs that use few colors have bounded treedepth. These colorings have an implicit tradeoff between the total number of colors used and the treedepth bound, and prior empirical work suggests that the former dominates the run time of existing algorithms in practice. We introduce p-linear colorings as an alternative to the commonly used p-centered colorings. They can be efficiently computed in bounded expansion classes and use at most as many colors as p-centered colorings. Although a set of k < p colors from a p-centered coloring induces a subgraph of treedepth at most k, the same number of colors from a p-linear coloring may induce subgraphs of larger treedepth. We establish a polynomial upper bound on the treedepth in general graphs, and give tighter bounds in trees and interval graphs via constructive coloring algorithms. We also give a coNP-completeness reduction for recognizing p-linear colorings and discuss ways to overcome this limitation in practice. Keywords Linear colorings · p-centered colorings · Bounded expansion · Treedepth
A preliminary version of this paper, with weaker results, has been presented at WG 2018 [10]. * Marcin Pilipczuk [email protected] Jeremy Kun [email protected] Michael P. O’Brien [email protected] Blair D. Sullivan [email protected] 1
Google, Mountain View, CA, USA
2
North Carolina State University, Raleigh, NC, USA
3
University of Warsaw, Warsaw, Poland
13
Vol.:(0123456789)
Algorithmica
1 Introduction Algorithms for graph classes that exhibit bounded expansion structure [12–15] offer a promising framework for efficiently solving many NP-hard problems on real-world networks. The structural restrictions of bounded expansion, which allow for pockets of localized density in globally sparse graphs, are compatible with properties of many real-world networks such as clustering and heavy-tailed degree distributions. Moreover, multiple random graph models designed to mimic these properties have been proven to asymptotically almost surely belong to classes of bounded expansion [5]. From a theoretical perspective, one of the main strengths of the notion of bounded expansion is the abundance of numerous equivalent characterizations of classes of bounded expansion (see e.g. the textbook [12] of the lecture notes [18]); while working with them, one can choose the characterization most suitable for the application at hand. For algorithmic applications, one of the most versatile characterizations are low-treedepth colorings. A p-treedepth coloring of a graph G is a function 𝜙 ∶ V(G) → [k] for an integer k such that for every set I ⊆ [k] of size less than p, 𝜙−1 (I) induces a subgraph of G of treedepth at most |I|. (Treedepth is a structural pro
Data Loading...
