 Award ID(s):
 2120644
 NSFPAR ID:
 10410909
 Date Published:
 Journal Name:
 Advances in Combinatorics
 ISSN:
 25175599
 Page Range / eLocation ID:
 1 to 29
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

null (Ed.)Understanding the structure of minorfree 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 “smallcomplexity” graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minorfree 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 minorfree graph G=(V,E,w) of diameter D, and parameter ϵ, we construct a distribution D over dominating metric embeddings into treewidthOϵ(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 minorfree metrics; (2) the first approximation scheme for boundedcapacity vehicle routing in minorfree metrics; (3) the first efficient approximation scheme for boundedcapacity vehicle routing on bounded genus metrics. En route to the latter result, we design the first FPT approximation scheme for boundedcapacity vehicle routing on boundedtreewidth graphs (parameterized by the treewidth).more » « less

Abstract A graph is ‐
free if 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 
This is equivalent to:G  there are two disjoint sets of vertices, of sizes at least and , complete or anticomplete to each other.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.
The sparse linear conjecture holds for all almost‐bipartite graphs .
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.
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.

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 NPhard 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 Hfree graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NPhard and APXhard 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 polynomialtime 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 Hfree 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 APXhard in Hfree graphs, the problem admits a quasipolynomial 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

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 trianglefree, 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 nonnullhomotopic 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 nonnullhomotopic 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 nonnullhomotopic 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

For a graph F, a graph G is Ffree if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an Hcoloring 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 HColoring, which asks for the existence of an Hcoloring of an input graph G. In particular, we consider HColoring of Ffree 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 3Coloring of Ptfree graphs. We show that for every odd k ≥ 5 the CkColoring problem, even in the precoloringextension variant, can be solved in polynomial time in P9free graphs. On the other hand, we prove that the extension version of CkColoring is NPcomplete for Ffree graphs whenever some component of F is not a subgraph of a subdivided claw.more » « less