CS Paper Radar

On the Vertices That Belong to All Minimum Identifying Codes

Ville Junnila, Tero Laihonen, Havu Miikonen

cs.DM math.CO ·submitted 2026-09-09 08:06 UTC · v1
theory

Abstract

Identifying codes in graphs have been widely studied since their introduction by Karpovsky, Chakrabarty and Levitin in 1998. In this paper, we consider the vertices that are in every minimum identifying code in a graph. There are two types of such vertices: \emph{always-forced} vertices that belong to all identifying codes (minimum or not) and \emph{min-forced} vertices that belong to all minimum identifying codes. A vertex is called \emph{proper-min-forced} if it is min-forced but not always-forced. We show an upper bound $2n/3$ for the number of such proper-min-forced vertices in a closed-twin-free graph of order $n$. Moreover, for integers $n$ divisible by three, we construct an infinite family of graphs in which there are $2n/3-1$ such vertices. In addition, we determine the maximum number of edges in a graph of even order such that the graph contains proper-min-forced vertices. We also show that the decision problem of determining whether a given vertex in a graph is proper-min-forced is co-NP-hard.

Closest papers

Nearest neighbours by meaning across the whole index.

On identifying codes on oriented graphs

cs.DM math.CO ·2026-08-27 ·Soura Sena Das, Sagnik Sen
similarity 0.70
Abstract

This article studies identifying codes in oriented graphs from a computational complexity perspective. We investigate the $\mathcal{F}$-Id Code problem, where given a simple graph $G$ and a vertex subset $C$, which induces a subgraph in the family $\mathcal{F}$, as inputs and ask whether it is possible to orient $G$ in such a way that $C$ becomes its oriented identifying code. Focusing on the family $\mathcal{F}_d$ of $d$-regular graphs, we establish a complete dichotomy by proving that the problem is polynomial-time solvable for $d\leq1$ and NP-complete for all $d\geq2$.

0.14

Minimality of Binary Codes From Weight Layers and Graph Cut Spaces

cs.IT ·2026-10-26 ·Xianhong Xie, Mengni Wang, Tingting Wu
similarity 0.66
Abstract

Minimal binary linear codes play an important role in secret-sharing schemes and in the structural study of linear codes. We study the minimality of three classes of known constructions: codes from a single complete Hamming-weight layer, codes from arbitrary unions of such layers and graph cut-space codes. For the previously studied single-layer codes C, we give a complete minimality classification: C is minimal if and only if t is even. For t = 4, we determine the minimum and maximum weights, and show that the family strictly violates the binary Ashikhmin Barg sufficient condition for every k. We also calculate the minimum distance of the dual code. For arbitrary unions of complete Hamming-weight layers, we obtain an if-and-only-if classification of minimality and uniform criteria for evenness, self-orthogonality, the doubly even property and hull dimension. We further analyze the family for odd k. Finally, using the classical bond characterization of cuts, we translate minimality of graph cut space codes into a graph-theoretic condition: a nonempty simple graph has a minimal cut code precisely when it has one edge-containing component and that component is complete. We also give a graph-function realization of the known binary tetrahedron code and explicitly identify the resulting code equivalence.

0.24

Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality

cs.IT math.CO ·2026-09-01 ·Aryeh Lev Zabokritskiy
similarity 0.64
Abstract · 44 pages

Codes over graphs store symbols on edges of a complete undirected graph on $n$ vertices with a self-loop at each vertex; erasing a node removes all its incident edges. Extending Yohananov, Efron, and Yaakobi's construction, we obtain binary codes correcting any three node erasures at infinitely many prime lengths $n$, unconditionally, with redundancy $3n-2$, one bit above the graph Singleton bound. The earlier construction has the same redundancy but requires $2$ to be primitive modulo $n$, which is not known for infinitely many primes. We give a deterministic decoder for these triple-node codes using $O(n^2)$ binary operations and construct Singleton-optimal binary triple-node codes at $n=6,8,10,12$. When $2$ is primitive modulo an odd prime $n$, we extend their double- and triple-node codes to binary codes correcting $ρ$ node erasures with redundancy $ρn-(ρ-1)$ for $2\leqρ\leq(n+1)/2$, saving $ρ-1$ bits over the binary symmetric rank-metric construction when $ρ<(n+1)/2$. Over every finite field of size $q$, the node weight of a word is the least number of vertices whose erasure removes its support. We give exact formulas for ball volumes in this node metric and prove that, for fixed $q,t$, the radius-$t$ volume is asymptotic to $\binom nt q^{tn-\binom t2}$ as $n\to\infty$. We obtain existence and covering bounds; for fixed $q,ρ$, we show that linear $ρ$-node-erasure-correcting codes exist with redundancy at most $ρ\log_q n+O_{q,ρ}(1)$ above the graph Singleton bound. Finally, reformulating Yohananov and Yaakobi's criterion, we show that a linear code over any finite field is Singleton-optimal for $ρ$ node erasures if and only if its dual is Singleton-optimal for erasures of the coordinates inside any $n-ρ$ vertices.

0.31

Closing the Complexity Gap for Wheeler Graph Recognition on $d$-NFAs

cs.CC cs.FL ·2026-11-08 ·Kengo Hashimoto
theory similarity 0.63
Abstract

Wheeler graph recognition asks whether a directed graph whose arcs are labeled by symbols from a totally ordered alphabet admits a Wheeler order, a total order on its vertices compatible with the labels of arcs and the order of their tails. A $d$-NFA is a nondeterministic finite automaton in which at most $d$ transitions with any given label leave each state. For Wheeler graph recognition on $d$-NFAs, Alanko et al. gave a polynomial-time algorithm for $d \leq 2$, whereas Gibney and Thankachan proved NP-completeness for every fixed $d \geq 5$. The computational complexity for $d = 3$ and $d = 4$ remained open. We resolve both open cases by extending the reduction of Gibney and Thankachan with a new encoding of clauses of Not-All-Equal 3-SAT. Specifically, we prove that recognition is NP-complete even for directed acyclic graphs over an ordered binary alphabet with a unique source reaching every vertex and total out-degree at most three at every vertex. Consequently, Wheeler graph recognition on $d$-NFAs is NP-complete for every fixed $d \geq 3$.

0.22

Small classes have linear neighbourhood complexity

cs.DM math.CO ·2026-11-11 ·John Sylvester, Viktor Zamaraev, Maksim Zhukovskii
theory similarity 0.62
Abstract · 31 pages, 6 figures

A hereditary graph class is small if it contains at most $n!c^n$ labelled graphs on $n$ vertices for some constant $c$. Small classes include proper minor-closed classes and classes of bounded twin-width. We prove that every small class has linear neighbourhood complexity, that is, in every graph in the class, vertex neighbourhoods intersect any $k$-vertex set in only $O(k)$ distinct ways. This resolves a conjecture of Bonnet, Duron, and the first two authors (ITCS 2025) and makes the algorithmic, structural, and representation consequences of linear neighbourhood complexity available for every small class. In particular, every small class admits an adjacency labelling scheme with $O(\log^2 n)$-bit labels, improving the previous $O(\log^3 n)$ bound.

0.20

The Multiple Unicast Conjecture is False

cs.IT cs.CCcs.DMcs.DS ·2026-10-07 ·Mark Braverman, Zhongtian He
theoryhighly cited similarity 0.61
Abstract

The undirected multiple-unicast conjecture [LL04] asserts that network coding offers no throughput advantage over multicommodity flow. We refute this conjecture by constructing a deterministic linear network code over $\mathbb{F}_9$ on a 182-vertex bipartite subgraph of the point-line incidence graph of $\mathrm{PG}(2,9)$. The construction supports $157$ independent unicast sessions at common coding rate at least $1$, while every fractional multicommodity flow has common rate at most $147/157$. By the amplification theorem of~[BGS17], this yields a family of undirected multiple-unicast instances with coding gap $Ω((\log n)^\varepsilon)$ for some $\varepsilon>0$. We also introduce a nondeterministic model of network coding based on locally verifiable certificates, which guides our construction and may be of independent interest. Building on the high-girth graph and error-correcting code framework of [BH25], we use GPT-6 to find a nondeterministic counterexample based on a new choice of Reed--Solomon local codes, and then convert this example into a causal code using an edge orientation and local search.

0.38

Crown graphs maximise the representation number of bipartite graphs

cs.DM math.CO ·2026-09-24 ·Matthew J. Colbrook, Catherine Drysdale
theory similarity 0.60
Abstract

The representation number of a graph is the least positive integer $k$ for which its vertices can be arranged in a word, each occurring $k$ times, so that two distinct letters alternate precisely when the corresponding vertices are adjacent. We prove that every bipartite graph on $N\ge9$ vertices has representation number at most $\lceil N/4\rceil$. Together with the known representation number of crown graphs, this settles the conjecture that crowns maximise the representation number among bipartite graphs of the same order. The proof develops a construction of Mozhui and Krishna by reducing the choice of a representing word to an ordering problem for neighbourhoods. We characterise the obstructions to this ordering and use probability estimates to exclude them for all sufficiently large balanced bipartitions. Two finite assertions complete the argument, each established by a checked Boolean unsatisfiability certificate. A refinement of the ordering argument treats the remaining odd part sizes directly. The main theorem and the crown-extremality corollary, including the finite certificate arguments, have also been formalised and verified in Lean 4.

0.25

Perfect Italian Domination on and Near Split Graphs: Algorithms, Hardness, and Approximation

cs.DM ·2026-10-07 ·Anand Babu N B, Ashwin Jacob, Manjusha M S, Renjith P
similarity 0.59
Abstract · Submitted to CALDAM 2027

A perfect Italian dominating function assigns a label from $\{0,1,2\}$ to each vertex so that the labels in the neighborhood of every zero-labeled vertex sum to exactly two. Although the associated decision problem (PID) is NP-complete on chordal graphs, the complexity status on split graphs remains open. We give an $O(n^4)$ time algorithm for split graphs on $n$ vertices. We note that this is in contrast to Roman, Italian, and perfect Roman domination, which are NP-complete on split graphs. We further show that this tractability boundary is tight: PID is NP-hard on graphs at deletion distance one from split graphs. We also provide dichotomy results for PID on restricted extensions of split graphs formed by attaching pendant stars, and establish inapproximability results for the same.

0.09