论文标题
阻塞（半）总统治与边缘收缩的复杂性
The complexity of blocking (semi)total dominating sets with edge contractions
论文作者
论文摘要
我们考虑通过收缩边缘将（半）总统治数减少（半）总统治数的问题。众所周知，这始终可以用最多三个边缘收缩来完成，并且决定一个边缘收缩是否足够的是$ \ mathsf {np} $ - 硬问题。我们表明，对于\ {2,3 \} $中的每一个固定的$ k \，确定是否确切必要的$ k $ edge收缩是$ \ mthsf {np} $ - 硬且进一步提供$ k = 2 $完整的复杂性二分法。
We consider the problem of reducing the (semi)total domination number of 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 $\mathsf{NP}$-hard problem. We show that for every fixed $k \in \{2,3\}$, deciding whether exactly $k$ edge contractions are necessary is $\mathsf{NP}$-hard and further provide for $k=2$ complete complexity dichotomies on monogenic graph classes.
