More Like this

1. On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs

   Cohen-Addad, Vincent ; Filtser, Arnold ; Klein, Philip N ; Le, Hung ( October 2020 , Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science)

   null (Ed.)

   Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a “small-complexity” graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minor-free metrics: 1) Construction of a light subset spanner. Given a subset of vertices called terminals, and ϵ, in polynomial time we construct a sub graph that preserves all pairwise distances between terminals up to a multiplicative 1+ϵ factor, of total weight at most Oϵ(1) times the weight of the minimal Steiner tree spanning the terminals. 2) Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion ϵD. Namely, given a minor-free graph G=(V,E,w) of diameter D, and parameter ϵ, we construct a distribution D over dominating metric embeddings into treewidth-Oϵ(log n) graphs such that ∀u,v∈V, Ef∼D[dH(f(u),f(v))]≤dG(u,v)+ϵD. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minor-free metrics; (2) the first approximation scheme for bounded-capacity vehicle routing in minor-free metrics; (3) the first efficient approximation scheme for bounded-capacity vehicle routing on bounded genus metrics. En route to the latter result, we design the first FPT approximation scheme for bounded-capacity vehicle routing on bounded-treewidth graphs (parameterized by the treewidth). 

   more » « less
2. Pure pairs. III. Sparse graphs with no polynomial‐sized anticomplete pairs

   https://doi.org/10.1002/jgt.22556  

   Chudnovsky, Maria ; Fox, Jacob ; Scott, Alex ; Seymour, Paul ; Spirkl, Sophie ( March 2020 , Journal of Graph Theory)

   A graph is ‐freeif it has no induced subgraph isomorphic to , and |G| denotes the number of vertices of . A conjecture of Conlon, Sudakov and the second author asserts that:

   For every graph , there exists such that in every ‐free graph with |G| there are two disjoint sets of vertices, of sizes at least and , complete or anticomplete to each other.

   This is equivalent to:

   The “sparse linear conjecture”: For every graph , there exists such that in every ‐free graph with , either some vertex has degree at least , or there are two disjoint sets of vertices, of sizes at least and , anticomplete to each other.

   We prove a number of partial results toward the sparse linear conjecture. In particular, we prove it holds for a large class of graphs , and we prove that something like it holds for all graphs . More exactly, say is “almost‐bipartite” if is triangle‐free and can be partitioned into a stable set and a set inducing a graph of maximum degree at most one. (This includes all graphs that arise from another graph by subdividing every edge at least once.) Our main result is:

   The sparse linear conjecture holds for all almost‐bipartite graphs .

   (It remains open when is the triangle .) There is also a stronger theorem:

   For every almost‐bipartite graph , there exist such that for every graph with and maximum degree less than , and for every with , either contains induced copies of , or there are two disjoint sets with and , and with at most edges between them.

   We also prove some variations on the sparse linear conjecture, such as:

   For every graph , there exists such that in every ‐free graph with vertices, either some vertex has degree at least , or there are two disjoint sets of vertices with , anticomplete to each other.

    

   more » « less
3. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs

   https://doi.org/10.1137/1.9781611975994.139  

   Chudnovsky, Maria. ; Pillipczuk, Marcin. ; Pillipczuk, Mihal ; and Thomasse, Stephan. ( April 2020 , Proceedings of the annual ACMSIAM symposium on discrete algorithms)

   In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In H-free graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs H such as P5, P6, the claw, or the fork. We prove that for every such “possibly tractable” graph H there exists an algorithm that, given an H-free graph G and an accuracy parameter ε > 0, finds an independent set in G of cardinality within a factor of (1 – ε) of the optimum in time exponential in a polynomial of log | V(G) | and ε−1. That is, we show that for every graph H for which Maximum Independent Set is not known to be APX-hard in H-free graphs, the problem admits a quasi-polynomial time approximation scheme in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set. 

   more » « less
4. Hyperbolic families and coloring graphs on surfaces

   https://doi.org/https://doi.org/10.1090/btran/26  

   Postle, Luke ; Thomas, Robin ( December 2018 , Transactions of the American Mathematical Society. Series B)

   We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $ G$ be a graph embedded in a fixed surface $ \Sigma $ of genus $ g$ and let $ L=(L(v):v\in V(G))$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $ G$ is triangle-free, or each list has size at least three and $ G$ has no cycle of length four or less. An $ L$-coloring of $ G$ is a mapping $ \phi $ with domain $ V(G)$ such that $ \phi (v)\in L(v)$ for every $ v\in V(G)$ and $ \phi (v)\ne \phi (u)$ for every pair of adjacent vertices $ u,v\in V(G)$. We prove if every non-null-homotopic cycle in $ G$ has length $ \Omega (\log g)$, then $ G$ has an $ L$-coloring, if $ G$ does not have an $ L$-coloring, but every proper subgraph does (``$ L$-critical graph''), then $ \vert V(G)\vert=O(g)$, if every non-null-homotopic cycle in $ G$ has length $ \Omega (g)$, and a set $ X\subseteq V(G)$ of vertices that are pairwise at distance $ \Omega (1)$ is precolored from the corresponding lists, then the precoloring extends to an $ L$-coloring of $ G$, if every non-null-homotopic cycle in $ G$ has length $ \Omega (g)$, and the graph $ G$ is allowed to have crossings, but every two crossings are at distance $ \Omega (1)$, then $ G$ has an $ L$-coloring, if $ G$ has at least one $ L$-coloring, then it has at least $ 2^{\Omega (\vert V(G)\vert)}$ distinct $ L$-colorings. We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $ L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities. 

   more » « less
5. Complexity of Ck-Coloring in Hereditary Classes of Graphs

   Chudnovsky, M. ; Huang, S. ; Rzazewski, P. ; Spirkl, S. ; and Zhong, M. ( September 2019 , European Symposium on Algorithms)

   For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an H-coloring of G is a mapping f : V (G) → V (H) such that for every edge uv ∈ E(G) it holds that f(u)f(v) ∈ E(H). We are interested in the complexity of the problem H-Coloring, which asks for the existence of an H-coloring of an input graph G. In particular, we consider H-Coloring of F-free graphs, where F is a fixed graph and H is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-Coloring of Pt-free graphs. We show that for every odd k ≥ 5 the Ck-Coloring problem, even in the precoloring-extension variant, can be solved in polynomial time in P9-free graphs. On the other hand, we prove that the extension version of Ck-Coloring is NP-complete for F-free graphs whenever some component of F is not a subgraph of a subdivided claw. 

   more » « less