More results on the complexity of domination problems in graphs (Q1664084)

Summary: Given a graph \(G=(V,E)\) and an integer \(r\geq 1\), we call `\(r\)-dominating code' any subset \(C\) of \(V\) such that every vertex in \(V\) is at distance at most \(r\) from at least one vertex in \(C\). We investigate and locate in the complexity classes of the polynomial hierarchy, several problems linked with domination in graphs, such as, given \(r\) and \(G\), the existence of, or search for, optimal \(r\)-dominating codes in \(G\), or optimal \(r\)-dominating codes in \(G\) containing a subset of vertices \(X\subset V\).