Algorithm design and engineering for graph connectivity problems
Authors: Κεφαλληνός Διονύσιος 
Published: July 2024

Η παρούσα διατριβή ασχολείται με διάφορα προβλήματα που αφορούν τη συνεκτικότητα γραφημάτων. Η συνεκτικότητα ακμών ή κορυφών ενός γραφήματος είναι σημαντικές μετρικές που μας περιγράφουν πόσο ”καλά” συνδεδεμένο είναι το εν λόγω γραφήμα. Διαισθητικά όσο μεγαλύτερη είναι η συνεκτικότητα τόσο πιο πυκνό σε συνδέσεις (ακμές) είναι το γράφημα, κατα συνέπεια είναι πιο δύσκολο να το διασπάσουμε ή να το καταστρέψουμε. Τα γραφήματα μοντελοποιούν δίκτυα, τα οποία ενδεχομένως να αποτελούνται από χιλιάδες ή και εκατομμύρια κόμβους ή ακμές όπως για παράδειγμα τα κοινωνικά δίκτυα, τα οδικά δίκτυα, τα βιολογικά δίκτυα κ.α.. Επομένως χρειαζόμαστε αποδοτικούς αλγορίθμους για να επιλύσουμε προβλήματα που δέχονται ως είσοδο γραφήματα τέτοιου μεγέθους, τόσο ασυμπτωτικά όσο και στη πράξη. Σε αυτή τη διατριβή, παρουσιάζουμε αποδοτικές υλοποιήσεις και εμπειρικές μελέτες σημαντικών αλγορίθμων για βασικά προβλήματα συνεκτικότητας σε κατευθυνόμενα γραφήματα. Επιπλέον, προτείνουμε αποτελεσματικές μεθόδους επιτάχυνσης αυτών των αλγορίθμων, οι οποίες βελτίωσαν τους χρόνους εκτέλεσης κατά μία έως δύο τάξεις μεγέθους. Τέλος, προτείνουμε νέους αλγόριθμους γραμμικού χρόνου για σχετικά προβλήματα συνδεσιμότητας σε μικτά γραφήματα. Ένα κατευθυνόμενο γράφημα G είναι ισχυρά συνεκτικό αν μεταξύ δύο οποιωνδήποτε κόμβων x και y, υπάρχει κατευθυνόμενο μονοπάτι από τον κόμβο x προς τον y και κατευθυνόμενο μονοπάτι από τον κόμβο y προς τον x. Η συνεκτικότητα ακμών λ (G) ενός κατευθυνόμενου γραφήματος G ορίζεται ως το ελάχιστο πλήθος ακμών που πρέπει να αφαιρεθούν από το G, έτσι ώστε το γράφημα που προκύπτει να μην είναι ισχυρά συνεκτικό. Το G είναι k-ισχυρά συνεκτικό όταν λ (G) k.Ο υπολογισμός της συνεκτικότητας ακμών (edge-connectivity) ενός γραφήματος είναι ένα θεμελιώδες πρόβλημα της αλγοριθμικής θεωρίας γραφημάτων, με πληθώρα εφαρμογών σε τομείς όπως στην ανάλυση μεταφορικών, επικοινωνιακών, ηλεκτρικών και κοινωνικών δικτύων, σε συστήματα παραγωγής, και στη χρονοδρομολόγηση εργασιών. Η εργασία μας [6] είχε ως σκοπό τη μελέτη των τεχνικών σχεδίασης αποδοτικών αλγορίθμων για τον υπολογισμό της συνεκτικότητας ακμών σε κατευθυνόμενα γραφήματα, εστιάζοντας τόσο στη θεωρητική όσο και στην πρακτική επίδοσητων σχετικών αλγορίθμων. Στο πλαίσιο αυτό, μελετήθηκαν και υλοποιήθηκαν αποδοτικοί αλγόριθμοι που υπολογίζουν τη συνεκτικότητα ακμών σε κατευθυνόμενα γραφήματα και πραγματοποιήθηκε μια ενδελεχής πειραματική ανάλυση των επιδόσεών τους. Συγκεκριμένα, στην εργασία μας [6] παρουσιάστηκε η πρώτη αποδοτική υλοποίηση του αλγορίθμου του Gabow [1], πολυπλοκότητας O(λmlog n) για γράφημα συνεκτικότητας λ με n κόμβους και m ακμές, ο οποίος βασίζεται στη θεωρία μητροειδών (matroid theory) και στον υπολογισμό ανεξάρτητων συνδετικών δένδρων. Επίσης, δόθηκαν οι πρώτες αποδοτικές υλοποιήσεις αλγορίθμων που βασίζονται σε πρόσφατες τεχνικές «τοπικής αναζήτησης» (local search) για την εύρεση ελάχιστων τομών, οι οποίες έχουν προταθεί από τους Chechik et al. [2] και Forsteret al. [7], πολυπλοκότητας O(λ2mpolylogn). Επιπροσθέτως, προτάθηκαν πρακτικές μέθοδοι επιτάχυνσης αυτών των αλγορίθμων. Στην πειραματική μελέτη συγκρίθηκεη αποδοτικότητα των διαφόρων αλγορίθμων σε πραγματικά γραφήματα, τα οποία έχουν ληφθεί από ποικίλα πεδία εφαρμογών, καθώς και σε συνθετικά γραφήματα, αποσκοπώντας στο να αναδειχθούν τα πλεονεκτήματα και μειονεκτήματα κάθε τεχνικής. Τα πειραματικά δεδομένα έδειξαν ότι ο αλγόριθμος του Gabow επιτυγχάνει συνολικά την καλύτερη απόδοση στην πράξη. Επιπλέον, παρατηρήθηκε ότι μια μέθοδος επιτάχυνσής που προτάθηκε στην εργασία [6], η οποία βασίζεται στη γρήγορη αρχικοποίηση των συνδετικών δένδρων που χρησιμοποιεί ο αλγόριθμος του Gabowμέσω καθοδικής διερεύνησης, επιτυγχάνει αξιοσημείωτη βελτίωση του χρόνου εκτέλεσης του αλγορίθμου του Gabow. Ένα ακόμα σημαντικό εύρημα της πειραματικής μελέτης της εργασίας [6] ήταν ότι οι αλγόριθμοι τοπικής αναζήτησης αποδίδουν καλά στην πράξη όταν η συνεκτικότητα λ του γραφήματος είναι μικρή, αλλά δεν μπορούν να ανταγωνιστούν τον αλγόριθμο του Gabow για μεγαλύτερες τιμές του λ. Σε συνέχεια της προηγούμενης εργασίας, μελετήσαμε το πρόβλημα υπολογισμού ενός συνόλου ανεξάρτητων συνδετικών δένδρων μέγιστου πλήθους σε κατευθυνόμενα γραφήματα. Έστω G ένα κατευθυνόμενο γράφημα με αφετηριακό κόμβο s. Ένα συνδετικό δένδρο T του G, με αφετηρία τoν κόμβο s, είναι ένα άκυκλο υπογράφημα του G, με την εξής ιδιότητα. Για κάθε κόμβο v 6= s, το T περιέχει μια μοναδική διαδρομή από τον s προς τον v. Αυτό συνεπάγεται ότι ο s δεν έχει καμία εισερχόμενη ακμή, και συγχρόνως κάθε κόμβος v 6= s έχει μια μοναδική εισερχόμενη ακμή. Δύο συνδετικά δένδρα είναι ανεξάρτητα (edge-disjoint) όταν δεν έχουν καμιά ακμή κοινή. Σε ένα σύνολο ανεξάρτητων συνδετικών δένδρων T = fT1, T2, . . . , Tkg, οποιαδήποτε δύο συνδετικά δένδρα Ti, Tj 2 T είναι μεταξύ τους ανεξάρτητα. Ένα κλασικό αποτέλεσμα του Edmonds [8] δηλώνει ότι το μέγιστο πλήθος ανεξάρτητων συνδετικών δένδρων ενός κατευθυνόμενου γραφήματος G, με αφετηριακό κόμβοs, ισούται με την ελάχιστη τιμή k = cG(s) μιας s-τομής του G. Μια s-τομή του Gείναι ένα σύνολο ακμών C, τέτοιο ώστε το G n C να μην περιέχει μονοπάτι απότον s προς κάποιο κόμβο v. Αυτή η έννοια σχετίζεται με τη συνεκτικότητα ακμών λ (G) ενός ισχυρά συνεκτικού κατευθυνόμενου γραφήματος G, καθώς ισχύειλ (G) = minfcG(s), cGR(s)g, όπου GR το αντίστροφο γράφημα του G. Στο πλαίσιο της εργασίας μας [9], μελετήθηκαν και υλοποιήθηκαν αποδοτικοί αλγόριθμοι για τον υπολογισμό ενός μέγιστου συνόλου ανεξάρτητων συνδετικών δένδρων ενός κατευθυνόμενου γραφήματος. Οι αλγόριθμοι που υλοποιήθηκαν και συμπεριλήφθηκαν στην πειραματική μελέτη της εργασίας [9] είναι ο αλγόριθμος του Gabow [6] πολυπλοκότητας O(k2n2), ο αλγόριθμος του Tarjan [4] πολυπλοκότητας O(k2m2), και ο αλγόριθμος των Tong και Lowler [5] πολυπλοκότητας O(k2mn). Επιπροσθέτως,προτάθηκαν μέθοδοι επιτάχυνσης αυτών των αλγορίθμων στην πράξη. Στην πειραματική μελέτη της εργασίας [9], συγκρίθηκε η αποδοτικότητα των διαφόρων αλγορίθμων σε γραφήματα που προέρχονται από τον πραγματικό κόσμο και από ένα ευρύ φάσμα εφαρμογών, καθώς και σε συνθετικά γραφήματα. Τα πειραματικά αποτελέσματα ανέδειξαν τα πλεονεκτήματα και μειονεκτήματα κάθε τεχνικής. Συγκεκριμένα, παρατηρήθηκε ότι ο αλγόριθμος του Gabow επιτυγχάνει συνολικά την καλύτερη απόδοση, καθώς είναι σημαντικά ταχύτερος από τους άλλους δύο αλγόριθμους, ενώ δεύτερος σε απόδοση έρχεται ο αλγόριθμος του Tarjan. Επίσης, παρατηρήθηκε ότι μια απλή αλλά πολύ αποτελεσματική ευρετική τεχνική που προτάθηκε στην εργασία [9], επιτάχυνε τον χρόνο εκτέλεσης του αλγορίθμου του Gabow κατά δύο τάξεις μεγέθους στις περισσότερες περιπτώσεις. Τέλος, στην περιοχή της συνεκτικότητας μεικτών γραφημάτων, μελετήθηκαν προβλήματα που σχετίζονται με την έννοια της 2-ισχυρής συνεκτικότητας ακμών (2-edgestrong connectivity). Ένα μεικτό γράφημα (mixed graph) G περιέχει τόσο κατευθυνόμενες ακμές όσο και μη κατευθυνόμενες ακμές. Ένας προσανατολισμός (orientation) R του μεικτού γραφήματος G πραγματοποιείται όταν δώσουμε κατευθύνσεις σε όλες τις μη κατευθυνόμενες ακμές. Δηλαδή, μετατρέπουμε κάθε μη κατευθυνόμενη ακμή u, v σε κατευθυνόμενη, η οποία είναι είτε η ακμή (u, v) είτε η ακμή (v, u). Στη βιβλιογραφία έχουν μελετηθεί πολλά προβλήματα προσανατολισμού μεικτών ή μη κατευθυνόμενων γραφημάτων, ανάλογα με τις ιδιότητες που επιθυμούμε να έχει ένας συγκεκριμένος προσανατολισμός. Ένας προσανατολισμός R του G είναι ισχυρός (strong orientation) όταν το γράφημα που προκύπτει είναι ισχυρά συνεκτικό. Πιο γενικά, ένας προσανατολισμός R του G είναι k-ισχυρός (k-strong orientation) όταν το γράφημα που προκύπτει είναι k-ισχυρά συνεκτικό. Αυτές οι έννοιες έχουν εφαρμογές σε τομείς όπως ο σχεδιασμός οδικών και τηλεπικοινωνιακών δικτύων. Σε ένα μεικτό γράφημα G, ένα σύνολο κόμβων S V (G) είναι ανθεκτικό (resilient) ως προς την ισχυρή συνεκτικότητα αν έπειτα από οποιαδήποτε αφαίρεση ακμής του γραφήματος, υπάρχει προσανατολισμός των μη κατευθυνόμενων ακμών ώστε το σύνολο S να παραμείνει ισχυρά συνεκτικό. Στο πλαίσιο της διδακτορικής διατριβής, μελετήσαμε το πρόβλημα υπολογισμού των ανθεκτικών συνιστωσών ενός μεικτού γραφήματος G, δηλαδή των μέγιστων συνόλων κόμβων C1,C2, . . . ,Ck, όπου κάθε Ci είναι ανθεκτικό. Δηλαδή, για κάθε ακμή e του G, υπάρχει προσανατολισμός Ri του G τέτοιος ώστε όλοι οι κόμβοι του Ci να είναι ισχυρά συνεκτικοί. Το πρόβλημα αυτό σχετίζεται με τη 2-ισχυρή συνεκτικότητα ακμών, καθώς αν το G περιέχει μόνο κατευθυνόμενες ακμές, τότε κάθε ανθεκτική συνιστώσα είναι 2-ισχυρά συνεκτική. Το κύριο αποτέλεσμα στην εργασία μας [10] ήταν ένας αλγόριθμος γραμμικού χρόνου για τον υπολογισμό των ανθεκτικών συνιστωσών ενός μεικτού γραφήματος. Ο αλγόριθμος αυτός βασίζεται κυρίως σε δύο βασικές τεχνικές: (1) στην κατασκευή μιας συλλογής H βοηθητικών γραφημάτων που διατηρεί τις ανθεκτικές συνιστώσες τουG, και (2) σε μια αναγωγή στο πρόβλημα υπολογισμού των συνεκτικών συνιστωσών ενός μη κατευθυνόμενου γραφήματος μετά τη διαγραφή συγκεκριμένων ζευγών στοιχείων του γραφήματος που αποτελούνται από ένα κόμβο και μια ακμή. Για την επίλυση του δεύτερου προβλήματος, η εργασία [10] εκμεταλλεύεται τις ιδιότητεςτων SPQR-δένδρων των δισυνεκτικών συνιστωσών κάθε γραφήματος.