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. C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width

   https://doi.org/10.1007/s00453-021-00839-2  

   Da Lozzo, Giordano ; Eppstein, David ; Goodrich, Michael T. ; Gupta, Siddharth ( August 2021 , Algorithmica)

   Abstract For a clustered graph , i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that (1) the subgraph induced by each cluster is drawn in the interior of the corresponding disk, (2) each edge intersects any disk at most once, and (3) the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Feng, Cohen, and Eades, Planarity for clustered graphs , ESA’95], has only been recently settled [Fulek and Tóth, Atomic Embeddability, Clustered Planarity, and Thickenability , to appear at SODA’20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs . We show that the C-Planarity Testing problem admits a single-exponential single-parameter FPT (resp., XP) algorithm for embedded flat (resp., non-flat) clustered graphs, when parameterized by the carving-width of the dual graph of the input. These are the first FPT and XP algorithms for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and Tóth. In particular, our algorithm runs in quadratic time for flat instances of bounded treewidth and bounded face size. To further strengthen the relevance of this result, we show that an algorithm with running time O ( r ( n )) for flat instances whose underlying graph has pathwidth 1 would result in an algorithm with running time O ( r ( n )) for flat instances and with running time $$O(r(n^2) + n^2)$$ O ( r ( n 2 ) + n 2 ) for general, possibly non-flat, instances. 

   more » « less
3. Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems

   https://doi.org/10.1137/1.9781611975482.66  

   Eli Fox-Epstein, Eli Klein ( March 2019 , Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete Algorithms)

   We show that, for any ∊ > 0, there is a deterministic embedding of edge-weighted planar graphs of diameter D into bounded-treewidth graphs. The embedding has additive error ∊D. We use this construction to obtain the first efficient bicriteria approximation schemes for weighted planar graphs addressing k-Center (equivalently d-Domination), and a metric generalization of independent set, d-independent SET. The approximation schemes employ a metric generalization of Baker's framework that is based on our embedding result. 

   more » « less
4. Computing Diameter+2 in Truly-Subquadratic Time for Unit-Disk Graphs

   https://doi.org/10.4230/LIPIcs.SoCG.2024.38  

   Chang, Hsien-Chih ; Gao, Jie ; Le, Hung ( January 2024 , Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang ; Phillips, Jeff M (Ed.)

   Finding the diameter of a graph in general cannot be done in truly subquadratic assuming the Strong Exponential Time Hypothesis (SETH), even when the underlying graph is unweighted and sparse. When restricting to concrete classes of graphs and assuming SETH, planar graphs and minor-free graphs admit truly subquadratic algorithms, while geometric intersection graphs of unit balls, congruent equilateral triangles, and unit segments do not. Unit-disk graphs is one of the major open cases where the complexity of diameter computation remains unknown. More generally, it is conjectured that a truly subquadratic time algorithm exists for pseudo-disk graphs where each pair of objects has at most two intersections on the boundary. In this paper, we show a truly-subquadratic algorithm of running time O^~(n^{2-1/18}), for finding the diameter in a unit-disk graph, whose output differs from the optimal solution by at most 2. This is the first algorithm that provides an additive guarantee in distortion, independent of the size or the diameter of the graph. Our algorithm requires two important technical elements. First, we show that for the intersection graph of pseudo-disks, the graph VC-dimension - either of k-hop balls or the distance encoding vectors - is 4. This contrasts to the VC dimension of the pseudo-disks themselves as geometric ranges (which is known to be 3). Second, we introduce a clique-based r-clustering for geometric intersection graphs, which is an analog of the r-division construction for planar graphs. We also showcase the new techniques by establishing new results for distance oracles for unit-disk graphs with subquadratic storage and O(1) query time. The results naturally extend to unit L₁ or L_∞-disks and fat pseudo-disks of similar size. Last, if the pseudo-disks additionally have bounded ply, we have a truly subquadratic algorithm to find the exact diameter. 

   more » « less
5. Model Checking on Interpretations of Classes of Bounded Local Cliquewidth

   https://doi.org/10.1145/3531130.3533367  

   Bonnet, Édouard ; Dreier, Jan ; Gajarský, Jakub ; Kreutzer, Stephan ; Mählmann, Nikolas ; Simon, Pierre ; Toruńczyk, Szymon ( August 2022 , LICS '22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science)

   An interpretation is an operation that maps an input graph to an output graph by redefining its edge relation using a first-order formula. This rich framework includes operations such as taking the complement or a fixed power of a graph as (very) special cases. We prove that there is an FPT algorithm for the first-order model checking problem on classes of graphs which are first-order interpretable in classes of graphs with bounded local cliquewidth. Notably, this includes interpretations of planar graphs, and of classes of bounded genus in general. To obtain this result we develop a new tool which works in a very general setting of NIP classes and which we believe can be an important ingredient in obtaining similar results in the future. 

   more » « less