{"id":"arxiv/2608.26593","url":"https://arxiv.org/abs/2608.26593","tags":["cs.DM","math.CO"],"score":0,"title":"On identifying codes on oriented graphs","domain":"cs.DM","source":"arxiv","authors":["Soura Sena Das","Sagnik Sen"],"reviews":0,"subject":"cs.DM","summary":"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$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-27","reactions":{}}