Efficient algorithms for some connectivity problems, in static and dynamic graphs

Abstract

In this thesis, we provide efficient algorithms for some connectivity problems in undirected graphs, in the static, dynamic, and sensitivity setting. Our contribution can be summarized as follows. (1) We provide the first linear-time algorithms for computing the 4- and 5-edge-connected components in undirected multigraphs. This result answers a theoretical question, and sheds light on the possibility that a linear-time solution may exist for general k. Furthermore, the algorithms that we provide can have a very efficient implementation with the use of elementary data structures. Especially for the case k=5, we provide a novel analysis of the structure of 4-edge cuts in 3-edge-connected graphs, that can guide us into a proper selection of them for our purposes. We believe that this analysis may provide a clue for a general solution for the k-edge-connected components, or other related graph connectivity problems. (2) A key component in our algorithm for the case k=5 is an oracle for answering connectivity queries for pairs of vertices in the presence of at most four edge-failures. Specifically, the oracle has size O(n), it can be constructed in linear time, and it answers connectivity queries in the presence of at most four edge-failures in constant time, where n denotes the number of vertices of the graph. We note that this is a result of independent interest. (3) We provide an oracle for efficiently answering connectivity queries in the presence of vertex failures. Specifically, we design a data structure that can handle an arbitrary but fixed number of vertex failures, so that it can efficiently answer connectivity queries between vertices in the remaining graph. This very basic connectivity problem has received the attention of researchers for more than a decade now, but the solutions that have been provided are highly complicated and very difficult to be implemented efficiently. On the other hand, our solution is arguably the simplest that has been proposed for this problem; it is relatively easy to describe and analyze, and it uses only standard textbook data structures. Furthermore, it even provides some trade-offs that improve on the state of the art in some respects. (4) Finally, we deal with the computation of the maximal k-edge-connected subgraphs in incremental graphs. We provide a general framework that reduces this computation to the incremental maintenance of the k-edge-connected components. As a concrete application of this framework, we provide an algorithm for the incremental maintenance of the maximal 3-edge-connected subgraphs, by relying on algorithms and data structures for the incremental maintenance of the 3-edge-connected components. This provides a significant improvement over the state of the art, which is given by applying the best known static algorithm after every insertion. Furthermore, we provide fast constructions of sparse spanning subgraphs that have the same maximal k-edge-connected subgraphs as the original graph. These can be used in order to speed up computations that involve the maximal k-edge-connected subgraphs.

Στην παρούσα διατριβή παρέχουμε αποδοτικούς αλγορίθμους για ορισμένα προβλήματα συνεκτικότητας σε στατικά και δυναμικά γραφήματα. Τα αποτελέσματά μας μπορούν να συνοψιστούν ως εξής. (1) Αρχικά, παρέχουμε αλγορίθμους γραμμικού χρόνου για τον υπολογισμό των 4- και 5-συνεκτικών συνιστωσών σε μη-κατευθυνόμενα πολυγραφήματα. Έτσι απαντούμε ένα θεωρητικό ερώτημα, και ενισχύουμε την υπόθεση ότι ο υπολογισμός των k-συνεκτικών συνιστωσών μπορεί να επιτευχθεί σε γραμμικό χρόνο για οποιοδήποτε k. Ένα σημαντικό χαρακτηριστικό των αλγορίθμων που παρέχουμε είναι ότι μπορούν να υλοποιηθούν αποδοτικά με την χρήση στοιχειωδών δομών δεδομένων. Ειδικά για την περίπτωση k=5, παρέχουμε και μια καινοτόμο ανάλυση των 4-τομών σε 3-συνεκτικά γραφήματα, η οποία μας καθοδηγεί στην κατάλληλη επιλογή μιας συλλογής αυτών προκειμένου να πετύχουμε τον σκοπό μας. Πιστεύουμε ότι αυτή η ανάλυση μπορεί να έχει εφαρμογές και στην γενικότερη εκδοχή του προβλήματος, ή και σε άλλα σχετικά προβλήματα συνεκτικότητας. (2) Μια βασική συνιστώσα του αλγορίθμου για την περίπτωση k=5 είναι μια αποδοτική δομή που απαντά σε ερωτήματα συνεκτικότητας όταν το γράφημα έχει υποστεί απώλειες το πολύ τεσσάρων ακμών. Συγκεκριμένα, η δομή αυτή κατασκευάζεται σε γραμμικό χρόνο, και απαντά ερωτήματα συνεκτικότητας έπειτα από απώλεια τεσσάρων ακμών σε σταθερό χρόνο. Με αυτές τις προδιαγραφές, η δομή που παρέχουμε είναι ουσιαστικά βέλτιστη, και αυτό είναι ένα αποτέλεσμα ανεξάρτητου ενδιαφέροντος. (3) Παρέχουμε μια δομή που απαντά αποδοτικά σε ερωτήματα συνεκτικότητας όταν το γράφημα υφίσταται απώλειες περιορισμένου πλήθους κόμβων. Πιο συγκεκριμένα, η δομή επεξεργάζεται αποδοτικά την πληροφορία ότι ένα σύνολο κόμβων έχει χαθεί, ώστε να μπορεί να απαντά γρήγορα σε ερωτήματα συνεκτικότητας μεταξύ των κόμβων που απομένουν στο γράφημα. Αυτό το πολύ βασικό πρόβλημα συνεκτικότητας έχει απασχολήσει τους ερευνητές εδώ και πάνω από μια δεκαετία, αλλά όλες οι λύσεις που έχουν προταθεί στην βιβλιογραφία είναι αρκετά περίπλοκες και δύσκολο να υλοποιηθούν αποδοτικά στην πράξη. Η δομή που παρέχουμε εμείς συνιστά την πιο απλή λύση που έχει βρεθεί μέχρι σήμερα: η περιγραφή και η ανάλυσή της είναι σχετικά απλή, και η υλοποίησή της βασίζεται σε απλές και γνωστές δομές δεδομένων. Επιπλέον, η λύση μας εμφανίζει από ορισμένες απόψεις και μια θεωρητική βελτίωση σε σχέση με τις προηγούμενες λύσεις. (4) Τέλος, ασχολούμαστε με το πρόβλημα του υπολογισμού των μεγιστικών k-συνεκτικών υπογραφημάτων σε γραφήματα που μεταβάλλονται με προσθήκη κόμβων ή ακμών. Προτείνουμε ένα γενικό πλαίσιο που ανάγει αυτόν τον υπολογισμό στην διατήρηση των k-συνεκτικών συνιστωσών. Ως απτή εφαρμογή αυτού του πλαισίου, παρέχουμε έναν αποδοτικό αλγόριθμο για την διατήρηση των μεγιστικών 3-συνεκτικών υπογραφημάτων, μέσω αναγωγής σε αλγορίθμους και δομές δεδομένων για την διατήρηση των 3-συνεκτικών συνιστωσών. Επιπλέον, παρέχουμε αποδοτικές κατασκευές αραιών υπογραφημάτων που διατηρούν τα μεγιστικά k-συνεκτικά υπογραφήματα του αρχικού γραφήματος. Τέτοιες κατασκευές επιταχύνουν διάφορους υπολογισμούς που αφορούν τα μεγιστικά k-συνεκτικά υπογραφήματα.