Golovach, Petr A. ;
Heggernes, Pinar ;
Konstantinidis, Athanasios L. ;
Lima, Paloma T. ;
Papadopoulos, Charis
Parameterized Aspects of Strong Subgraph Closure
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 Strong Fclosure problem, where F is a fixed graph. This is a generalization of Strong Triadic Closure, whereas it is a relaxation of Ffree Edge Deletion. In Strong Fclosure, 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 Ffree, but whenever it contains a copy of F, there are additional edges in G to destroy that strong copy of F in G.
We study Strong Fclosure 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 ddegenerate. 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 Strong Fclosure by the number of edges of G that are not selected as strong.
BibTeX  Entry
@InProceedings{golovach_et_al:LIPIcs:2018:8849,
author = {Petr A. Golovach and Pinar Heggernes and Athanasios L. Konstantinidis and Paloma T. Lima and Charis Papadopoulos},
title = {{Parameterized Aspects of Strong Subgraph Closure}},
booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
pages = {23:123:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770682},
ISSN = {18688969},
year = {2018},
volume = {101},
editor = {David Eppstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8849},
URN = {urn:nbn:de:0030drops88490},
doi = {10.4230/LIPIcs.SWAT.2018.23},
annote = {Keywords: Strong triadic closure, Parameterized complexity, Forbidden subgraphs}
}
04.06.2018
Keywords: 

Strong triadic closure, Parameterized complexity, Forbidden subgraphs 
Seminar: 

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Issue date: 

2018 
Date of publication: 

04.06.2018 