Abstract
Motivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized study of the StrongF-closure problem, where F is a fixed graph. This is a generalization of Strong Triadic Closure, whereas it is a relaxation of F-free Edge Deletion. In StrongF-closure, we want to select a maximum number of edges of the input graph G, and mark them as strong edges, in the following way: whenever a subset of the strong edges forms a subgraph isomorphic to F, then the corresponding induced subgraph of G is not isomorphic to F. Hence, the subgraph of G defined by the strong edges is not necessarily F-free, but whenever it contains a copy of F, there are additional edges in G to forbid that strong copy of F in G. We study StrongF-closure from a parameterized perspective with various natural parameterizations. Our main focus is on the number k of strong edges as the parameter. We show that the problem is FPT with this parameterization for every fixed graph F, whereas it does not admit a polynomial kernel even when \(F =P_3\). In fact, this latter case is equivalent to the Strong Triadic Closure problem, which motivates us to study this problem on input graphs belonging to well known graph classes. We show that Strong Triadic Closure does not admit a polynomial kernel even when the input graph is a split graph, whereas it admits a polynomial kernel when the input graph is planar, and even d-degenerate. Furthermore, on graphs of maximum degree at most 4, we show that Strong Triadic Closure is FPT with the above guarantee parameterization \(k - \mu (G)\), where \(\mu (G)\) is the maximum matching size of G. We conclude with some results on the parameterization of StrongF-closure by the number of edges of G that are not selected as strong.
Similar content being viewed by others
Notes
NP-completeness result for \(F=P_3\) restricted to planar graphs (and, thus, 5-degenerate graphs) is given in Sect. 5.
References
Abu-Khzam, F.N.: A kernelization algorithm for d-Hitting set. J. Comput. Syst. Sci. 76, 524–531 (2010)
Alon, N., Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: Solving MAX-r-SAT above a tight lower bound. Algorithmica 61, 638–655 (2011)
Backstrom, L., Kleinberg, J.: Romantic partnerships and the dispersion of social ties: a network analysis of relationship status on facebook. In: CSCW 2014, pp. 831–841 (2014)
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75, 423–434 (2009)
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28, 277–305 (2014)
Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58, 171–176 (1996)
Cai, L., Cai, Y.: Incompressibility of \(H\)-free edge modification problems. Algorithmica 71, 731–757 (2015)
Cai, L., Chan, S., Chan, S.: Random separation: a new method for solving fixed-cardinality optimization problems. In: IWPEC 2006, pp. 239–250 (2006)
Chitnis, R., Cygan, M., Hajiaghayi, M., Pilipczuk, M., Pilipczuk, M.: Designing FPT algorithms for cut problems using randomized contractions. SIAM J. Comput. 45, 1171–1229 (2016)
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Berlin (2012)
Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and ids. ACM Trans. Algorithms 11, 13:1–13:20 (2014)
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)
Dyer, M.E., Frieze, A.M.: Planar 3DM is NP-complete. J. Algorithms 7, 174–184 (1986)
Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, Cambridge (2010)
Golovach, P. A., Heggernes, P., Konstantinidis, A. L., Lima, P. T., Papadopoulos, C.: Parameterized aspects of strong subgraph closure. In: SWAT 2018, pp. 23:1–23:13 (2018)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics. Elsevier, Amsterdam (2004)
Grüttemeier, N., Komusiewicz, C.: On the relation of strong triadic closure and cluster deletion. In: WG 2018, volume 11159 of Lecture Notes in Computer Science, pp. 239–251. Springer (2018)
Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci. 289, 997–1008 (2002)
Kleinberg, J.M., Tardos, É.: Algorithm Design. Addison-Wesley, Boston (2006)
Konstantinidis, A. L., Nikolopoulos, S. D., Papadopoulos, C.: Strong triadic closure in cographs and graphs of low maximum degree. In: COCOON 2017, pp. 346–358 (2017)
Konstantinidis, A. L., Papadopoulos, C.: Maximizing the strong triadic closure in split graphs and proper interval graphs. In: ISAAC 2017, pp. 53:1–53:12 (2017)
Kratsch, S., Wahlstrom, M.: Two edge modification problems without polynomial kernels. Discrete Optim. 10, 193–199 (2013)
Micali, S., Vazirani, V. V.: An \(O(\sqrt{|V|} |E|)\) algorithm for finding maximum matching in general graphs. In: FOCS 1980, pp. 17–27 (1980)
Sintos, S., Tsaparas, P.: Using strong triadic closure to characterize ties in social networks. In: KDD 2014, pp. 1466–1475 (2014)
Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10, 297–309 (1981)
Acknowledgements
We thank the reviewers for their valuable comments that helped improve the presentation of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
A preliminary version of this paper appeared as an extended abstract in the proceedings of SWAT 2018 [16]. This work is supported by Research Council of Norway via project “CLASSIS”.
The research work done by A. L. Konstantinidis is co-financed by Greece and the European Union (European Social Fund – ESF) through the Operational Programme “Human Resources Development, Education and Lifelong Learning” in the context of the project “Strengthening Human Resources Research Potential via Doctorate Research” (MIS–5000432), implemented by the State Scholarships Foundation (IKY). The research work done by C. Papadopoulos was supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the “First Call for H.F.R.I. Research Projects to support Faculty members and Researchers and the procurement of high-cost research equipment grant” (Project Number: 431).
Rights and permissions
About this article
Cite this article
Golovach, P.A., Heggernes, P., Konstantinidis, A.L. et al. Parameterized Aspects of Strong Subgraph Closure. Algorithmica 82, 2006–2038 (2020). https://doi.org/10.1007/s00453-020-00684-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-020-00684-9