Maximizing the strong triadic closure in split graphs and proper interval graphs
From MaRDI portal
Publication:2197407
Graph algorithms (graph-theoretic aspects) (05C85) Social networks; opinion dynamics (91D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Abstract: In social networks the {sc Strong Triadic Closure} is an assignment of the edges with strong or weak labels such that any two vertices that have a common neighbor with a strong edge are adjacent. The problem of maximizing the number of strong edges that satisfy the strong triadic closure was recently shown to be NP-complete for general graphs. Here we initiate the study of graph classes for which the problem is solvable. We show that the problem admits a polynomial-time algorithm for two unrelated classes of graphs: proper interval graphs and trivially-perfect graphs. To complement our result, we show that the problem remains NP-complete on split graphs, and consequently also on chordal graphs. Thus we contribute to define the first border between graph classes on which the problem is polynomially solvable and on which it remains NP-complete.
Recommendations
Cites work
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- scientific article; zbMATH DE number 3307330 (Why is no real title available?)
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Applying modular decomposition to parameterized cluster editing problems
- Bipartite roots of graphs
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- Complement reducible graphs
- Complexity of the cluster deletion problem on subclasses of chordal graphs
- Computing square roots of trivially perfect and threshold graphs
- Computing the Bandwidth of Interval Graphs
- Gallai graphs and anti-Gallai graphs
- Generalized graph clustering: recognizing \((p,q)\)-cluster graphs
- Graph Classes: A Survey
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Networks, crowds and markets. Reasoning about a highly connected world.
- Optimal greedy algorithms for indifference graphs
- Parameterized algorithms for finding square roots
- Paths, Trees, and Flowers
- Recognizing Powers of Proper Interval, Split, and Chordal Graphs
- Reducibility among combinatorial problems
- Social and economic networks.
- The clique-separator graph for chordal graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Tree decompositions and social graphs
- Trivially perfect graphs
Cited in
(10)- Cluster deletion on interval graphs and split related graphs
- Parameterized aspects of strong subgraph closure
- Parameterized aspects of strong subgraph closure
- Maximizing the strong triadic closure in split graphs and proper interval graphs
- A survey of the studies on Gallai and anti-Gallai graphs
- Strong triadic closure in cographs and graphs of low maximum degree
- Relaxing the strong triadic closure problem for edge strength inference
- Strong triadic closure in cographs and graphs of low maximum degree
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
- Structural parameterization of cluster deletion
This page was built for publication: Maximizing the strong triadic closure in split graphs and proper interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197407)
