Maximizing the strong triadic closure in split graphs and proper interval graphs

DOI10.1016/J.DAM.2020.05.035zbMATH Open1446.05080arXiv1609.09433OpenAlexW2964183795MaRDI QIDQ2197407FDOQ2197407

Charis Papadopoulos, Athanasios L. Konstantinidis

Publication date: 31 August 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1609.09433

Recommendations

• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Strong triadic closure in cographs and graphs of low maximum degree
• Strong triadic closure in cographs and graphs of low maximum degree
• On the relation of strong triadic closure and cluster deletion
• On the relation of strong triadic closure and cluster deletion

zbMATH Keywords

NP-completenesspolynomial-time algorithmproper interval graphssplit graphsstrong triadic closure

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Applying modular decomposition to parameterized cluster editing problems
• Social and economic networks.
• Graph Classes: A Survey
• Paths, Trees, and Flowers
• Complement reducible graphs
• Optimal greedy algorithms for indifference graphs
• Computing square roots of trivially perfect and threshold graphs
• Parameterized algorithms for finding square roots
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Bipartite roots of graphs
• Title not available (Why is that?)
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs
• Title not available (Why is that?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Trivially perfect graphs
• The clique-separator graph for chordal graphs
• Computing the Bandwidth of Interval Graphs
• Gallai graphs and anti-Gallai graphs
• Generalized Graph Clustering: Recognizing (p,q)-Cluster Graphs
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• Tree decompositions and social graphs

Cited In (5)

• A survey of the studies on Gallai and anti-Gallai graphs
• Strong triadic closure in cographs and graphs of low maximum degree
• Cluster deletion on interval graphs and split related graphs
• Structural parameterization of cluster deletion
• Your rugby mates don't need to know your colleagues: triadic closure with edge colors

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)