Algorithms and complexity of graph modification problems

Abstract

Graph modification problems play important role in both structural and algorithmic graph theory. These problems have been studied for decades and find a large number of practical applications in several different fields in real world. In this thesis, we study a famous edge deletion problem, known under the terms Cluster Deletion or P3-free Edge Deletion, and we consider an edge labeling scheme that characterizes social networks in terms of an edge deletion problem, known as MaxSTC. Both problems are known to be NP-hard. We provide the first computational results of MaxSTC and we determine the computational complexity of Cluster Deletion on particular graph classes. Moreover, we generalize the MaxSTC problem and propose a relaxation of the classical F-free Edge Deletion problem that we call Strong F-Closure. We study Strong F-Closure from the parameterized perspective and provide computational results with various natural parameterizations.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 is known as MaxSTC and it was recently shown to be NP-complete for general graphs. Here we initiate the study of graph classes for which MaxSTC is solvable in polynomial time or NP-complete. On the positive side, we show that the problem admits a polynomial-time algorithm for the following incomparable classes of graphs: proper interval graphs, cographs, graphs with maximum degree 3, and graphs with bounded treewidth. To complement our result, we show that the problem remains NP-complete on the following graphs: split graphs, and consequently also on chordal graphs, graphs with maximum degree at most 4, planar graphs, and (3K1, 2K2)-free 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.Inspired by the close relative of MaxSTC, we consider the Cluster Deletion problem. The goal is to remove the minimum number of edges of a given graph, such that every connected component of the resulting graph constitutes a clique. It is known that the decision version of Cluster Deletion is NP-complete on (P5-free) chordal graphs, whereas Cluster Deletion is solved in polynomial time on split graphs. However, the existence of a polynomial-time algorithm of Cluster Deleition on interval graphs, a proper subclass of chordal graphs, remained a well-known open problem. Our main contribution is that we settle this problem in the affirmative, by providing a polynomial-time algorithm for Cluster Deletion on interval graphs. Moreover, despite the simple formulation of a polynomial-time algorithm on split graphs, we show that Cluster Deletion remains NP-complete on a natural and slight generalization of split graphs that constitutes a proper subclass of P5-free chordal graphs. To complement our results, we provide faster and simpler polynomial-time algorithms for Cluster Deletion on subclasses of such a generalization of split graphs.Furthermore we introduce and initiate the parameterized study of the Strong F-closure problem, for a fixed graph F, which a natural generalization of MaxSTC. The goal is 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 forbid that strong copy of F in G. Therefore Strong F-closure is a generalization of MaxSTC, whereas it is a relaxation of F-free Edge Deletion. 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 = P3. In fact, this latter case is equivalent to the MaxSTC problem, which motivates us to study this problem on input graphs belonging to well known graph classes. We show that MaxSTC 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 MaxSTC is FPT with the above guarantee parameterization k − μ(G), where μ(G) is the maximum matching size of G. We conclude with some results on the arameterization of Strong F-closure by the number of weak edges of G.

Τα προβλήματα επεξεργασίας γραφημάτων παίζουν σημαντικό ρόλο τόσο στην δομική όσο και στην αλγοριθμική θεωρία γραφημάτων. Τα προβλήματα αυτά έχουν μελετηθεί για δεκαετίες και βρίσκουν πρακτικές εφαρμογές σε σημαντικές περιοχές έρευνας. Σε αυτήν την διατριβή μελετάμε ένα κλασικό πρόβλημα επεξεργασίας ακμών, γνωστό ως Cluster Deletion ή P3-free Edge Deletion, και εξετάζουμε έναν κανόνα επιγραφής ακμών ο οποίος χαρακτηρίζει τα κοινωνικά δίκτυα, ως ένα πρόβλημα διαγραφής ακμών, γνωστό ως MaxSTC. Τα δύο αυτά προβλήματα είναι γνωστό ότι είναι NP-δύσκολα. Παρέχουμε τα πρώτα υπολογιστικά αποτελέσματα για το MaxSTC και καθορίζουμε την υπολογιστική πολυπλοκότητα για το Cluster Deletion σε κλάσεις γραφημάτων. Επιπλέον, γενικεύουμε το πρόβλημα MaxSTC προτείνοντας μία “χαλάρωση” του κλασικού προβλήματος επεξεργασίας ακμών F-free Edge Deletion, το οποίο καλούμε Strong F-Closure. Μελετάμε το πρόβλημα Strong F-Closure από την σκοπιά της παραμετρικής πολυπλοκότητας και παρέχουμε τα πρώτα υπολογιστικά αποτελέσματα υπό διαφορετικούς παραμέτρους.Στα κοινωνικά δίκτυα η Ισχυρή Τριαδική Κλειστότητα είναι μία ανάθεση επιγραφών στις ακμές ως ισχυρές ή ασθενείς ακμές, έτσι ώστε για οποιεσδήποτε δύο κορυφές οι οποίες έχουν ένα κοινό γείτονα με ισχυρή ακμή είναι γειτονικές μεταξύ τους (είτε με ισχυρή είτε με ασθενή ακμή). Το πρόβλημα μεγιστοποίησης του αριθμού των ισχυρών ακμών οι οποίες να ικανοποιούν την ισχυρή τριαδική κλειστότητα είναι γνωστό ως MaxSTC και έχει δειχθεί πρόσφατα ότι είναι NP-πλήρες σε γενικά γραφήματα. Σε αυτή διατριβή επικεντρωνόμαστε σε κλάσεις γραφημάτων με την συστηματική μελέτη για τις οποίες το πρόβλημα MaxSTC είναι επιλύσιμο σε πολυωνυμικό χρόνο ή παραμένει NP-πλήρες. Από την θετική σκοπιά των υπολογιστικών αποτελεσμάτων, δείχνουμε ότι το πρόβλημα επιδέχεται πολυωνυμικού χρόνου αλγόριθμο στις ακόλουθες μη-συγκρίσιμες κλάσεις γραφημάτων: proper interval γραφήματα, cographs, γραφήματα με μέγιστο βαθμό 3, και γραφήματα με φραγμένο δεντροπλάτος. Από την άλλη πλευρά, δείχνουμε ότι το πρόβλημα παραμένει NP-πλήρες ακόμα και όταν το γράφημα εισόδου ανήκει σε μια από τις ακόλουθες κλάσεις γραφημάτων: split γραφήματα (επομένως, και chordal γραφήματα), γραφήματα με μέγιστο βαθμό το πολύ 4, επίπεδα γραφήματα, και (3K1, 2K2)-free γραφήματα. Συνεπώς, συμβάλουμε να οριστούν τα πρώτα υπολογιστικά όρια μεταξύ κλάσεων γραφημάτων για τις οποίες το πρόβλημα είναι πολυωνυμικά επιλύσιμο και για τις οποίες παραμένει NP-πλήρες.Εμπνευσμένοι από την στενή σχέση που έχει με το πρόβλημα MaxSTC, θεωρούμε το πρόβλημα Cluster Deletion. Σκοπός είναι να αφαιρέσουμε το ελάχιστο πλήθος ακμών από ένα δοθέν γράφημα, έτσι ώστε κάθε συνεκτική συνιστώσα του εναπομείναντος γραφήματος να σχηματίζει κλίκα. Είναι γνωστό ότι το Cluster Deletion ως πρόβλημα απόφασης είναι NP-πλήρες στα (P5-free) chordal γραφήματα, ενώ το Cluster Deletion λύνεται σε πολυωνυμικό χρόνο στα split γραφήματα. Ωστόσο, η ύπαρξη ενός πολυωνυμικού χρόνου αλγορίθμου για το Cluster Deletion στα interval γραφήματα, μία γνήσια υποκλάση των chordal γραφημάτων, παρέμενε ανοιχτό πρόβλημα. Η κύρια συνεισφορά στο πρόβλημα αυτό είναι ότι απαντάμε θετικά, δίνοντας έναν πολυωνυμικό αλγόριθμο για το πρόβλημα Cluster Deletion στα interval γραφήματα. Επιπλέον, αν και ο πολυωνυμικός αλγόριθμος για τα split γραφήματα είναι σχετικά απλός, δείχνουμε ότι το πρόβλημα Cluster Deletion παραμένει NP-πλήρες σε μία φυσική και μικρή γενίκευση των split γραφημάτων που αποτελεί ταυτόχρονα μία γνήσια υποκλάση των (P5-free) chordal γραφημάτων. Παρά την δυσκολία σε αυτή τη γενίκευση των split γραφημάτων, παρέχουμε γρηγορότερους και απλούστερους πολυωνυμικούς αλγορίθμους για το πρόβλημα Cluster Deletion σε υποκλάσεις της συγκεκριμένης γενίκευσης.Επιπροσθέτως, εισάγουμε και μελετάμε την παραμετρική πολυπλοκότητα του προβλήματος Strong F-Closure, για σταθερό γράφημα F, που αποτελεί μία γενίκευση του προβλήματος MaxSTC. Ο στόχος είναι να επιλέξουμε ένα μέγιστο πλήθος από ακμές του δοθέντος γραφήματος G και να τις χαρακτηρίσουμε ως ισχυρές ακμές, με τον ακόλουθο τρόπο: όταν ένα υποσύνολο από ισχυρές ακμές σχηματίζει ένα υπογράφημα ισόμορφο με το F, τότε το αντίστοιχο επαγόμενο υπογράφημα του G δεν είναι ισόμορφο με το F. Συνεπώς, το υπογράφημα του G που ορίζεται από τις ισχυρές ακμές δεν είναι απαραίτητα F-free, αλλά όταν περιέχει ένα αντίγραφο του F, υπάρχουν επιπλέον ακμές στο G ώστε να απαγορεύουν αυτό το ισχυρό αντίγραφο του F στο G. Επομένως, το πρόβλημα Strong F-Closure αποτελεί μία γενίκευση του προβλήματος MaxSTC όταν F = P3, ενώ αποτελεί ένα είδος “χαλάρωσης” του προβλήματος F-free Edge Deletion. Μελετάμε την παραμετρική πολυπλοκότητα του προβλήματος υπό διάφορες φυσικές παραμέτρους. Επικεντρωνόμαστε κυρίως στο πλήθος k των ισχυρών ακμών ως παράμετρο. Δείχνουμε ότι το πρόβλημα είναι FPT με αυτή την παραμετροποίηση για κάθε σταθερό γράφημα F, ενώ δεν επιδέχεται πολυωνυμικό πυρήνα ακόμα και όταν το F = P3. Αυτή η τελευταία περίπτωση είναι ισοδύναμη με το MaxSTC πρόβλημα, το οποίο μας παρακινεί να μελετήσουμε το πρόβλημα αυτό σε γνωστές κλάσεις γραφημάτων. Δείχνουμε ότι το MaxSTC δεν επιδέχεται πολυωνυμικό πυρήνα ακόμα και όταν το γράφημα που μας δίνεται είναι split, ενώ επιδέχεται ένα πολυωνυμικό πυρήνα αν το γράφημα είναι επίπεδο ή d-degenerate γράφημα. Επιπροσθέτως, στα γραφήματα με μέγιστο βαθμό το πολύ 4, δείχνουμε ότι το MaxSTC παραμένει FPT ακόμα και με τη παράμετρο k − μ(G), όπου μ(G) είναι το μέγεθος του μέγιστου ταιριάσματος του G. Κλείνουμε με ορισμένα υπολογιστικά αποτελέσματα της παραμετροποίησης του προβλήματος Strong F-Closure υπό το πλήθος των ασθενών ακμών, όπου δείχνουμε ότι το πρόβλημα είναι FPT και επιδέχεται πολυωνυ μικό πυρήνα με τη συγκεκριμένη παράμετρο.