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

preprint2026arXivOpen access

Abstract

A graph HH is an \emph{induced minor} of a graph GG if HH can be obtained from GG by a sequence of edge contractions and vertex deletions. Otherwise, GG is \emph{HH-induced minor-free}. In this paper, we provide a different proof of the fact that K2,3K_{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(nm)O(nm)-time algorithm which takes as input a K2,3K_{2,3}-induced minor-free graph with nn vertices and mm edges, and outputs a tree-width two graph HH with the desired additive distortion. For \emph{universally signable} graphs, a subclass of K2,3K_{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 \emph{diameter} of a universally signable graph. In contrast, assuming the \emph{Strong Exponential Time Hypothesis} (\textsc{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)].

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.