Alexis Cornet ; Christian Laforest - Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts

dmtcs:3128 - Discrete Mathematics & Theoretical Computer Science, December 20, 2017, Vol. 19 no. 3 - https://doi.org/10.23638/DMTCS-19-3-17
Total Domination, Connected Vertex Cover and Steiner Tree with ConflictsArticle

Authors: Alexis Cornet 1; Christian Laforest 1

  • 1 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.


Volume: Vol. 19 no. 3
Section: Graph Theory
Published on: December 20, 2017
Accepted on: December 8, 2017
Submitted on: February 9, 2017
Keywords: NP- completeness,Steiner tree,total dominating set,graph theory,conflicts,connected vertex cover,forbidden pairs,Graphs, conflicts,[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO]

Consultation statistics

This page has been seen 599 times.
This article's PDF has been downloaded 814 times.