Publisher DOI: | 10.1016/j.tcs.2022.12.028 | Title: | The complexity of blocking (semi)total dominating sets with edge contractions | Language: | English | Authors: | Galby, Esther | Keywords: | Blocker problem; Edge contraction; H-free graphs; Semitotal domination number; Total domination number | Issue Date: | 13-Jan-2023 | Publisher: | Elsevier | Source: | Theoretical Computer Science (2023) | Abstract (english): | We consider the problem of reducing the (semi)total domination number of a graph by one by contracting edges. It is known that this can always be done with at most three edge contractions and that deciding whether one edge contraction suffices is an NP-hard problem. We show that for every fixed k∈2,3, deciding whether exactly k edge contractions are necessary is NP-hard and further provide for k=2 complete complexity dichotomies on monogenic graph classes. |
URI: | http://hdl.handle.net/11420/15025 | ISSN: | 0304-3975 | Journal: | Theoretical computer science | Institute: | Algorithmen und Komplexität E-11 | Document Type: | Article |
Appears in Collections: | Publications without fulltext |
Show full item record
Google ScholarTM
Check
Add Files to Item
Note about this record
Cite this record
Export
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.