 Award ID(s):
 1841954
 NSFPAR ID:
 10217106
 Date Published:
 Journal Name:
 Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science
 Page Range / eLocation ID:
 589600
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

null (Ed.)The Capacitated Vehicle Routing problem is to find a minimumcost set of tours that collectively cover clients in a graph, such that each tour starts and ends at a specified depot and is subject to a capacity bound on the number of clients it can serve. In this paper, we present a polynomialtime approximation scheme (PTAS) for instances in which the input graph is planar and the capacity is bounded. Previously, only a quasipolynomialtime approximation scheme was known for these instances. To obtain this result, we show how to embed planar graphs into boundedtreewidth graphs while preserving, in expectation, the clienttoclient distances up to a small additive error proportional to client distances to the depot.more » « less

We show that, for any ∊ > 0, there is a deterministic embedding of edgeweighted planar graphs of diameter D into boundedtreewidth graphs. The embedding has additive error ∊D. We use this construction to obtain the first efficient bicriteria approximation schemes for weighted planar graphs addressing kCenter (equivalently dDomination), and a metric generalization of independent set, dindependent SET. The approximation schemes employ a metric generalization of Baker's framework that is based on our embedding result.more » « less

A hole in a graph $G$ is an induced cycle of length at least four, and an even hole is a hole of even length. The diamond is the graph obtained from the complete graph $K_4$ by removing an edge. A pyramid is a graph consisting of a vertex $a$ called the apex and a triangle $\{b_1, b_2, b_3\}$ called the base, and three paths $P_i$ from $a$ to $b_i$ for $1 \leq i \leq 3$, all of length at least one, such that for $i \neq j$, the only edge between $P_i \setminus \{a\}$ and $P_j \setminus \{a\}$ is $b_ib_j$, and at most one of $P_1$, $P_2$, and $P_3$ has length exactly one. For a family $\mathcal{H}$ of graphs, we say a graph $G$ is $\mathcal{H}$free if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$. Cameron, da Silva, Huang, and Vušković proved that (even hole, triangle)free graphs have treewidth at most five, which motivates studying the treewidth of evenholefree graphs of larger clique number. Sintiari and Trotignon provided a construction of (even hole, pyramid, $K_4$)free graphs of arbitrarily large treewidth. Here, we show that for every $t$, (even hole, pyramid, diamond, $K_t$)free graphs have bounded treewidth. The graphs constructed by Sintiari and Trotignon contain diamonds, so our result is sharp in the sense that it is false if we do not exclude diamonds. Our main result is in fact more general, that treewidth is bounded in graphs excluding certain wheels and threepathconfigurations, diamonds, and a fixed complete graph. The proof uses “noncrossing decompositions” methods similar to those in previous papers in this series. In previous papers, however, bounded degree was a necessary condition to prove bounded treewidth. The result of this paper is the first to use the method of “noncrossing decompositions” to prove bounded treewidth in a graph class of unbounded maximum degree.

null (Ed.)Graph compression or sparsification is a basic informationtheoretic and computational question. A major open problem in this research area is whether $(1+\epsilon)$approximate cutpreserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we initiate the study of a thresholded version of the problem: for a given parameter $c$, find a smaller graph, which we call \emph{connectivity$c$ mimicking network}, which preserves connectivity among $k$ terminals exactly up to the value of $c$. We show that connectivity$c$ mimicking networks of size $O(kc^4)$ exist and can be found in time $m(c\log n)^{O(c)}$. We also give a separate algorithm that constructs such graphs of size $k \cdot O(c)^{2c}$ in time $mc^{O(c)}\log^{O(1)}n$. These results lead to the first offline data structures for answering fully dynamic $c$edgeconnectivity queries for $c \ge 4$ in polylogarithmic time per query as well as more efficient algorithms for survivable network design on bounded treewidth graphs.more » « less

Gortz, Inge Li ; FarachColton, Martin ; Puglisi, Simon J. ; Herman, Grzegorz (Ed.)Computing the diameter of a graph, i.e. the largest distance, is a fundamental problem that is central in finegrained complexity. In undirected graphs, the Strong Exponential Time Hypothesis (SETH) yields a lower bound on the time vs. approximation tradeoff that is quite close to the upper bounds. In directed graphs, however, where only some of the upper bounds apply, much larger gaps remain. Since d(u,v) may not be the same as d(v,u), there are multiple ways to define the problem, the two most natural being the (oneway) diameter (max_(u,v) d(u,v)) and the roundtrip diameter (max_{u,v} d(u,v)+d(v,u)). In this paper we make progress on the outstanding open question for each of them.  We design the first algorithm for diameter in sparse directed graphs to achieve n^{1.5ε} time with an approximation factor better than 2. The new upper bound tradeoff makes the directed case appear more similar to the undirected case. Notably, this is the first algorithm for diameter in sparse graphs that benefits from fast matrix multiplication.  We design new hardness reductions separating roundtrip diameter from directed and undirected diameter. In particular, a 1.5approximation in subquadratic time would refute the AllNodes kCycle hypothesis, and any (2ε)approximation would imply a breakthrough algorithm for approximate 𝓁_∞ClosestPair. Notably, these are the first conditional lower bounds for diameter that are not based on SETH.more » « less