We study the parameterized and classical complexity of two related problems on undirected graphs G = (V, E). In Strong Triadic Closure we aim to label the edges in E as strong and weak such that at most k edges are weak and G contains no induced P_3 with two strong edges. In Cluster Deletion we aim to destroy all induced P_3s by a minimum number of edge deletions. We first show that Strong Triadic Closure admits a 4k-vertex kernel. Then, we study parameterization by ℓ := |E| - k and show that both problems are fixed-parameter tractable and unlikely to admit a polynomial kernel with respect to ℓ. Finally, we give a dichotomy of the classical complexity of both problems on H-free graphs for all H of order four.
展开▼
机译：我们在无向图G =（V，E）上研究了两个相关问题的参数化和经典复杂度。在“强三合会闭合”中，我们旨在将E中的边缘标记为强和弱，这样最多k个边缘是弱的，而G不包含带有两个强边缘的诱导P_3。在簇删除中，我们旨在通过最少数量的边缘删除来破坏所有诱导的P_3。我们首先显示“强三合会封闭”接受4k顶点内核。然后，我们通过ℓ：= | E |研究参数化。 -k并且表明这两个问题都是固定参数可处理的，并且不太可能接受关于ℓ的多项式核。最后，我们对所有四阶H的无H图上的两个问题的经典复杂度作了二分法。
展开▼
