Parameterized aspects of strong subgraph closure
From MaRDI portal
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 F-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 Strong F-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 destroy that strong copy of F in G. We study Strong F-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 Strong F-closure by the number of edges of G that are not selected as strong.
Recommendations
Cites work
- A kernelization algorithm for \(d\)-hitting set
- Algorithmic graph theory and perfect graphs
- Designing FPT algorithms for cut problems using randomized contractions
- Edge-Deletion Problems
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Fundamentals of parameterized complexity
- Incompressibility of \(H\)-free edge modification problems
- Kernelization Lower Bounds by Cross-Composition
- Kernelization lower bounds through colors and IDs
- Maximizing the strong triadic closure in split graphs and proper interval graphs
- Networks, crowds and markets. Reasoning about a highly connected world.
- On problems without polynomial kernels
- Parameterized algorithms
- Parameterized aspects of strong subgraph closure
- Parameterized complexity of finding subgraphs with hereditary properties.
- Planar 3DM is NP-complete
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Solving MAX-\(r\)-SAT above a tight lower bound
- Strong triadic closure in cographs and graphs of low maximum degree
- Two edge modification problems without polynomial kernels
Cited in
(6)- Cluster deletion on interval graphs and split related graphs
- Parameterized aspects of strong subgraph closure
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
- A survey of parameterized algorithms and the complexity of edge modification
- When can cluster deletion with bounded weights be solved efficiently?
- When can cluster deletion with bounded weights be solved efficiently?
This page was built for publication: Parameterized aspects of strong subgraph closure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2182097)
