Some Rainbow Problems in Graphs Have Complexity Equivalent to Satisfiability Problems
International Transactions in Operational Research, Vol. 29(3), pp. 1547-1572, 2022.
Olivier HUDRY (#) & Antoine LOBSTEIN (*)
(#) Département Informatique et Réseaux, LTCI,
Télécom ParisTech, Université Paris-Saclay,
46 rue Barrault, 75634 Paris Cedex 13 - France
olivier.hudry@telecom-paristech.fr
(*) Centre National de la Recherche Scientifique,
Laboratoire de Recherche en Informatique, UMR 8623,
Université Paris-Sud, Université Paris-Saclay,
Bâtiment 650 Ada Lovelace, 91405 Orsay Cedex - France
antoine.lobstein@lri.fr
Abstract. In a vertex-colored graph, a set of vertices S is said to be a rainbow set if every color in the graph appears exactly once in S. We investigate the complexities of various problems dealing with domination in vertex-colored graphs (existence of rainbow dominating sets, of rainbow locating-dominating sets, and of rainbow identifying sets), including when we ask for a unique solution: we show equivalence between these complexities and those of the well-studied Boolean satisfiability problems.