Algorithm design and engineering for graph connectivity problems

Abstract

This dissertation deals with topics related to some notions of graph connectivity in directed graphs and mixed graphs. The edge and vertex connectivity of a graph are important measures of its resilience as a network. There is a great variety of real-life relations that can be modeled by graphs. A few of the most notable examples include road networks, the World Wide Web, social networks, and other communication networks. Such a graph may consist of millions of edges and vertices as for example road or social networks. Therefore, we are interested both in asymptotically fast algorithms and in algorithms that are efficient in practice. In this dissertation, we present efficient implementations and empirical studies of important algorithms for basic connectivity problems in directed graphs. Moreover, we propose efficient methods of speeding up these algorithms for practical instances, which improved their execution times by one to two orders of magnitude. Finally, we provide new linear-time algorithms for related connectivity problems in mixed graphs. Firstly we provide an experimental study of algorithms for computing the edge connectivity λ of a directed graph efficiently in practice. The edge connectivity λ of Gis the minimum number of edges whose deletion leaves G not strongly connected. A graph G is strongly connected if there is a directed path from each vertex to any other vertex. Computing the edge connectivity of a graph is a classical subject in graph theory, and is an important notion in several application areas, such as transportation, communication, production, scheduling, and power engineering. We presented the first efficient implementations of Gabow’s algorithm [1] which runs in O(λmlog n)time and is based on matroid intersection and packing spanning trees, as well as algorithms based on recent “local search” algorithms for minimum-cut which have been proposed by Chechik et al. [2] and Forster et al. [3], of complexity O(λ2mpolylogn).Also, we proposed practical methods for speeding up these algorithms. In the experimental study, the efficiency of the various algorithms was compared on real graphs, taken from various application areas, as well as on synthetic graphs, aiming to highlight the advantages and disadvantages of each technique. Then we studied the problem of packing arborescences. An s-arborescence of Gis a directed spanning tree, i.e., an acyclic subgraph of G where s has in-degree zero and every other vertex has in-degree one. The problem of packing arborescences is to compute a maximum cardinality set of edge-disjoint arborescences of a directed graph. We explored the design space of efficient algorithms for packing arborescences of a directed graph in practice and we conducted a thorough empirical study to highlight the merits and weaknesses of each technique. In particular, we presented efficient implementations of Gabow’s arborescence packing algorithm [1] of complexity O(k2n2), Tarjan’s algorithm [4] of complexity O(k2m2), and the algorithm of Tongand Lowler [5] of complexity O(k2mn). In addition, we proposed a simple but very efficient method that significantly improves the running time of Gabow’s algorithm in practice. In our experimental study, the performance of the various algorithms was compared on real-world taken from a wide range of applications, as well as on synthetic graphs. Finally, we considered some orientation problems in mixed graphs related to the concept of 2-edge strong connectivity. A mixed graph G is a graph that consists of both undirected and directed edges. An orientation of G is formed by orienting all the undirected edges of G, i.e., converting each undirected edge fu, vg into a directed edge that is either (u, v) or (v, u). Many mixed or undirected graph orientation problems have been studied in the literature, depending on the properties we wish a particular orientation to have. An orientation R of G is a strong orientation when the resulting graph is strongly connected. More generally, an orientation R of G isa k-strong orientation when the resulting graph is k-edge strongly connected. These concepts have applications in areas such as the design of road and telecommunications networks, and the structural stability of buildings. Our main result was to provide a linear time algorithm for the following problem. Given a mixed graph G, we wish to compute its maximal sets of vertices C1,C2, . . . ,Ck with the property that by removing any edge e from G (directed or undirected) there is an orientation Ri of Gne such that all vertices of Ci are strongly connected in Ri. This problem is related to 2-edge strong connectivity, since if G contains only directed edges, then every set Ci corresponds toa 2-edge strong component of G.

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