Αλγόριθμοι και πολυπλοκότητα της ισχυρής τριαδικής κλειστότητας σε κλάσεις γραφημάτων
(EL)
Algorithms and complexity of strong triadic closure in graph classes
(EN)
Κωνσταντινίδης, Αθανάσιος
(EL)
Παπαδόπουλος, Χάρης
(EL)
Κωνσταντινίδης, Αθανάσιος
(EL)
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
(EL)
Στα κοινωνικά δίκτυα η Ισχυρη Τριαδικη κλειστοτητα είναι µία ανάθεση στις ακµές µε ισχυρές ή ασθενείς επιγραφές, τέτοια ώστε για δύο οποιεσδήποτε κορυ- φές που έχουν κοινό γείτονα µε ισχυρή ακµή να είναι γειτονικές. Το πρόβληµα της
µεγιστοποίησης των ισχυρών ακµών, οι οποίες ικανοποιούν την ισχυρή τριαδική κλειστότητα, έχει πρόσφατα αποδειχτεί ότι είναι NP-πλήρες σε γενικά γραφήµατα.
Στην παρούσα διατριβή γίνεται µελέτη σε κλάσεις γραφηµάτων, για τις οποίες το πρόβληµα χαρακτηρίζεται είτε µε πολυωνυµική λύση είτε παραµένει NP-πλήρες. 6είχνουµε ότι το πρόβληµα δέχεται πολυωνυµικό σε χρόνο αλγόριθµο σε δύο ανεξάρτητες κλάσεις γραφηµάτων των proper interval και των trivially-perfect, καθώς και στις κλάσεις των bipartite, co-bipartite και threshold γραφηµάτων. Για να έχουµε µια πιο κατηγοριοποιηµένη και ολοκληρωµένη αντίληψη των α- ποτελεσµάτων µας, δείχνουµε ότι το πρόβληµα παραµένει NP-πλήρες στα split γραφήµατα, και ακολούθως στα chordal γραφήµατα. Εποµένως, µέσα από την διατριβή αυτή συµβάλουµε να οριστούν τα πρώτα διαχωριστικά όρια µεταξύ των κλάσεων γραφηµάτων, όπου σε κάποιες κλάσεις το πρόβληµα λύνεται σε πολυω- νυµικό χρόνο ενώ σε άλλες κλάσεις το πρόβληµα παραµένει NP-πλήρες.
(EL)
In social networks the 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. In this thesis we initiate the
study of graph classes for which the problem is either polynomially solvable
or remains NP-complete. We show that the problem admits a polynomialtime
algorithm for two unrelated classes of graphs: proper interval graphs
and trivially-perfect graphs, as well as, on classes of bipartite graphs, cobipartite
graphs and threshold graphs. To complement our result, we show
that the problem remains NP-complete on split graphs, and consequently also
on chordal graphs. Thus in this thesis we contribute to define the first border
between graph classes on which the problem is polynomially solvable and on
which it remains NP-complete.
(EN)
