Some rainbow problems in graphs have complexity equivalent to satisfiability problems

Autor: Olivier Hudry, Antoine Lobstein
Přispěvatelé: Institut Polytechnique de Paris (IP Paris), Département Informatique et Réseaux (INFRES), Télécom ParisTech, Cybersécurité et Cryptographie (C2), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Télécom Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Mathématiques discrètes, Codage et Cryptographie (MC2), Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)
Rok vydání: 2020
Předmět:
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Twin-free graphs
Strategy and Management
Uniqueness of solution
0211 other engineering and technologies
02 engineering and technology
Management Science and Operations Research
Set (abstract data type)
Combinatorics
Identifying codes
Computer Science::Discrete Mathematics
Management of Technology and Innovation
0202 electrical engineering
electronic engineering
information engineering
[INFO]Computer Science [cs]
Locating-dominating codes
[MATH]Mathematics [math]
Business and International Management
Rainbow sets
Equivalence (measure theory)
ComputingMilieux_MISCELLANEOUS
Mathematics
Mathematics::Combinatorics
021103 operations research
Complexity theory
Dominating codes
Rainbow
Graph theory
16. Peace & justice
Graph
Satisfiability
Computer Science Applications
Graph Theory
020201 artificial intelligence & image processing
Boolean satisfiability problem
Zdroj: International Transactions in Operational Research
International Transactions in Operational Research, Wiley, 2022
International Transactions in Operational Research, 2022, 29 (3), pp.1547-1572
International Transactions in Operational Research, Wiley, In press
International Transactions in Operational Research, 2022
ISSN: 1475-3995
0969-6016
Popis: International audience; In a vertex-coloured graph, a set of vertices S is said to be a rainbow set if every colour in the graph appears exactly once in S. We investigate the complexities of various problems dealing with domination in vertex-coloured graphs (existence of rainbow dominating sets, of rainbow locating-dominating sets, 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.
Databáze: OpenAIRE
Externí odkaz: