CS Paper Radar

Designing Caterpillars for Graphs: Approximation and Hardness

Leon Kullmann, Phuoc Lucky Trinh, Leon Kellerhals, Mitja Krebs, André Nichterlein, Stefan Schmid

cs.DS ·submitted 2026-08-25 12:57 UTC · v1
theory

Abstract

The classical Minimum Linear Arrangement (MLA) problem has been studied extensively. It is known to be NP-hard and it admits an $O(\sqrt{\log n}\log\log n)$-approximation [Feige and Lee, IPL, 2007]. MLA can be defined as follows as design problem: Given a graph $G$ with vertex set $V(G)$, design a path $H$ on the same vertex set that minimizes the linear arrangement cost $\sum_{uv\in E(G)}\textrm{dist}_H(u,v)$, where $\textrm{dist}_H(u,v)$ indicates the distance of $u$ and $v$ in $H$. We initiate the study of the generalization in which $H$ is allowed to be a caterpillar graph of maximum degree at most $Δ$. Caterpillars are the simplest generalization of paths, having pathwidth one and interpolating between paths and stars via the degree parameter $Δ$. We give an algorithm that lifts any $α$-approximation for MLA to an $(α+3-2/(Δ-1))$-approximation for our problem, thus obtaining an $O(\sqrt{\log n}\log\log n)$-approximation for our more general problem as well. Moreover, we derive a $4$-approximation whenever MLA is polynomial-time solvable, in particular, for trees. Complementing these results, we prove NP-hardness for every constant $Δ\geq 2$, and, in stark contrast to MLA, show it remains NP-hard on trees when $Δ$ is part of the input.

Closest papers

Nearest neighbours by meaning across the whole index.

$(α, β)$ Spanners and Hybrid Spanners with Nearly Tight Bounds

cs.DS cs.DM ·2026-09-30 ·Shiri Chechik, Gur Lifshitz
top venue similarity 0.67
Abstract · A preliminary version appeared in SODA 2026

For an $n$-vertex undirected, unweighted graph $G=(V,E)$ and a positive integer $k$, we present new spanner constructions with $O_k(n^{1+1/k})$ edges that achieve nearly optimal guarantees for all distances $d\le k$. Specifically, we construct a spanner $H\subseteq G$ with $O(n^{1+1/k}+(k+d\log d)n)$ edges, ensuring that any pair at original distance at most $d$ satisfies $\mathrm{dist}_H(u,v)\le 2k+O(d\log d)$. Equivalently, the multiplicative stretch for pairs at distance $d$ is $2k/d+O(\log d)$. In particular, setting $d=k/\log k$ yields an $(O(\log k),O(k))$-spanner with $O(n^{1+1/k}+kn)$ edges. For comparison, Ben-Levy and Parter (SODA'20) obtained, for every fixed $\varepsilon>0$ and sufficiently large $k$, an $(O(k^\varepsilon),O_\varepsilon(k))$-spanner with $O_{\varepsilon,k}(n^{1+1/k})$ edges. Our result improves the multiplicative stretch from $O(k^\varepsilon)$ to $O(\log k)$ while keeping the additive term linear in $k$, bringing us closer to the goal of $(O(1),O(k))$-spanners. Furthermore, Ben-Levy and Parter obtained multiplicative stretch $O_\varepsilon(k/d)$ for distances $d\le k^{1-\varepsilon}$, for every fixed $\varepsilon>0$, and an explicit bound of $7k/d$ for $d\le\sqrt{k}/2$. We achieve $2k/d+O(\log d)$, which is $(2+o(1))k/d$ whenever $d=o(k/\log k)$. Our second result is an improved construction of $k$-hybrid spanners, which guarantee stretch $2k-1$ for adjacent pairs and $k$ for non-adjacent pairs. Parter's original construction uses $O(k^2 n^{1+1/k})$ edges; we achieve the same guarantees with $O(n^{1+1/k}+kn)$ edges, removing the $k^2$ factor from the $n^{1+1/k}$ term. For every fixed $k$, our edge bound is optimal up to a constant factor under Erdős' girth conjecture.

0.49

Parameterized Complexity of Isometric Path Cover: Treewidth and Diameter

cs.DS cs.CC ·2026-10-15 ·Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale
similarity 0.65
Abstract

We study the fixed-parameter tractability of the \textsc{Isometric Path Cover} problem where, given an integer $k$ and a simple, undirected, and unweighted graph $G$, the objective is to decide whether $G$ admits a set of $k$ isometric paths (i.e., shortest paths between their endpoints) whose union is the entire vertex set of $G$. We show that \textsc{Isometric Path Cover} is NP-hard on graphs of pathwidth (and thus treewidth) at most 287. This is an interesting contrast with the closely related problems \textsc{Isometric Path Partition} and \textsc{Path Cover}, which are both known to be XP for treewidth, see [Chakraborty et al., WG 2026] and [Foucaud et al., TCS 2026]. On the positive side, we show, by a suitable dynamic programming scheme, that \textsc{Isometric Path Cover} admits an XP algorithm w.r.t.~the parameter combination of treewidth and diameter, running in time $n^{\diam^{O(\tw)}}$ where $\diam$, $\tw$, and $n$ denote the diameter, the treewidth, and the number of vertices of the input graph, respectively. However, we also prove that \textsc{Isometric Path Cover} becomes W[1]-hard for pathwidth on graphs of diameter~7, showing that an XP algorithm is the best one can hope for w.r.t.~this parameterization, under standard complexity theory assumptions.

0.21

Eccentricity Shortest Path: the structural parameter landscape

cs.DS math.CO ·2026-10-14 ·Anand Babu, Ashwin Jacob, Hitendra Kumar, R. B. Sandeep
theory similarity 0.63
Abstract · 74 pages, short abstract for arXiv

The Eccentricity Shortest Path problem asks, given a connected graph and a nonnegative integer $R$, whether some shortest path is within distance $R$ of every vertex. We study its structural parameterized complexity. We give fixed-parameter algorithms for vertex-deletion distance to cographs, vertex-deletion distance to interval graphs, and bandwidth. The interval-deletion result answers a question of Bhyravarapu et al. (IWOCA 2023). We obtain XP algorithms for vertex-deletion distance to chordal graphs, clique-width, and rank-width, without requiring expressions or decompositions for the latter two. Consequently, the problem is polynomial-time solvable for every fixed treewidth, answering a question of Chakraborty et al. (2026). We also derive fixed-parameter tractability for treedepth and XP membership for diameter from earlier algorithms. We prove $\mathsf{W}[3]$-hardness for cutwidth, and hence pathwidth and treewidth, even on graphs of maximum degree at most five; $\mathsf{W}[2]$-hardness for vertex clique-cover number; and NP-hardness on graphs of tree-independence number at most two. For maximum leaf number $\ell$, we obtain an $O(\ell^4)$-bit compression and a polynomial kernel. Finally, unless $\mathsf{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$, we exclude polynomial kernels for bandwidth, feedback edge number, vertex-deletion distance to a clique, and vertex cover number. The last bound also excludes polynomial kernels for vertex-deletion distance to proper interval graphs.

0.24

Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs

cs.DS ·2026-10-19 ·Rares-Darius Buhai, Suprovat Ghoshal, Neng Huang, Pravesh Kothari, Euiwoong Lee +2 more
theory similarity 0.63
Abstract · 70 Pages

We give a polynomial-time algorithm that achieves an $α_{GW} + \tildeΩ(1/d)$-approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most $d$ constraints. This improves on the $α_{GW}+\tildeΩ(1/d^2)$-approximation guarantee of [Hsieh-Kothari, ICALP'23]. We also show a matching Unique Games hardness under randomized polynomial-time reductions, thereby proving that the gain on $α_{GW}$ is optimal up to $\mathrm{polylog}(d)$ factors. Here, $α_{GW} \approx 0.878$ is the approximation ratio of the Goemans-Williamson algorithm. Our results resolve an open question due to Raghavendra and refute his conjectured optimal approximation ratio of $α_{GW} + \tildeΩ(1/\sqrt{d})$. Our local improvement scheme can be thought of as using an adaptive (based on the neighbors) shift applied to the Gaussian before using the GW sign rounding. This allows us to implement a ``soft but simultaneous'' flipping decision at each vertex as opposed to hard but sequential flipping decisions in prior works. Our hardness results are based on a new sparsification lemma for graphs produced by the reduction from Unique Games [Khot-Kindler-Mossel-O'Donnell, SICOMP'07] that preserves the optimal values up to a factor of $1 \pm ε$ while subsampling to an average degree of only $\tilde{O}(1/ε)$. This is the first example of a CSP in which the optimal advantage on degree-$d$ instances is asymptotically smaller than $O(1/\sqrt{d})$ [Trevisan, STOC'01]. A key idea in the proof of our sparsification theorem establishes new bounds on the number of ``nearly optimal'' cuts in the output of the KKMO reduction. This step, in turn, relies on a new, robust inverse Majority-Is-Stablest theorem.

0.15

When Shall We $k$ Meet Again? Tight Algorithms for Diameter and Radius under the Meet Distance

cs.DS ·2026-09-18 ·Yael Kirkpatrick, John Kuszmaul, Merey Temirzinova, Virginia Vassilevska Williams
theory similarity 0.62
Abstract · 20 pages

Finding an optimal meeting point for a collection of agents on a directed graph is a classical problem studied in the context of network analysis, operations research and computational geometry. In this work, we use the two objectives of optimal meeting points examined in the literature to study two notions of meet-distance: $d^{\max}(u,v)$, the minimum over all meeting points $w$ of $\max(d(u,w), d(v,w))$; and $d^+(u,v)$, the minimum over all meeting points of $d(u,w) + d(v,w)$. These values measure the minimum time and minimum total distance required for two agents to meet. We initiate the fine-grained study of fundamental graph parameters under the two notions of meet-distance, namely the diameter, radius and eccentricities. For general directed graphs, we give an $\tilde{O}(m\sqrt{n})$ time algorithm for computing a 2-approximation to both notions of meet-diameter and show that this result is optimal under SETH. In contrast, we show that such a result is unattainable for the meet-radius as any finite approximation requires quadratic time under the Hitting Set Conjecture. For directed acyclic graphs, we obtain stronger results. We compute the meet$^{\max}$-diameter exactly in linear time and give a linear-time $2$-approximation for the meet$^{+}$-diameter. We complement the latter with a quadratic-time lower bound for any $(3/2-\varepsilon)$-approximation under SETH, yielding a separation between the two meet-distance objectives. Finally, we study the generalized meet-distance of $k$-tuples of vertices. For every positive integer $\ell$, we reduce the problem of $\ell$-approximating the $k$-point meet-diameter to computing an exact meet-diameter on smaller tuples, obtaining an $\ell$-approximation in time \[ O\!\left( mn+ \ell \left\lceil k^{1/\ell}\right\rceil n^{\left\lceil k^{1/\ell}\right\rceil+1} \right). \]

0.28

Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs

cs.DM math.CO ·2026-10-01 ·Gautam K. Das, Kamal Santra
similarity 0.62
Abstract

An edge open packing is a set of edges whose endpoints induce a disjoint union of stars. We study the problem of finding a maximum edge open packing in AT-free, chordal, and convex bipartite graphs. For AT-free graphs, we use the oriented star-conflict graph $A_G$, introduced by Das and Santra, for which $ρ_e^o(G)=α(A_G)$, and prove that $A_G$ is AT-free whenever $G$ is AT-free. Consequently, a known maximum independent set algorithm for AT-free graphs yields an $O(n^2+m^4)$-time algorithm for Maximum Edge Open Packing, where $n$ and $m$ denote the numbers of vertices and edges of $G$, respectively. For chordal graphs, we develop an $O(n^4)$-time dynamic programming algorithm over a nice tree decomposition derived from a clique tree, exploiting the structural fact that the endpoint set of an edge open packing intersects every clique in at most two vertices. Finally, for convex bipartite graphs, we obtain an $O(n^4)$-time dynamic programming algorithm based on two boundary indices that separate consecutive star components. This result extends the previously known algorithm for biconvex bipartite graphs and, in particular, provides an improved explicit running-time bound for that class.

0.07

Bicriteria Approximate Navigable Graphs in General Metrics

cs.DS ·2026-10-25 ·Hongyi Chen, Tianyi Zhang
top venue similarity 0.62
Abstract · To appear in SODA 2027

We study approximation algorithms for constructing sparse navigable graphs in general metrics. Given an $n$-point metric $(P,d)$ and a parameter $α\ge 1$, an $α$-navigable graph is a directed graph $G=(P,E)$ such that for every ordered pair of distinct points $s,t\in P$, the vertex $s$ has an outgoing edge $(s,p)$ with $d(p,t)<d(s,t)/α$. The objective is to minimize the number of edges. Approximation algorithms for this problem were recently studied by Khanna, Padaki, and Waingarten (SODA 2026), and independently by Conway et al. (SODA 2026). These works show that the single-criterion problem faces a Set Cover barrier: an $O(\log n)$-approximation is achievable, whereas obtaining an $o(\log n)$-approximation is NP-hard. To obtain faster algorithms, Khanna, Padaki, and Waingarten introduced bicriteria approximation, in which the output graph is required to be $α$-navigable, while its size is compared against that of an optimal $β$-navigable graph for some relaxed parameter $β\ge α$. They gave a fast matrix-multiplication-based algorithm that computes an $(α,2(1+\varepsilon)α)$-bicriteria $O(\log n)$-approximation in time $\widetilde O(n^ω\log Δ/\varepsilon)$, where $Δ$ denotes the aspect ratio and $ω$ is the matrix multiplication exponent. Our main result is a simpler near-quadratic-time algorithm with stronger bicriteria guarantees. For every constant $α\ge 1$, we compute in time $\widetilde O(n^2\logΔ)$ an $α$-navigable graph that is simultaneously an $(α,2α+O(1))$-bicriteria $O(1)$-approximation and an $(α,α+O(1))$-bicriteria $O(\log n)$-approximation. We complement the algorithm with a hardness result showing that for every constant $η\in(0,1)$, no polynomial-time algorithm can compute an $(α,2α-η)$-bicriteria $o(\log n)$-approximation unless $P=NP$.

0.34

Nearly Optimal Sparse Navigable Graphs in General Metrics

cs.DS ·2026-10-29 ·Hongyi Chen, Tianyi Zhang
similarity 0.62
Abstract · 24 pages, 3 figures

We study approximation algorithms for constructing sparse navigable graphs in general metrics. Given an $n$-point metric $(P,d)$ and a parameter $α\ge1$, a directed graph on $P$ is $α$-navigable if, for every pair of distinct points $s,t\in P$, the source $s$ has an outgoing neighbor $p$ with $d(p,t)<d(s,t)/α$. The objective is to minimize the number of edges. Recent independent works of Khanna, Padaki, and Waingarten (2026) and Conway et al. (2026) give $O(\log n)$-approximation algorithms and show that an $o(\log n)$ approximation is NP-hard in general. Before our work, the best known running time for such an approximation for general $α\ge1$ was $\widetilde O(\min\{n\operatorname{OPT}_α,n^{2.5}\})$, where $\operatorname{OPT}_α$ is the minimum number of edges in an $α$-navigable graph. In this paper, we give a randomized algorithm that, with high probability, runs in $\widetilde O(n^2)$ time and achieves an $O(\log n)$ approximation for every $α\ge1$. In general, these guarantees are nearly optimal up to constant factors in the approximation and polylogarithmic factors in the running time.

0.20