On the minimum size of an identifying code over all orientations of a graph (Q1753015)

Summary: If \(G\) be a graph or a digraph, let \(\mathrm{id}(G)\) be the minimum size of an identifying code of \(G\) if one exists, and \(\mathrm{id}(G)=+\infty\) otherwise. For a graph \(G\), let \(\mathrm{idor}(G)\) be the minimum of \(\mathrm{id}(D)\) overall orientations \(D\) of \(G\). We give some lower and upper bounds on \(\mathrm{idor}(G)\). In particular, we show that \(\mathrm{idor}(G)\leqslant \frac{3}{2} \mathrm{id}(G)\) for every graph \(G\). We also show that computing \(\mathrm{idor}(G)\) is NP-hard, while deciding whether \(\mathrm{idor}(G)\leqslant |V(G)|-k\) is polynomial-time solvable for every fixed integer \(k\).