On identifying codes on oriented graphs
Soura Sena Das, Sagnik Sen
Source 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$.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.