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 4k-vertex kernel. Then, we study parameterization by \(\ell :=|E|-k\) and show that both problems are fixed-parameter tractable and unlikely to admit a polynomial kernel with respect to \(\ell \). Finally, we give a dichotomy of the classical complexity of both problems on H-free graphs for all H of order four.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Böcker, S., Damaschke, P.: Even faster parameterized cluster deletion and cluster editing. Inf. Process. Lett. 111(14), 717–721 (2011)
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discret. Math. 28(1), 277–305 (2014)
Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570–4578 (2011)
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey, vol. 3. SIAM, Philadelphia (1999)
Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013). https://doi.org/10.1007/978-1-4471-5559-1
Gao, Y., Hare, D.R., Nastos, J.: The cluster deletion problem for cographs. Discret. Math. 313(23), 2763–2771 (2013)
Golovach, P.A., Heggernes, P., Konstantinidis, A.L., Lima, P.T., Papadopoulos, C.: Parameterized Aspects of Strong Subgraph Closure. ArXiv e-prints, abs/1802.10386, February 2018
Guo, J.: A more effective linear kernelization for cluster editing. Theor. Comput. Sci. 410(8–10), 718–726 (2009)
Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718–720 (1981)
Hsu, W.-L., Ma, T.-H.: Substitution decomposition on chordal graphs and applications. In: Hsu, W.-L., Lee, R.C.T. (eds.) ISA 1991. LNCS, vol. 557, pp. 52–60. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-54945-5_49
Komusiewicz, C., Uhlmann, J.: Cluster editing with locally bounded modifications. Discret. Appl. Math. 160(15), 2259–2270 (2012)
Konstantinidis, A.L., Nikolopoulos, S.D., Papadopoulos, C.: Strong triadic closure in cographs and graphs of low maximum degree. In: Cao, Y., Chen, J. (eds.) COCOON 2017. LNCS, vol. 10392, pp. 346–358. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62389-4_29
Konstantinidis, A.L., Papadopoulos, C.: Maximizing the strong triadic closure in split graphs and proper interval graphs. In: Proceedings of the 28th ISAAC. LIPIcs, Dagstuhl, Germany, vol. 92, pp. 53:1–53:12. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)
Poljak, S.: A note on stable sets and colorings of graphs. Commentationes Mathematicae Universitatis Carolinae 15(2), 307–309 (1974)
Protti, F., da Silva, M.D., Szwarcfiter, J.L.: Applying modular decomposition to parameterized cluster editing problems. Theory Comput. Syst. 44(1), 91–104 (2009)
Sbihi, N.: Algorithme de recherche d’un stable de cardinalite maximum dans un graphe sans etoile. Discret. Math. 29(1), 53–76 (1980)
Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discret. Appl. Math. 144(1–2), 173–182 (2004)
Sintos, S., Tsaparas, P.: Using strong triadic closure to characterize ties in social networks. In: Proceedigns of the 20th KDD, pp. 1466–1475. ACM, New York (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Grüttemeier, N., Komusiewicz, C. (2018). On the Relation of Strong Triadic Closure and Cluster Deletion. In: Brandstädt, A., Köhler, E., Meer, K. (eds) Graph-Theoretic Concepts in Computer Science. WG 2018. Lecture Notes in Computer Science(), vol 11159. Springer, Cham. https://doi.org/10.1007/978-3-030-00256-5_20
Download citation
DOI: https://doi.org/10.1007/978-3-030-00256-5_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-00255-8
Online ISBN: 978-3-030-00256-5
eBook Packages: Computer ScienceComputer Science (R0)