Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts

Alexis Cornet (1) , Christian Laforest (1)

1 LIMOS - Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes

Total dominating set, connected vertex cover and Steiner tree are well-known graph problems. Despite the fact that they are NP-complete to optimize, it is easy (even trivial) to find solutions, regardless of their size. In this paper, we study a variant of these problems by adding conflicts, that are pairs of vertices that cannot be both in a solution. This new constraint leads to situations where it is NP-complete to decide if there exists a solution avoiding conflicts. This paper proposes NP-completeness proofs of the existence of a solution for different restricted classes of graphs and conflicts, improving recent results. We also propose polynomial time constructions in several restricted cases and we introduce a new parameter, the stretch, to capture the locality of the conflicts.

Mots clés: Graphs; conflicts

Domaines: Recherche opérationnelle [math.OC]

Alexis Cornet, Christian Laforest. Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts. [Research Report] LIMOS (UMR CNRS 6158), université Clermont Auvergne, France. 2017. ⟨hal-01455072v2⟩