Algorithms and complexity of graph modification problems
Authors: Κωνσταντινίδης Αθανάσιος 
Published: September 2024

Τα προβλήματα επεξεργασίας γραφημάτων παίζουν σημαντικό ρόλο τόσο στην δομική όσο και στην αλγοριθμική θεωρία γραφημάτων. Τα προβλήματα αυτά έχουν μελετηθεί για δεκαετίες και βρίσκουν πρακτικές εφαρμογές σε σημαντικές περιοχές έρευνας. Σε αυτήν την διατριβή μελετάμε ένα κλασικό πρόβλημα επεξεργασίας ακμών, γνωστό ως 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 και επιδέχεται πολυωνυ μικό πυρήνα με τη συγκεκριμένη παράμετρο.