Some rainbow problems in graphs have complexity equivalent to satisfiability problems

Research output: Contribution to journalArticlepeer-review

Abstract

In a vertex-colored graph, a set of vertices (Formula presented.) is said to be a rainbow set if every color in the graph appears exactly once in (Formula presented.). 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.

Original languageEnglish
Pages (from-to)1547-1572
Number of pages26
JournalInternational Transactions in Operational Research
Volume29
Issue number3
DOIs
Publication statusPublished - 1 May 2022

Keywords

  • complexity theory
  • dominating codes
  • graph theory
  • identifying codes
  • locating-dominating codes
  • rainbow sets
  • twin-free graphs
  • uniqueness of solution

Fingerprint

Dive into the research topics of 'Some rainbow problems in graphs have complexity equivalent to satisfiability problems'. Together they form a unique fingerprint.

Cite this