Source-linked AI summary
On identifying codes on oriented graphs
Soura Sena Das, Sagnik Sen
TL;DR
The paper asks when a specified vertex subset can become an oriented identifying code under some orientation, with the induced code subgraph constrained to a graph family. It analyzes d-regular families through complexity arguments and proves a complete dichotomy: polynomial time for d≤1 and NP-complete for d≥2. The result also yields NP-completeness for several broader graph families.
Problem
The paper studies the computational complexity of deciding whether a given subset C inducing a graph from F can become an oriented identifying code of G.
Method
The paper analyzes F-Id Code for d-regular graph families and uses polynomial-time reasoning for low degrees alongside a reduction from (3,4)-SAT for the NP-hard cases.
Results
The F_d-Id Code problem is polynomial-time solvable for d≤1 and NP-complete for d≥2.
Takeaways & Limitations
The complexity boundary occurs at d=2, and the results imply NP-completeness for bipartite, outerplanar, partial 2-tree, planar, and bounded-maximum-degree graph families.
Takeaways & Limitations
The low-degree polynomial-time argument assumes that a 1-regular induced code subgraph is a disjoint union of K2s.
Abstract
from arXiv · showhide
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$.
1 Introduction
The paper studies when a vertex subset can serve as an oriented identifying code after orienting an underlying graph, focusing on the complexity of this decision problem. For d-regular induced code subgraphs, it establishes a complete tractability dichotomy at d=2.
- Identifying codes require every vertex to have a non-empty, distinct set of adjacent codewords, including itself.
- The F-Id Code problem asks whether a graph G can be oriented so that a given subset C, inducing a graph from F, becomes an oriented identifying code.
- Earlier work established NP-completeness for all simple graphs but polynomial-time solvability for sufficiently sparse graph families.
- The paper studies F_d-Id Code for families of d-regular graphs and finds polynomial-time solvability for d≤1 and NP-completeness for d≥2.
- This threshold implies NP-completeness for several graph families, including bipartite, outerplanar, partial 2-tree, planar, and bounded-maximum-degree graphs.
2 Proof of Theorem 1.2
The proof establishes a complexity dichotomy for d-regular induced subgraphs: the problem is polynomial-time solvable for d≤1 and NP-complete for d≥2. The polynomial case uses matching-based orientation, while hardness for d=2 comes from a linear-size reduction and extends to all d≥3.
- Polynomial cases: The F1-Id Code problem is polynomial-time solvable when the induced subgraph G[C] is 1-regular.Such an induced graph can be assumed to be a disjoint union of k copies of K2.
- Polynomial cases: A matching saturating the non-codeword side of the auxiliary bipartite graph determines orientations that give distinct identifiers to the vertices of G* and can then be extended to G.If no such matching exists, C is not an oriented identifying code; the auxiliary graph has O(|V(G)|^2) vertices.
- Hardness for d≥3: NP-completeness extends to all d≥3, yielding the stated dichotomy for d-regular graph families.The extension uses the NP-completeness of the B2-Id Code problem and preserves equivalence while keeping |V(G*)| = O(|V(G)|).