On the relation of strong triadic closure and cluster deletion

Author name not available (Why is that?)

Abstract: 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_{3}

s by a minimum number of edge deletions. We first show that Strong Triadic Closure admits a

4 k

-vertex kernel. Then, we study parameterization by

e l l : = | E | - k

and show that both problems are fixed-parameter tractable and unlikely to admit a polynomial kernel with respect to

e l l

. Finally, we give a dichotomy of the classical complexity of both problems on

H

-free graphs for all

H

of order four.

No records found.

No records found.

This page was built for publication: On the relation of strong triadic closure and cluster deletion