CS Paper Radar

Weekly top 20 · cs.DM

2026-W47 Nov 16 – Nov 22, 2026

Ranked from 3,194 papers submitted on 4 days — week in progress, ranks can still change.

Score = weighted mean ofCitations 20%Upvotes 10%Code stars 10%Venue 15%Code/data 10%Novelty 15%Momentum 15%Substance 5%how it works
1

Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity

cs.DM math.CO ·2026-11-16 ·Florent Foucaud, Yan Gerard, Christian Laforest, Le Vu Pham
published
Abstract · 23 pages, 5 figures. Appears in the Proceedings of the 52nd International Conference on Current Trends in Theory and Practice of Computer Sc…

A vertex is uni-dominated by a set $S \subseteq V(G)$ if exactly one vertex of $S$ lies in its closed neighborhood, and the uni-domination number $\mathrm{ud}^*(G)$ is the largest number of vertices a single set can uni-dominate. The graphs admitting an efficient dominating set are those with $\mathrm{ud}^*(G) = n$. Hedetniemi and Rall asked for the largest constant $c$ with $\mathrm{ud}^*(T) \geq c \cdot n$ for every tree $T$ of order $n$. We answer their question: the constant is $4/5$, and a set attaining it can be computed in linear time. This set is moreover a dominating set. Recall that an efficient dominating set satisfies two requirements at once: it dominates every vertex, and it dominates no vertex twice. Our set satisfies the first one, which leads us to study $\mathrm{ud}^*$ under each of the two requirements separately, giving the Full-Cover variant $\mathrm{ud}^*_0$ and the Non-Overlapping variant $\mathrm{ud}^*_+$. The two behave very differently: on arbitrarily large graphs $\mathrm{ud}^*_0$ may remain bounded by a constant, whereas $\mathrm{ud}^*_+$ always grows with the order. We present bounds for both, and show that the associated decision problems are polynomial for constant thresholds and NP-complete for the thresholds $\lceil \sqrt[c]{n} \rceil$ and $4\sqrt{n}$, respectively, the latter even on split graphs. Finally, we show that neither of the two parameters bounds the other.

0.55
2

Beyond 4: Improved Competitive Traveling Repairperson

cs.DS cs.DCcs.DMcs.MA ·2026-11-16 ·Bibek Maharjan, Gokarna Sharma
Abstract · 27 pages, 1 figure, 2 pseudocodes, 1 table

With $k\geq 1$ repairpersons starting initially from a depot, we present a 3.877-competitive deterministic algorithm for the fundamental online traveling repairperson problem on an arbitrary metric. For the special class of zero-residual instances, we improve the ratio to $3+ε$ for every $ε>0$. We also extend these results to some variants of the related so-called online dial-a-ride problem. The state-of-the-art is the 4-competitive deterministic algorithm for both problems.

0.48
3

An Optimal Online Algorithm for Single-machine Scheduling with Two Agents

cs.DS cs.DM ·2026-11-16 ·Peihai Liu, Kejun Zhao, Xiwen Lu
theory
Abstract · 24 pages, 6 figure. Comments and suggestions are most welcome

This paper addresses the online two-agent scheduling problem on a single machine, where jobs arrive over time. The objective is to minimize the weighted sum of the agents' makespans, denoted as $C_{\max}^A + θC_{\max}^B$, for a given priority weight $θ\ge 1$. A significant gap has persisted between the established theoretical lower bound on the competitive ratio and the performance of the best-known online algorithms. For the parameter range $1 \leq θ\leq \tfrac{1+\sqrt{5}}{2}$, we propose novel online algorithm which achieves a competitive ratio of $1+\tfracθ{1+θ}$. This result matches the theoretical lower bound.

0.43
4

Up or down at every integer: Collatz-type maps of arbitrary sets and the up-down graph

cs.DM math.DSmath.NT ·2026-11-16 ·Oleg Vasilyev
Abstract

For a set $S$ of positive integers let $T_S$ send $x$ to $\lceil 3x/2\rceil$ if $x\in S$ and to $\lceil x/2\rceil$ otherwise. The odd numbers give the Collatz map, the even numbers give it again after a shift by one, and $S=\mathbb{N}$ gives Mahler's map $x\mapsto\lceil 3x/2\rceil$. All these maps are subgraphs of the up-down graph $G$, in which every $x$ has the edges $x\to\lceil x/2\rceil$ and $x\to\lceil 3x/2\rceil$, and so are the families of maps in which the direction is forced at some numbers and free at the others. The cycles of the maps are the simple cycles of the subgraph, their divergent orbits are its rays, and all maps of a family are bounded exactly when the subgraph has no ray. We classify the simplest sets and show that density says little: some sets of density one send every orbit to 1, and some periodic sets of arbitrarily small density have increasing orbits. Every positive integer is the least element of a cycle of some map. The critical proportion of steps up is $\log_3 2$: cycles stay below it, divergent orbits stay above it, and both come arbitrarily close. For sets periodic modulo a power of 2, an effective up-frequency from a finite Markov chain takes the place of the density, and a finite computation can prove that every orbit reaches a cycle. Mahler's Z-number problem is implied by a question about one such map. Finally, we ask how far the Collatz map is from maps whose behaviour can be proved. Finite changes never help. Adding fewer than $\log_{3/2}N+1$ even numbers below $N$ makes an orbit increase, while removing the odd numbers congruent to 9 or 15 modulo 16, an eighth of all integers, gives a map all of whose orbits provably reach the cycle (1,2); removing 22 residue classes modulo 512, a proportion 0.043, also suffices.

0.39
5

Exact guarantees and faster algorithms for $k$-rollercoasters

cs.DM cs.DS ·2026-11-19 ·Sungmin Kim, Florin Manea
theory
Abstract

For $k\ge3$, a $k$-rollercoaster is a sequence of distinct values whose maximal increasing and decreasing runs all have length at least $k$. We discover the maximum guaranteed length $f_k(n)$ of $k$-rollercoasters appearing as subsequences of $n$-point permutations. In particular, letting $q=k-1$, we prove that $f_k(n)= \lceil n/q\rceil$ for $n\ge2q^2$, $f_k(n)= 2q-\lfloor \sqrt{2q^2-n}\rfloor$ for $q^2<n<2q^2$ and $f_k(n)= 0$ otherwise. We prove that the guarantees are tight by constructing an $n$-point permutation whose longest $k$-rollercoaster has exactly $f_k(n)$ points. Our proof extends Seidenberg's argument [Journal of the London Mathematical Society, 1959] for proving the Erdős--Szekeres theorem by representing points in a subsequence with respect to the lengths of longest monotonic (increasing and decreasing) subsequences that reach each point. The combinatorial proof yields a deterministic comparison-based algorithm that finds a rollercoaster of length at least $f_k(n)$ in $O(n\log f_k(n))$ time and $O(n)$ space for $n>q^2$. Independently, we give an $O(nk\log k)$-time, $O(nk)$-space algorithm for a longest $k$-rollercoaster, improving the previous $O(nk^2)$ bound. We use the dynamic program of Gawrychowski et al. [STACS 2019, Algorithmica 2022], and process its weighted predecessor queries through monotone subsequences with finger-search trees. Both algorithms return such subsequences.

0.37
6

Strong Transitivity of Group Cellular Automata: Characterization and Decidability

cs.DM cs.FLmath.DS ·2026-11-17 ·Niccolò Castronuovo, Alberto Dennunzio, Luciano Margara
theory
Abstract

A discrete-time dynamical system is strongly transitive if every point can be reached, in finitely many steps, from every non-empty open set. We study this property for group cellular automata, \ie cellular automata over a finite group alphabet whose global map is a group endomorphism, in every dimension $d\geq1$. We prove that no group cellular automaton over a non-abelian group is strongly transitive, and we develop a decomposition of group cellular automata over abelian groups, via quotients by power subgroups, which preserves strong transitivity. For linear cellular automata over $(\mathbb Z/p\mathbb Z)^n$ we use Pontryagin duality to characterize strong transitivity in terms of the characteristic polynomial $χ_A$ of the associated matrix $A$ of Laurent polynomials: the automaton is strongly transitive if and only if $\det(A)\neq0$ and no irreducible factor of $χ_A$ has an invertible constant term. Combining these results, we obtain that strong transitivity is decidable for group cellular automata in every dimension. For every fixed dimension $d$, we give an explicit decision procedure whose running time is polynomial in the group size $N$, the number $k$ of neighbours, and the neighbourhood radius $\varrho$.

0.34
7

Speed-Robust Scheduling for Total Completion Time

cs.DS cs.DM ·2026-11-16 ·Moritz Buchem, Nicole Megow, Morten Weber
Abstract

We study two-stage speed-robust scheduling for minimizing total completion time. Jobs must be partitioned into $M$ bags before an adversary reveals the speeds of at most $M$ machines. Each bag is then assigned to one available machine, and the jobs on each machine may be processed in any order independent of the bags. We compare with an optimal schedule that knows the speeds in advance and assigns jobs individually. This model has been studied for makespan minimization. We initiate its study for total completion time, as suggested by Stein and Zhong (TALG 2020). For an unknown number of identical machines, we show that the optimal deterministic robustness factor is exactly~$13/12$, both for unit-size jobs and for arbitrary processing times. For infinitesimally small jobs, the factor lies between $31/30\approx1.0333$ and $28/27\approx1.0370$, well below the optimal makespan factor of about $1.2071$. General speeds make the problem strictly harder: no deterministic algorithm is better than $1.2669$-robust, already for infinitesimally small jobs. We give a $25/16$-robust algorithm for arbitrary processing times and improve the guarantee to $1681/1152\approx1.4592$ for infinitesimally small jobs. Our main tools are a layer decomposition that extends guarantees from unit-size jobs to arbitrary processing times when one assignment satisfies them for every prefix in non-increasing processing-time order, and a threshold analysis of the bag counts produced by greedy assignment rules.

0.31
8

A (12/11+eps)-Approximation for Nonpreemptive Throughput Maximization

cs.DS cs.DM ·2026-11-18 ·Mikhail Cherniavskii, Mikhail Koshelev, Andrey Kupavskii, Stanislav Moiseev, Fedor Ozhegov +1 more
Abstract

We study unweighted nonpreemptive throughput maximization on an arbitrary number of identical machines: each job has a processing time and a release--deadline window, and the goal is to schedule as many jobs as possible. For every fixed $\varepsilon>0$, we give a randomized $(12/11+\varepsilon)$-approximation. This improves the recent $(4/3+\varepsilon)$-approximation of Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese and the $(17/13+\varepsilon)$-approximation of Tong and Xu. For binary-encoded integral inputs, our algorithm runs in time $n^{O_\varepsilon(1)}\operatorname{poly}(N)$, where $N$ is the input length.

0.28
9

Proper thinness at most 2: threshold and trivially perfect graphs

cs.DM ·2026-11-17 ·Barbara Rivero, Eric Brandwein, Flavia Bonomo-Braberman
Abstract · 43 pages, 7 figures

The proper thinness of a graph is a parameter that generalizes proper interval graphs: the graphs of proper thinness 1 are exactly the proper interval graphs. The complexity of computing it is open even for cographs. In this paper we study it on two subclasses of cographs: threshold graphs and trivially perfect graphs. For threshold graphs, we show that the proper thinness is 1 if the graph is claw-free and 2 otherwise. For trivially perfect graphs, we characterize those of proper thinness at most 2 in three ways: structurally, through two properties of strongly consistent solutions that we call staggered and boundary; algorithmically, with a linear-time algorithm that decides whether the proper thinness is at most 2; and by forbidden induced subgraphs, showing that the $\mathrm{claw}_2$ and the lotus are exactly the minimal obstructions.

0.26
10

There is no binary linear $[65,9,29]$ code

cs.IT cs.DMmath.CO ·2026-11-18 ·Zhichao Tang, Xiang Fan
theory
Abstract · 10 pages

We prove that no binary linear $[65,9,\geqslant29]$ code exists, equivalently, that no even binary linear $[66,9,\geqslant30]$ code exists. Together with known constructions, this determines $d_2(65,9)=28$, $n_2(9,29)=66$, and $n_2(9,30)=67$. A residual-code bound and a known construction also give $d_2(122,10)=56$. To prove nonexistence, we associate with a hypothetical even code a quadratic function derived from half the codeword weight modulo $2$. Its polar form determines the fourth derivative of a Boolean function of degree at most four. Character sums, weight moments, and the exclusion of weight-$42$ codewords give upper bounds on the support of this function in seven cases. Restrictions to nondegenerate affine subspaces exclude six cases. In the remaining case, equality would force four distinct coordinate functionals to be identically $1$ on an affine seven-space, although at most two can have this property. The argument uses published minimum-length results for binary linear codes of dimensions eight and nine.

0.25
11

The Sum of Leaf Weights in the Minimum Spanning Tree of the Complete Graph

cs.DM math.CO ·2026-11-16 ·Julia Gaudio, Phawin Prongpaophan, Miklós Z. Rácz
theory
Abstract

Let $G_n$ be a random weighted complete graph on $n$ vertices, where edges have i.i.d. $\text{Unif}(0,1)$ weights. Let $T_n$ be the Minimum Spanning Tree (MST) of $G_n$. The expected weight of $T_n$ is known to converge to $ζ(3) = \sum_{k=1}^{\infty} \frac{1}{k^3}$ (Frieze 1985). We investigate the sum of weights of edges incident to the leaves of $T_n$, denoting this quantity by $L_n$. We give tight upper and lower bounds on $\mathbb{E}[L_n]$ and determine its limit as $n$ diverges, leveraging typical behavior of sparse Erdős--Rényi random graphs. We also establish concentration of $L_n$ around $\mathbb{E}[L_n]$ and almost sure convergence to this value. These results directly yield substantial improvements to state-of-the-art bounds for two important variants of the MST problem: (1) an improved upper bound on the weight of the optimal random instance Steiner tree, as studied by Bollobás, Gamarnik, Riordan, and Sudakov (2004); and (2) an improvement over the upper bound for the Probabilistic Minimum Spanning Tree, introduced by Bertsimas (1988).

0.24
12

From a finite subgroup of $SO(3)$:$C_2$ leads to a Holant dichotomy

cs.CC cs.CLcs.DM ·2026-11-18 ·Yuxuan Zhou
theory
Abstract

Counting complexity within the Holant framework has been extensively studied through complexity dichotomy theorems. While substantial progress has been achieved for various restricted settings, the general complex-valued even-arity case without auxiliary unary signatures remains largely open. This paper studies a fundamental case in this program where the binary signatures induce a group structure satisfying \(M(B(\mathcal{F}))\cong C_2\). It is observed that projective equivalence classes of binary signature matrices naturally embed into finite subgroups of \(SO(3)\), providing an algebraic viewpoint for structural classification. This paper further identifies two fundamentally different regimes for the \(C_2\) case, namely the normal and isotropic cases, and analyzes their complexity behavior separately. Combining gadget constructions, decomposition techniques, interpolation arguments, and a realnumberization approach that transforms the complex-valued setting into an equivalent real-structured framework, this paper establishes a complete dichotomy theorem: for every even-arity signature set \(\mathcal{F}\) satisfying \(M(\B(\mathcal{F}))\cong C_2\), the problem \(\mathrm{Holant}(\mathcal{F})\) is either polynomial-time computable or \#P-hard. A Pauli-basis representation for signatures is further introduced as an algebraically natural language for organizing realizable signatures and revealing structural relations that are less transparent in the standard basis.

0.24
13

Matroid Connectedness and Component Decomposition: Breaking the Quadratic Barrier

cs.DM ·2026-11-17 ·Manuel Aprile, Roberto Ronco
theory
Abstract

Deciding whether a matroid is connected and computing its connected components are two fundamental algorithmic problems in matroid theory. Since the 1970s, the best known algorithms for both problems have used $O(n^2)$ independence queries on an $n$-element ground set. Our main contribution is to break this quadratic barrier: we give a deterministic algorithm that computes all connected components of a matroid on $n$ elements with $O(n \log{n})$ independence queries. Our algorithm for component decomposition combines fundamental basis exchanges with a disjoint-set union data structure, avoiding the explicit construction of the fundamental graph. Moreover, we show that our algorithm is asymptotically optimal by giving a lower bound based on a simple information-theoretic argument: any (deterministic or bounded-error randomized) algorithm to compute connected components needs $Ω(n \log{n})$ independence queries. Then, we turn to the query complexity of deciding whether a matroid is connected. For this problem, we present an algorithm that uses $O(nh)$ independence queries, where $h \ge 1$ bounds the size of any chain of nonempty proper cyclic flats. The algorithm achieves asymptotically optimal linear query complexity on elementary split matroids, that include all paving matroids, and on arbitrary direct sums of uniform matroids.

0.15