CS Paper Radar

Sub-polynomial parameterized complexity of $k$-core

Yan S. Couto, Cristina G. Fernandes

cs.CC ·submitted 2026-09-21 21:17 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

Strictly Unfriendly $k$-Partitions: Sharp Degree Thresholds and ETH-Based Lower Bounds

cs.CC ·2026-10-03 ·Sanjay Jain, Frank Stephan, Haoyun Tang
publishedtheory similarity 0.71
Abstract · Accepted at TAMC 2026; this is the full version with omitted proofs and figures. 23 pages, 13 figures

We present a complete complexity classification and fine-grained analysis for the Strictly Unfriendly $k$-Partition problem ($\text{SU}k\text{P}$), which asks whether the vertices of a graph can be partitioned into $k$ classes such that every vertex has strictly more neighbors in each of the other $k-1$ classes than in its own. We first establish a sharp tractability-intractability threshold with respect to the maximum degree $Δ$: for $k \in \{2, 3\}$, $\text{SU}k\text{P}$ is solvable in polynomial time when $Δ\le 2$, but becomes $\mathbf{NP}$-hard and ETH-hard immediately on subcubic graphs ($Δ= 3$), resolving the degree limitations in prior work and establishing subcubic graphs as the precise frontier of intractability. Furthermore, under the Exponential Time Hypothesis (ETH), we establish the first fine-grained lower bounds via direct reductions from $(3,3)$-SAT. On general graphs, we establish a uniform lower bound across all partition parameters $k \ge 2$, revealing a striking complexity convergence where the core exponential complexity remains invariant despite technical divergences in gadget constructions. On subcubic graphs, we formally quantify the "cost of sparsity," deriving explicit lower bound constants to demonstrate how enforced structural degree restrictions degrade reduction efficiency.

0.19

Polynomial Kernels for Interval Completion

cs.DS cs.CC ·2026-10-07 ·Zimo Sheng, Tian Bai, Mingyu xiao
similarity 0.70
Abstract

An interval graph is the intersection graph of a family of intervals on the real line. \textsc{Interval Completion} asks whether a given graph can be transformed into an interval graph by adding at most $k$ edges. Although the problem is fixed-parameter tractable when parameterized by $k$, whether it admits a polynomial kernel has long been an open question. We resolve this question by giving the first polynomial kernel for \textsc{Interval Completion}. Our main contribution is a parameter-preserving polynomial-time reduction from \textsc{Interval Completion} to \textsc{Odd Cycle Transversal} (OCT). Combining this reduction with the known randomized and deterministic polynomial kernels for OCT and a polynomial-time reduction back to \textsc{Interval Completion}, we obtain a randomized kernel with $\widetilde O(k^{18})$ vertices and $\widetilde O(k^{36})$ edges, and a deterministic kernel with $O(k^{36})$ vertices and $O(k^{72})$ edges. Here, $\widetilde O$ suppresses polylogarithmic factors in $k$.

0.10

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

Subexponential algorithms for structural parameterizations of Vertex Cover in geometric graphs

cs.DS ·2026-11-16 ·Marin Bougeret, Juan Pablo Bravo, Daniel Gonçalves
theory similarity 0.69
Abstract · 43 pages, 8 figures, submitted

A number of recent works have investigated the existence of parameterized subexponential algorithms in geometric graph classes for hitting a fixed small graph as a subgraph or as a minor. In this setting, given an $n$-vertex graph, the goal is to decide in time $n^{O(1)}2^{o(k)}$ if a solution of size at most $k$ exists. Inspired by recent results in kernelization for structural parameters, we investigate subexponential algorithms for the Vertex Cover (VC) problem, but parameterized by distance-to-triviality instead of solution size. More formally, given a fixed "trivial" graph class $\mathcal{C}$, the problem takes as input $(G,X,k)$, where $G \setminus X \in \mathcal{C}$, and asks if $G$ admits a vertex cover of size at most $k$. Our goal is to design algorithms for this problem running in time $n^{O(1)}2^{o(|X|)}$. The motivation is that, since $|X|$ is typically arbitrarily smaller than $k$, such algorithms might be faster than ETH-tight subexponential algorithms parameterized by $k$. We identify two sets of sufficient conditions under which the problem admits a subexponential algorithm: one for the case where $\mathcal{C}$ is the class of paths, and another for the case where $\mathcal{C}$ is the class of graphs of constant treedepth. We also provide two applications of these algorithmic results: we prove that $s$-string graphs and pseudo-disk graphs satisfy the first set of conditions, whereas string graphs satisfy the second set. The two sets share a common condition that might be of independent interest, as it implies a property that bounds the treewidth of any string graph in terms of a given modulator to a fixed graph class $\mathcal{C}$. Finally, concerning more restricted graph classes having the $ASQGM(ω)$ property (such as map graphs and $H$-minor free graphs), we prove a dichotomy, depending on the maximum treewidth in $\mathcal{C}$.

0.14

Kernelization of 2-Club Cluster Edge Deletion on Interval Graphs

cs.DS ·2026-09-01 ·Ajinkya Gaikwad
similarity 0.68
Abstract

The \emph{$s$-Club Cluster Edge Deletion} problem asks whether, given a graph $G$ and an integer $k$, one can delete at most $k$ edges so that every remaining connected component has diameter at most~$s$. This generalizes the classical \emph{Cluster Edge Deletion} problem by permitting components of bounded diameter instead of requiring cliques. On general graphs, $2$-Club Cluster Edge Deletion is known to be fixed-parameter tractable when parameterized by $k$, but it remains open whether it admits a polynomial kernel, as posed in~\cite{ABUKHZAM2023113864}. Motivated by this question, we study the problem on interval graphs and obtain a polynomial vertex kernel of size $\mathcal{O}(k^{5})$. As a complementary result, we also show that the \emph{$s$-Club Cluster Edge Deletion} problem is polynomial time solvable on unit interval graphs. We also show that $2$-Club Cluster Edge Deletion is NP-hard even on split graphs.

0.17

Forbidden Subgraphs of Graphs with Low Bandwidth

cs.DS ·2026-09-01 ·Maria Chudnovsky, Daniel Lokshtanov, Eran Nevo
top venuetheory similarity 0.68
Abstract

A layout of a graph G is an injective function $f : V(G) \rightarrow Z$, and the bandwidth of a layout f is $bw(G,f) = max_{uv \in E(G)} |f(u) - f(v)|$. The bandwidth bw(G) of G is the minimum bandwidth of a layout of G. Computing the bandwidth of a graph is a notoriously hard problem: assuming P != NP, there is no polynomial time algorithm, even on very restricted classes of trees [Monien, SIAM Journal on Algebraic Discrete Methods, 1986], and no constant factor approximation, even on trees [Dubey et al., JCSS 2011]. Assuming the Exponential Time Hypothesis, there is no algorithm with running time $f(k)n^{o(k)}$ to determine whether an input graph has bandwidth at most k, even on very restricted classes of trees [Dregi and Lokshtanov, ICALP 2014]. In this paper we show that {\sc Bandwidth} on general graphs is FPT-approximable. In particular we give an algorithm that takes as input a graph G and an integer k, runs in time $2^{O(9^k)}n^{O(1)}$, and outputs a subtree T of G such that $bw(T) \geq k$ or a layout of G of bandwidth at most $(10^{85} k^{28})^{4^k}$. This resolves in the affirmative an open problem of Chung and Seymour [Discrete Mathematics, 1989], who asked whether the bandwidth of every graph G is upper bounded in terms of the maximum bandwidth of a subtree of G. Our theorem leads to a forbidden subgraph characterization for graphs of bounded bandwidth, and can be seen as an analog for bandwidth of the classic grid minor theorem for treewidth, the forbidden subtree theorem for pathwidth, and the forbidden subpath theorem for treedepth.

0.54

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