CS Paper Radar

Structural properties of semi-cutting sets

Bartłomiej Bosek, Oriol Serra, Lluís Vena

cs.DM math.CO ·submitted 2026-11-15 22:34 UTC · v1
theory

Abstract

Let $G=(V,E)$ be a finite simple undirected graph, let $T\subseteq V$, and let $F\subseteq E$. We call $F$ semi-cutting for $T$ if $d_{G}(u,w)<d_{G\setminus F}(u,w)$ for every two distinct terminals $u,w\in T$. We prove the sharp bound $|F|\ge |T|-1$. The argument is structural: semi-cutting sets are first identified with edge transversals of all shortest terminal-terminal paths, and the bound then follows from a contraction step, a terminal-deletion lemma, and a lexicographic induction on $(|T|,|V|)$.

Comment
7 pages, 4 figures

Closest papers

Nearest neighbours by meaning across the whole index.

On the Parameterized Complexity of Conflict-Free Edge Cut in Undirected Graphs

cs.DS cs.DM ·2026-10-05 ·Sourav Das, Ashwin Jacob, Arpit Kumar, Diptapriyo Majumdar
theory similarity 0.62
Abstract · 26 pages

In this paper, we study CONFLICT-FREE EDGE CUT (CF-CUT), which is a recently introduced conflict-free version of the MIN-CUT problem that asks to find the minimum number of edges to disconnect a connected graph. The CF-CUT takes as input a connected undirected graph G = (V, E), a conflict graph $\widehat{G}$ such that $E(G) = V(\widehat{G})$, and the objective is to decide whether there exists $F \subseteq E(G)$ such that $G - F$ is disconnected and $F$ is an independent set in $\widehat{G}$. Rauch et. al. [IPL-2025] proved that CF-CUT is NP-Complete and also provided some results on the parameterized complexity of CF-CUT. A related variant MIN CONFLICT-FREE EDGE CUT (MIN-CF-CUT) takes a connected graph $G$, a conflict graph $\widehat{G}$ such that $V(\widehat{G}) = E(G)$, and an integer $k$ as input and asks if there is a set $F$ of at most $k$ edges such that $G - F$ is disconnected and $F$ is an independent set in $\widehat{G}$. In this paper, we extend the work of Rauch et al. [IPL-2025] and provide a systematic study on the CF-CUT and MIN-CF-CUT from the perspective of parameterized complexity and polynomial kernelization. We prove that CF-CUT is NP-hard when the dissociation number of the input graph is at most two. We also complement it by proving that CF-CUT is poly-time solvable when the dissociation number of an input graph is at most one. Additionally, for MIN-CF-CUT, we consider both solution size and various structural parameters of the input graph as parameters, and provide fixed-parameter tractability and W[1]-hardness results when the conflict graph is restricted to various graph classes. We also prove that unless NP $\subseteq$ coNP/poly, MIN-CF-CUT admits no polynomial kernel when parameterized by the vertex cover number of the input graph; and also when parameterized by the sum of the solution size and the vertex integrity of the input graph.

0.44

Improved Lower Bound for Steiner Point Removal

cs.DS ·2026-09-16 ·Karthekeyan Chandrasekaran, Chandra Chekuri, Qingyun Chen, Weihao Zhu
theory similarity 0.62
Abstract

In the Steiner Point Removal problem, we are given a graph $G=(V,E)$ with an edge-length function $\ell_G: E\rightarrow \mathbb{R}_+$ and a subset $T\subseteq V$ of terminals. The goal is to find a minor $H=(T, E_H)$ of $G$ on vertex set $T$ such that the shortest path metric derived from $G$ on the edges of $H$ preserves the distance between every pair of terminals within a small multiplicative stretch. Filtser proved that a stretch of $O(\log |T|)$ can be achieved (in polynomial time), while Chen and Tan more recently proved a lower bound of $Ω\left(\sqrt{\frac{\log |T|}{\log\log |T|}}\right)$ on the achievable stretch. Their lower bound is via a simple construction involving low-degree high-girth graphs. The existence of such graphs is guaranteed through the existence of low-degree high-girth expanders. In this work, we improve the lower bound to $Ω(\sqrt{\log |T|})$ using the same simple construction of Chen and Tan but with a more careful analysis that exploits the expansion property.

0.18

Induced packing treewidth III. Branch decompositions

cs.DM math.CO ·2026-11-09 ·Amir Nikabadi, Paweł Rzążewski
theory similarity 0.61
Abstract

The notion of induced packing treewidth aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured tree decompositions. In this paper, we introduce induced packing branchwidth, a branch-decomposition analogue of induced packing treewidth. For a graph $H$, the induced $H$-packing branchwidth of a graph $G$, denoted by $\branchpi_H(G)$, is the minimum, over all branch decompositions of $G$, of the largest number of pairwise anticomplete induced copies of $H$ that cross one displayed cut. For $H=P_2$, it equals sim-width. We prove several structural properties of graphs of bounded $\branchpi_H$, for various choices of $H$, including $χ$-boundedness, polynomial degree-boundedness, and metric properties.

0.13

A Linear Kernel for Planar Semitotal Domination

cs.DS ·2026-10-27 ·Paloma T. de Lima, Lukas Retschmeier
similarity 0.60
Abstract

A set of vertices $S$ in a graph $G$ is a semitotal dominating set if $S$ is a dominating set and every vertex in $S$ has a witness, that is, another vertex in $S$ within distance at most two. The Semitotal Domination problem asks whether $G$ admits such a set of size at most $k$. We study this problem parameterized by the solution size. We provide a linear kernel of size $358k$ on planar graphs, a result that adds to several existing linear kernels for other domination variants on planar graphs. Additionally, we show Semitotal Domination is $W[2]$-hard on split graphs, on bipartite graphs and on $t$-claw-free graphs, it is $W[1]$-hard on circle graphs.

0.15

Conflict-Free Cuts: Exploring the Boundaries of Tractability

cs.DS math.CO ·2026-11-11 ·Subrahmanyam Kalyanasundaram, Subodh Kumar
theory similarity 0.59
Abstract · 48 pages, 9 figures

A conflict-free cut of a host graph $G$ is an edge cut containing no conflicting pair of edges. The conflicts are specified by a conflict graph $\widehat G$ whose vertex set is $E(G)$. The conflict-free cut problem asks if the given instance $(G, \widehat G)$ has a conflict-free cut. When restricted to planar $G$ and 1-regular $\widehat G$, the problem is polynomial time solvable when $G$ has maximum degree 4, but NP-complete already at maximum degree 5. We study the complexity of conflict-free cut problem under restrictions on the degrees of $G$, the components of $\widehat G$, and the locality of the conflicts. A conflict is local if its two edges share an endpoint in $G$. We prove the following results. * For $Δ(\widehat G)\le1$, a directed-cycle formulation gives a polynomial-time algorithm when $|E(G)|\le2|V(G)|$, hence for maximum degree four. The problem is NP-complete on $5$-regular hosts with exactly $1$-regular conflicts. * For $Δ(\widehat G)\le1$, we give a constructive FPT algorithm in $s_4(G)=\sum_v\max\{0,d_G(v)-4\}$, single-exponential for planar hosts. For arbitrary conflicts, we give an XP algorithm in $η=\max\{0,|E(\widehat G)|-|V(G)|\}$. * On $4$-regular hosts, local exactly $2$-regular conflicts with components $C_3,C_4$ give NP-completeness. For local conflicts at maximum degree four, pair or triangle components separately permit polynomial algorithms, but mixing them gives NP-completeness. We classify cases where $\widehat G$ is a union of cliques. * An $a$-COC is a vertex set whose deletion leaves components of order at most $a$. For local conflicts, the problem is FPT in the minimum $2$-COC size, but NP-complete with a supplied $3$-COC of size six. Without locality, hardness holds with a supplied $2$-COC of size six. Both hardness results use exactly $1$-regular conflicts.

0.20

Important Cuts with Logical Constraints: A Meta-Theorem for Eulerian Digraphs

cs.DS ·2026-11-14 ·Václav Blažej, Satyabrata Jana, Jędrzej Olkowski, M. S. Ramanujan, Peter Strulo
top venuetheory similarity 0.58
Abstract · To appear at SODA 2027

Important separators are a standard tool in parameterized cut algorithms. An $S$-$T$ separator is important if it is inclusion-wise minimal and no separator of at most the same size leaves a strict superset of the vertices reachable from $S$ after deletion. Their use relies on a boundedness theorem: for fixed $k$, the number of important $S$-$T$ separators of size at most $k$ is at most a constant ($4^k$ to be precise) independent of the input size, even in directed graphs, and they can be enumerated efficiently. The classical theory, however, controls only the size of the separator, not the structure of the source side cut off by it. Once the source side is required to satisfy a condition such as acyclicity, bipartiteness, or another logical property, the corresponding maximal source sides can be unbounded in general digraphs. This obstruction is fundamentally related to hardness phenomena in directed deletion problems such as Directed Odd Cycle Transversal}. Prior to this work, even in undirected graphs, boundedness of such maximal constrained source sides was known only in more specialized settings, not at the level of generality considered in our work.

0.64

Algorithms for Connected Multicuts of Weighted Trees

cs.DS ·2026-10-17 ·Sunny Atalig, Marek Chrobak, Petr Kolman, Claire Mathieu, Hans Raj Tiwary
similarity 0.58
Abstract

In the \emph{connected multicut problem for weighted trees}, the instance is an edge-weighted tree $T = (V,E,ω)$, a set of terminals $Γ\subseteq V$, and a set of pairwise ``conflicts'' between these terminals represented by edges of a conflict graph $\mathcal{C} = (Γ,\mathcal{F})$. A \emph{connected multicut} for this instance is a partition $\mathcal{M}$ of the vertex set $V$ into subsets called the \emph{components of $\mathcal{M}$}, where each component induces a subtree of $T$, contains at least one terminal, but does not contain any conflicting terminal pair. Two cost functions for multicuts are considered: in the min-sum variant, we minimize the total weight of the edges between different components of $\mathcal{M}$, and in the min-max variant, we minimize the maximum, over all components, of the total weight of edges leaving the component. In the first part of the paper, we focus on algorithms for the min-max variant, for which we give a $2$-approximation algorithm for the unweighted case, a $(2+ε)$-approximation algorithm for the general case, and a mildly exponential exact algorithm for the unweighted case. In the second part of the paper, we study algorithms that take advantage of the structure of the conflict graph. We first give a polynomial-time exact algorithm for the min-max variant when $\mathcal{C}$ is a clique (the variant referred to in the literature as the \emph{multiway cut}). Next, we generalize this result by providing polynomial-time exact algorithms, for both variants, for instances whose conflict graph has constant \emph{split complexity} --- a new parameter that refines the concept of neighborhood diversity previously studied in the context of parameterized complexity. This unifies and generalizes previous results for the min-sum variant when conflict graphs are complete multipartite graphs or unions of cliques.

0.25

On (Directed) Width-Parameters of Geometric Spanners

cs.CG ·2026-09-18 ·Kevin Buchin, Carolin Rehs, Torben Scheele
published similarity 0.58
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