K 2 , 3 K_{2,3} -induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two

Dibyayan Chakraborty · 2025

Read K 2 , 3 K_{2,3} -induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two by Dibyayan Chakraborty (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-00798.txt.

Introduction

Dibyayan Chakraborty gives a new proof that a certain family of graphs is, in a precise sense, close to very simple graphs. The family excludes one pattern, the graph K2,3, as an induced minor, a pattern ruled out under vertex deletions and edge contractions only. The theorem says every such graph can be matched to a graph of tree-width at most two by a quasi-isometry that distorts distances only by an additive amount.

The proof comes with an algorithm that builds the simple partner graph in time proportional to the product of vertices and edges. For a well-behaved subclass it runs in linear time. As a payoff, the diameter of those graphs can be approximated within a constant factor in truly sub-quadratic time. That beats known hardness barriers for even narrower graph classes.

Catalog record

CREATORDibyayan Chakraborty
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00798

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

K 2 , 3 K_{2,3} -induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two Dibyayan Chakraborty Abstract A graph H H is an induced minor of a graph G G if H H can be obtained from G G by a sequence of edge contractions and vertex deletions. Otherwise, G G is H H -induced minor-free . In this paper, we provide a different proof of the fact that K 2 , 3 K_{2,3} -induced minor-free graphs admit a quasi-isometry with additive distortion to graphs with tree-width at most two. Our proof yields a O ⁡ ( n ​ m ) O(nm) -time algorithm which takes as input a K 2 , 3 K_{2,3} -induced minor-free graph with n n vertices and m m edges, and outputs a tree-width two graph H H with the desired additive distortion. For universally signable graphs, a subclass of K 2 , 3 K_{2,3} -induced minor-free graphs, the time complexity of our algorithm is linear. As a consequence, we obtain a truly sub-quadratic time additive constant factor approximation algorithm to compute the diameter of a universally signable graph. In contrast, assuming the Strong Exponential Time Hypothesis ( SETH ), the diameter of split graphs (a very restricted class of universally signable graphs), cannot be computed in truly sub-quadratic time [Borassi et al. (ENTCS, 2016)]. 1 Introduction When is a graph quasi-isometric ( Definition 1 ) to a much simpler host graph? This question is central to coarse graph theory [ 25 ] . When the host graphs are restricted to the class of graphs with bounded tree-width , remarkably, the answer is provided by Nguyen, Scott & Seymour [ 29 ] and independently by Hickingbotham [ 27 ] . Specifically, they proved the following: Theorem 1 ( [ 29 , 27 ] ) . A graph is quasi-isometric to a graph with bounded tree-width if and only if it has a tree-decomposition where each bag consists of a bounded number of balls of bounded diameter. When quasi-isometric maps with only additive distortions ( Definition 2 ) are allowed, the situation is much less understood. Brandstädt et al. [ 6 ] proved that chordal graphs (i.e., graphs without any induced cycle of length greater than three) admit a quasi-isometry to trees with additive distortion at most 2 . This result has been later generalized to k -chordal graphs [ 13 ] , and more generally to graphs of bounded treelength [ 21 ] . Berger & Seymour [ 3 ] characterized graphs admitting quasi-isometry with additive distortion to trees. See [ 22 ] for a comprehensive overview of graphs admitting a quasi-isometry with additive distortion to trees. When does a graph class admit quasi-isometry with additive distortion to graphs with tree-width at most two? The above question also relates to the following conjecture of Nguyen, Scott & Seymour [ 29 ] . Conjecture 2 ( [ 29 ] ) . There is a constant k , such that if a graph G admits a quasi-isometry to a graph of tree-width at most two, then G admits a quasi-isometry with additive distortion to a graph with tree-width at most k . In this paper, we consider the class of K_{2,3} -induced minor-free graphs. A graph H is an induced minor of a graph G if H can be obtained from G by a sequence of edge contractions and vertex deletions. Otherwise, G is H -induced minor-free . The class of K_{2,3} -induced minor-free graphs have been studied extensively in structural graph theory [ 18 , 19 ] . K_{2,3} -induced minor-free graphs generalize many popular graph classes. Examples include outerplanar graphs, circular-arc graphs [ 23 ] , chordal graphs, universally signable graph [ 17 ] etc. Coarse generalizations of K_{2,3} -induced minor-free graphs have been studied [ 12 ] . A recent result of Albrechtsen et al. [ 2 ] implies that K_{2,3} -induced minor-free graphs are quasi-isometric to graphs with tree-width at most two. Combining results of Fujiwara & Papasoglu [ 24 ] and Nguyen, Seymour & Scott [ 29 ] prove that Conjecture 2 holds for K_{2,3} -induced minor-free graphs 1 1 1 We thank Robert Hickingbotham for informing us of this connection. . In this paper, we provide a different constructive proof for the above. Specifically, we prove the following theorem. Theorem 3 . There is a constant c , and an O(nm) -time algorithm that takes as input a K_{2,3} -induced minor-free graph G with n vertices and m edges, and outputs a graph H with V(G)=V(H) , tree-width at most two, and \left|d_{G}\left(u,v\right)-d_{H}\left(u,v\right)\right|\leq c for any u,v\in V(G) . In the above theorem, d_{G}\left(.,.\right) and d_{H}\left(.,.\right) denote the standard graph metric in G and H , respectively. The class of universally-signable graphs [ 17 ] is an important subclass of K_{2,3} -induced minor-free graphs. A graph G is universally-signable if for all choices of vector \gamma , there exists a subset F of the edge set of G such that |F\cap H|\equiv\gamma_{H}(\mod 2) , for all holes H of G . A hole of G is an induced subgraph of G isomorphic to C_{k} with k\geq 4 . A characterization of universally-signable graphs via forbidden induced subgraphs states that a graph is universally signable if and only if it has none of the four Truemper configurations as induced subgraphs. Conforti et al. [ 17 ] proved that a graph is universally-signable if and only if it is a clique or a hole (i.e. an induced cycle of length more than three) or it has a clique cutset . This result generalises a famous theorem of Dirac [ 20 ] (on chordal graphs ) and is one of the earliest instance of decomposition theorems for hereditary graph classes, a technique which were instrumental in the resolution of the Strong Perfect Graph Conjecture [ 16 ] . When the input graphs are restricted to universally signable graphs, a subclass of K_{2,3} -induced minor-free graph, our algorithm runs in linear time, which has the following consequence. The diameter of a graph is the length of a longest isometric path (i.e. a path of minimum length between the end-vertices) between two of its vertices. Given an undirected graph G , Diameter is the algorithmic task of computing the diameter of G . Diameter is a fundamental problem with countless applications in computer science. The fastest combinatorial algorithm for Diameter has a running time of O(nm) in m -edge, n -vertex graphs. Surprisingly, Roditty and Vassilevska Williams [ 30 ] proved that a truly sub-quadratic \left(\frac{3}{2}-\epsilon\right) -approximation algorithm for Diameter would falsify the Strong Exponential Time Hypothesis [ 28 ] . This motivated researchers to study the approximability of Diameter on special graph classes. However, Borassi, Crescenzi & Habib [ 4 ] proved that assuming SETH, diameter cannot be computed optimally in truly sub-quadratic time even on split graphs, i.e. graphs whose vertex set can be partitioned into a clique and an independent set. Split graphs are universally signable graphs. Hence assuming SETH, the diameter of universally signable graphs cannot be computed optimally in truly sub-quadratic time. The diameter of graphs with tree-width at most two can be computed in

Read the complete text