CS Paper Radar

Computing the Helly Number, Radon Number and Rank in Cycle Convexity

Revathy S. Nair, Bijo S. Anand, Ullas Chandran S. V., Julliano R. Nascimento, Arun Anil

cs.DM math.CO ·submitted 2026-09-28 03:40 UTC · v1

Abstract

In this paper, we investigate three fundamental convexity parameters of graphs under cycle convexity, namely the Helly number, Radon number, and rank. We first study the computational complexity of these parameters. For each of these parameters, we consider the associated threshold decision problem of determining whether the parameter of a given graph is at least a prescribed integer. We establish that all three problems are $\NP$-hard and $\W[1]$-hard when parameterized by the threshold. Moreover, we strengthen these results by showing that the $\NP$-hardness persists even when the input is restricted to planar graphs of maximum degree at most $6$. We also focus on the structural properties of connected graphs corresponding to extremal values of these parameters. In particular, we characterize the graph classes for which the three parameters attain the values $n-1$ and $n-2$, where $n$ is the order of $G$.

Closest papers

Nearest neighbours by meaning across the whole index.

Sub-polynomial parameterized complexity of $k$-core

cs.CC ·2026-09-21 ·Yan S. Couto, Cristina G. Fernandes
theory similarity 0.65
Abstract

The $k$-core of a graph is its (unique) largest subgraph with minimum degree at least $k$. For any $k \geq 3$, deciding whether a given vertex belongs to the $k$-core is a P-complete problem, meaning that it is inherently sequential and highly unlikely to admit efficient parallel algorithms, even on graphs of maximum degree $k+1$. This paper investigates alternative parameterizations of the $k$-core problem to identify conditions under which it can be placed into sub-polynomial complexity classes. We prove that the problem is in para-NC$^{2+ε}$ when parameterized by treewidth, and in para-NC$^3$ when parameterized by $k$ on chordal graphs. Furthermore, we introduce a novel NC$^{3}$ algorithm for interval graphs when $k = \mathcal{O}(\lg v(G))$, which relies on an improved parameterization by pathwidth. Finally, we establish corresponding lower bounds, demonstrating that, even with these parameterizations, computing the $k$-core remains L-hard, meaning it requires at least logarithmic space. These findings explore the boundary of parallel tractability for the $k$-core problem by highlighting the graph parameters that make it inherently sequential.

0.23

Minimum Label $k$-Cut on Planar Graphs: Complexity and Color Structure

cs.DS ·2026-10-29 ·Yuanhao Wang, Wei Wang
theory similarity 0.64
Abstract

Minimum Label $k$-Cut asks for a minimum-size set of colors such that deleting all edges of these colors leaves at least $k$ connected components. We study how the structure of the underlying graph and its color classes affects the complexity of this problem. Regarding fixed-parameter tractability with respect to $k$ on simple planar graphs, we prove that the problem is W[1]-hard, even when the underlying graph is a cactus graph and each color appears at most twice. Furthermore, for cactus graphs in which every color class is connected, we establish a complexity boundary in terms of the maximum monochromatic degree: when this degree is at most two, an optimal solution can be found in $O(Nk^2)$ time, where $N$ is the input size, with no restriction on color frequency or the number of blocks spanned by a color; allowing the maximum monochromatic degree to increase to three already makes the decision version NP-complete. Finally, we prove that the problem remains W[1]-hard parameterized by $k$ on fan graphs, even when every color class is an induced path. These results show that bounding color frequency does not suffice to eliminate parameterized hardness. They also establish a monochromatic-degree boundary for connected colors on cactus graphs and identify complexity barriers to extending this tractable case to outerplanar graphs.

0.16

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

NP-Hardness of the $H$-Free Edge-Deletion Problem

cs.CC math.CO ·2026-09-09 ·Lior Gishboliner, Ethan Honest
similarity 0.64
Abstract

For a graph $H$, the $H$-freeness edge-deletion problem is the algorithmic problem of finding, for an input graph $G$, the minimum number of edges of $G$ whose deletion turns $G$ into an $H$-free graph. We show that for every graph $H$ containing a cycle, this problem is NP-hard. This proves a conjecture of Gishboliner, Levanzov and Shapira, and completes the characterization of the complexity of the $H$-freeness edge-deletion problem, answering a question of Alon, Shapira and Sudakov.

0.38

Minimum Membership Dominating Set and Its Generalization: Leafage vs. Asteroidal Number

cs.DS ·2026-11-10 ·Yuma Tamura, Daichi Wakayama, Akira Suzuki, Xiao Zhou
published similarity 0.64
Abstract · Accepted for publication in IPEC2026

The Dominating Set problem is known to be fixed-parameter tractable when parameterized by leafage, a structural graph parameter defined on chordal graphs. We investigate whether this tractability extends to its variants with natural constraints. Specifically, we study the Minimum Membership Dominating Set problem and its generalization, the Min. $(σ, ρ)$-Dominating Set problem. Given a graph $G$ and a positive integer $\ell$, Minimum Membership Dominating Set asks whether there is a dominating set $D$ such that every vertex in $G$ is dominated by at most $\ell$ vertices in $D$. We first show a negative result: Minimum Membership Dominating Set parameterized by leafage plus $\ell$ is W[1]-hard, demonstrating that even this natural constraint serves as a severe barrier to designing FPT algorithms. To complement this, we present an XP algorithm for the Min. $(σ, ρ)$-Dominating Set problem parameterized by asteroidal number plus $μ$, where $σ$ and $ρ$ are finite sets of non-negative integers and $μ$ is the maximum value in $σ\cup ρ$. Note that asteroidal number generalizes leafage to arbitrary graphs. Combining this algorithm with our structural bound that every graph $G$ admits a dominating set such that no vertex is dominated by more than $7\mathsf{an}(G)-6$ vertices, where $\mathsf{an}(G)$ denotes the asteroidal number of $G$, we show that Minimum Membership Dominating Set admits an XP algorithm parameterized solely by asteroidal number.

0.32

Packing Diverse Shortest Cycles

cs.DS ·2026-10-07 ·Akanksha Agrawal, Fedor V. Fomin, Petr A. Golovach, Vinod Gupta, Yash Hiren More +1 more
theory similarity 0.64
Abstract

Bentert, Fomin, Golovach, Korhonen, Lochet, Panolan, Ramanujan, Saurabh, and Simonov (SODA 2025) initiated the parameterized study of Edge-Disjoint Shortest Cycle Packing: given a weighted graph $G$ and an integer $k$, decide whether $G$ contains $k$ edge-disjoint cycles of minimum weight. They showed that the problem admits an algorithm running in time $n^{O(k^6)}$ and asked whether it is fixed-parameter tractable or $W[1]$-hard parameterized by $k$. We resolve this question by proving that Edge-Disjoint Shortest Cycle Packing is $W[1]$-hard parameterized by $k$, even on unweighted subcubic graphs. The same lower bound also applies to the vertex-disjoint variant. For planar graphs, they provides a construction of a kernel with $O(k^2)$ vertices and an algorithm running in time $k^{O(k)} \cdot n^{O(1)}$, and explicitly asked whether the problem admits a single-exponential algorithm of running time $2^{O(k)} \cdot n^{O(1)}$. Rather than addressing this question in isolation, we introduce a more general framework, Diverse Shortest Cycle Coverage, which asks for $k$ shortest cycles that may overlap in a controlled way while maximizing the total weight of covered edges. This framework simultaneously captures edge-disjoint shortest cycle packing, the problem of finding diverse shortest cycles, and the problem of maximizing edge coverage by shortest cycles. Our main algorithmic result shows that Diverse Shortest Cycle Coverage can be solved on planar graphs in time $2^{O(k)} \cdot n^{O(1)}$, thereby giving a single-exponential algorithm for Edge-Disjoint Shortest Cycle Packing as a special case. The key idea of our algorithm is a structural analysis of the Laminar Shortest Cycles Tree, a tree-like decomposition that reveals a laminar interaction pattern among shortest cycles in planar graphs and enables an efficient dynamic programming algorithm.

0.24

Parameterized Complexity of Edge-Constrained Graph Partitioning

cs.DS cs.CC ·2026-08-28 ·Ajinkya Gaikwad, Jan Pokorný, Tomáš Valla
similarity 0.63
Abstract

We study the Edge-Constrained Graph Partitioning Problem (ECGP), which asks whether the vertices of a graph can be partitioned into r parts, each inducing at least gamma edges. We also consider a balanced variant (BECGP), requiring equal-sized parts, and signed variants, where the utility of a part is the difference between its numbers of positive and negative edges. We show that ECGP and BECGP remain NP-hard for fixed gamma, while BECGP is also NP-hard for fixed r. For the natural parameterization r+gamma, both problems admit polynomial kernels. We obtain FPT algorithms for ECGP and BECGP parameterized by maximum leaf number, vertex deletion distance to a clique, cluster vertex deletion number plus gamma, and vertex integrity. Furthermore, ECGP is FPT parameterized by vertex deletion distance to stars plus gamma and vertex deletion distance to paths plus gamma. On the negative side, ECGP and BECGP are W[1]-hard when parameterized by r together with several structural parameters. In particular, hardness holds for feedback edge set, vertex deletion distance to stars or paths, and modular width even when the corresponding parameter is zero. The problems are also W[1]-hard parameterized by cluster vertex deletion number plus r, and by clique-width even when gamma=3. For signed graphs, both variants are NP-hard even when r+gamma=3 and the input is a disjoint union of two cliques. Finally, the balanced signed variant is W[1]-hard parameterized by treedepth plus r, even when gamma=0.

0.09

Clique counts under degree and matching constraints

cs.DM math.CO ·2026-10-31 ·Rajat Adak
theory similarity 0.63
Abstract

We study the maximum number of $t$-cliques in graphs with maximum degree at most $D$ and matching number at most $M$, with no restriction on the number of vertices. For $t\ge 3$, we determine this maximum whenever $D\ge 2M-1$ and characterize all extremal graphs when the maximum is positive. Up to isolated vertices, these are complete or complete split graphs for $D\ge 2M$, while $K_{2M}$ is uniquely extremal when $D=2M-1$. We also derive a general upper bound from the Chvátal-Hanson edge theorem and refine it for even $D$. For fixed even $D$ and $3\le t\le D+1$, every extremal graph consists, apart from isolated vertices, of copies of $K_{D+1}$ together with a remainder whose order is bounded independently of $M$. When $D/2$ divides $M$, this remainder is empty and the extremal graph is unique. This structure yields an eventual recurrence, reducing the determination of all extremal values and graphs to finitely many matching bounds.

0.28