Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts
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 ar...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2017-12-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3128/pdf |
| _version_ | 1797270058514251776 |
|---|---|
| author | Alexis Cornet Christian Laforest |
| author_facet | Alexis Cornet Christian Laforest |
| author_sort | Alexis Cornet |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:58:14Z |
| format | Article |
| id | doaj.art-233523eef0c84d108ab9b4b9f706cc92 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:14Z |
| publishDate | 2017-12-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-233523eef0c84d108ab9b4b9f706cc922024-03-07T15:34:16ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502017-12-01Vol. 19 no. 3Graph Theory10.23638/DMTCS-19-3-173128Total Domination, Connected Vertex Cover and Steiner Tree with ConflictsAlexis Cornet0Christian Laforest1Laboratoire d'Informatique, de Modélisation et d'optimisation des SystèmesLaboratoire d'Informatique, de Modélisation et d'optimisation des SystèmesTotal 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.https://dmtcs.episciences.org/3128/pdfnp- completenesssteiner treetotal dominating setgraph theoryconflictsconnected vertex coverforbidden pairsgraphsconflicts[info.info-ro] computer science [cs]/operations research [cs.ro] |
| spellingShingle | Alexis Cornet Christian Laforest Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts Discrete Mathematics & Theoretical Computer Science 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] |
| title | Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts |
| title_full | Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts |
| title_fullStr | Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts |
| title_full_unstemmed | Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts |
| title_short | Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts |
| title_sort | total domination connected vertex cover and steiner tree with conflicts |
| topic | 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] |
| url | https://dmtcs.episciences.org/3128/pdf |
| work_keys_str_mv | AT alexiscornet totaldominationconnectedvertexcoverandsteinertreewithconflicts AT christianlaforest totaldominationconnectedvertexcoverandsteinertreewithconflicts |