CS Paper Radar

On Kernels and Leaves: Searching for Bare and Lush Trees

Jesse Beisegel, Ekkehard Köhler, Robert Scheffler, Martin Strehler

cs.DS cs.CCcs.DM ·submitted 2026-09-24 12:08 UTC · v1

Abstract

We study a variation of the classical Maximum (Minimum) Leaf Spanning Tree problem. In many applications, Depth-First Search (DFS) is used to compute a spanning tree of a graph. Such a search tree is constructed by connecting each vertex $v$ with the last vertex the search has visited before $v$ and we call this a last-in tree. By restricting the Maximum (Minimum) Leaf Spanning Tree problem to last-in trees of a graph search, we ask for a search ordering that leads to the largest (smallest) number of leaves in its search tree. Recently, Bergougnoux et al. [Journal of Computer and System Sciences 154 (2025)] have studied the parameterized complexity of these problems for DFS. They showed that the minimization problem is para-$\mathsf{NP}$-hard and the maximization problem is $\mathsf{W}[1]$-hard when parameterized by the number of leaves. When parameterized by the number of internal vertices, both problems have polynomial kernels. Here, we examine whether these results also hold for the variant Lexicographic DFS (LDFS). We show that the hardness results of DFS can be transferred to LDFS. We also present exponential kernels for the number of internal vertices as the parameter. We complement this by showing that polynomial kernels do not exist, unless $\mathsf{NP} \subseteq \mathsf{coNP} / \mathsf{poly}$. We also consider last-in trees of searches that do not follow the DFS scheme. In contrast to (L)DFS, minimizing the number of internal vertices is para-$\mathsf{NP}$-hard for several searches including Breadth-First Search.

Comment
Full version of an extended abstract accepted for IPEC 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Generalized Graph Search Trees

cs.DM cs.DS ·2026-09-08 ·Florian Krowiorz, Robert Scheffler
similarity 0.67
Abstract

Graph search algorithms and their corresponding graph search trees are commonly used in algorithmic graph theory. In recent years, the recognition problem of these graph search trees has received significant attention. So far, the research has focused on two types of search trees: first-in trees that behave like BFS-trees and last-in trees that behave like DFS-trees. The search tree paradigms differ from each other by the parent a vertex is connected to. In first-in trees, it is the first visited neighbor, while in last-in trees it is the last neighbor visited before that vertex. Here, we will generalize these concepts of graph search trees by allowing every preceding neighbor of a vertex to be the parent. We study the complexity of the recognition problem of these generalized graph search trees. We present NP-completeness proofs for most searches. We also show that the problem is trivial for Generic Search and polynomial-time solvable for several searches on bipartite graphs and chordal graphs. We also study the question how fixing the start vertex influences the complexity of the problem.

0.19

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.66
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

Incremental Minimum Spanning Trees on a Napkin

cs.DS ·2026-11-03 ·Lucian Bicsi, Adrian Budău
similarity 0.63
Abstract · 20 pages, 5 figures, 3 tables

In the incremental minimum spanning forest problem, weighted edges arrive one at a time. After each insertion we must report the edge that leaves the minimum spanning forest, and queries ask for the bottleneck distance of two vertices: the smallest possible maximum edge cost on a path between them. Link-cut trees solve both in $O(\log n)$ amortized time. In 2021 we wrote the folklore BottleneckTree, a short competitive-programming structure that stores one parent pointer and one cost per vertex, and conjectured that it also runs in $O(\log n)$ amortized time. We show that this conjecture is false: on a family of inputs, its amortized cost per operation is $Ω(\sqrt{n})$. We then present a structure with the same state, two arrays and a single loop, and prove that it runs in $O(\log n)$ amortized time per insertion and per query. Unlike the AM-tree of Ding, Gu and Sun, which attains the same bound, it stores no subtree sizes and maintains no balance invariant. For a connected graph with distinct costs, the structure can be viewed as an implicit link-cut tree on the Kruskal reconstruction tree: each rotation corresponds to exactly one preferred-child change, and each skip acts on a stale path-parent pointer. In experiments it is 1.3-2.1 times faster than the folklore BottleneckTree on insertions, up to 480 times faster on its adversarial input, and 6.3-16 times faster than an explicit link-cut tree.

0.32

Not All Degree Constraints Are Created Equal when Computing Spanning Trees

cs.DS ·2026-08-26 ·Narek Bojikian, Alexander Firbas, Robert Ganian, Hung P. Hoang, Krisztina Szilagyi
publishedtheory similarity 0.63
Abstract · To appear at IPEC 2026. This is the original submitted version - reviewer comments will be incorporated in a later version

We study the computation of minimum spanning trees subject to local degree constraints. Recent work (ICALP 2026) established that three natural formalizations of this problem share the exact same parameterized complexity under standard structural graph parameters, including treewidth, pathwidth and clique-width. This applies to the cases where every vertex has a single target degree (Specified Degree MST), or a degree upper bound (Bounded Degree MST), or is equipped with a set of admissible degrees (Set of Degrees MST). In this paper, we investigate these problems under more restrictive parameterizations and reveal that their complexity landscapes fundamentally diverge on bounded-treedepth graphs. Specifically, we prove that the former two problems are fixed-parameter tractable when parameterized by the treedepth of the input graph. In sharp contrast, we show that Set of Degrees MST remains W[1]-hard parameterized by treedepth, even when combined with the feedback vertex number (i.e., deletion distance to treewidth $1$). Finally, we show that this divergence seems to be specific to treedepth: we exclude an analogous W[1]-hardness result for Set of Degrees MST w.r.t. the vertex cover number and also rule out fixed-parameter algorithms for the former two problems w.r.t. deletion distance to constant pathwidth.

0.19

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

On (Directed) Width-Parameters of Geometric Spanners

cs.CG ·2026-09-18 ·Kevin Buchin, Carolin Rehs, Torben Scheele
published similarity 0.62
Abstract · Accepted at ISAAC 2026

To speed up algorithms on geometric graphs, it is common to approximate the complete Euclidean graph while maintaining certain geometric properties. A (directed) $t$-spanner $G$ for a point set $P$ in the Euclidean space is a (directed) graph such that for every pair of points, the shortest path in $G$ is at most a factor $t$ longer than the Euclidean distance between those points. In this paper, we investigate $t$-spanners that are bounded by certain graph parameters. Let $κ$ be a graph parameter. We show that for path-width, branch-width and cut-width there is an $\mathcal{O}(n/k^{d/(d-1)})$-spanner $G$ on $P$ with $κ(G)=k$ and that this is asymptotically worst-case optimal. In $\mathbb{R}^2$ we show the same bounds for planar graphs of clique-width or rank-width $k$. In contrast, for tree-depth, we show that there are sets of points for which the dilation cannot be bounded. Therefore, we investigate computing a spanner with tree-depth $k$ and minimum dilation. We show that already for tree-depth $3$ this problem is NP-hard to approximate within any factor strictly less than $\sqrt{2}$, and present an XP-algorithm to compute for a given tree-depth $k$ a graph with dilation at most $2t^*$, where $t^*$ is the minimum dilation. We further extend these results to obtain directed $\mathcal{O}(n/k^{d/(d-1)})$-spanners $G$ with $κ(G)=k$ for $κ$ being directed tree-width, directed path-width or DAG-width and show that also in the directed case, this is asymptotically worst-case optimal.

0.29

Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth-$η$ Deletion

cs.DS cs.CC ·2026-08-10 ·Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann, Roohani Sharma
publishedtheory similarity 0.62
Abstract

For a constant $η\geq 0$, Pathwidth-$η$ Deletion is the problem of deciding whether, for a given graph $G$ and integer $k$, there is a set $S \subseteq V(G)$ of size at most $k$ such that the pathwidth of $G - S$ is at most $η$. The problems Treewidth-$η$ Deletion and Treedepth-$η$ Deletion are defined similarly for the parameters treewidth and treedepth, respectively. A landmark result of Fomin et al. [FOCS, 2012] shows that, for any constant $η$, all three problems admit a kernel on $O(k^{c(η)})$ vertices, where $c(η)$ is a constant depending on $η$. Giannopoulou et al. [ACM TALG, 2017] show that, in some sense, this result is optimal for Treewidth-$η$ Deletion: for $η\geq 2$ and even when parameterizing by the size of a vertex cover $M$ of the input graph, there is no kernel of size $O(|M|^{\frac{η+1}{2}-\varepsilon})$, for any $\varepsilon > 0$. Contrasting this result, they prove that Treedepth-$η$ Deletion admits a uniform polynomial kernel, that is, a kernel of size $O(k^c)$ for a constant $c$ that is independent of $η$. In comparison, the question whether Pathwidth-$η$ Deletion admits a uniform polynomial kernel has been neglected in the literature. As treewidth and pathwidth tend to behave similarly, it is natural to expect that no uniform kernel exists when parameterizing by the size of a vertex cover. Surprisingly, we show this not to be the case. More concretely, we prove the existence of a uniform polynomial kernel for Pathwidth-$η$ Deletion when parameterizing by (1) the solution size $k$ plus the size of a set $M$ such that $G - M$ has bounded treedepth; (2) the (vertex-deletion) distance to pathwidth-$1$ graphs; (3) the distance to the class of graphs with treedepth at most $η+ 1$. This leads us to conjecture that Pathwidth-$η$ Deletion admits a uniform kernel when parameterizing by the solution size $k$.

0.50

A general algebraic characterization of extremal $Δ$-trees and $k$-cyclic graphs for degree-homogeneous VDB indices

cs.DM math.CO ·2026-10-25 ·Milan Bašić
similarity 0.61
Abstract · 16 pages, 1 figure

We present a general algebraic method for maximizing a vertex-degree-based (VDB) topological index $TI(G) = \sum_{uv \in E(G)} f(d(u),d(v))$ over the class of $n$-vertex trees with a prescribed maximum degree $Δ\ge 3$. By expressing the edge multiplicities of the basis $\mathcal{B} = \{(1,Δ), (Δ,Δ)\}$ via degree-sum identities, we reduce the maximization of $TI(T)$ to the minimization of an explicit discrete penalty function $G(x,y)$ over the non-basic edges. We formulate five analytical conditions on the weight function $f(x,y)$ that dictate the optimal edge distributions, yielding a complete characterization of the extremal trees across all congruence classes of $n \pmod{Δ- 1}$. Additionally, we provide their explicit construction by attaching leaves to a core of internal vertices. Applying this framework, we obtain the complete characterization of extremal $Δ$-trees for the Degree-Ratio Sombor ($DRSO$), Symmetric Division Deg ($SDD$), and Hyperbolic Sombor ($HSO$) indices for all $Δ\ge 3$. Furthermore, the analytical conditions identify the exact degree thresholds for the Arithmetic-Geometric ($AG$) and Diminished Sombor ($DSO$) indices, showing that the same extremal family maximizes $AG$ if and only if $3 \le Δ\le 8$, and $DSO$ if and only if $3 \le Δ\le 4$. Finally, since changing the edge count from $m = n - 1$ to $m = n - 1 + k$ affects only the constant term in the decomposition while leaving the penalty function $G(x,y)$ invariant, the method extends directly to connected $k$-cyclic graphs.

0.18