MSc thesis of Σπυρίδωνος Μανιάτη
Δεσμώσεις σε πρωτεύοντα-δυϊκά γραφήματα
Supervisor: Δημήτριος Μ. Θηλυκός
Ένα από τα επιτεύγματα με τη μεγαλύτερη επιρροή στη Θεωρία Γραφημάτων υπήρξε χωρίς αμφιβολία η σειρά εργασιών "{\em Ελλάσσονα Γραφήματα}" των Neil Robertson και Paul D. Seymour, στην οποία, έπειτα από $23$ εργασίες από το 1983 έως το 2011, κατάφεραν να αποδείξουν την εικασία του Wagner. Η εικασία αυτή λέει ότι η κλάση των μη κατευθυνόμενων γραφημάτων, μερικώς διατεταγμένων με τη σχέση ελλάσσονος γραφήματος, αποτελεί well-quasi-διάταξη ή ισοδύναμα, για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελλάσσονα υπάρχει ένα σύνολο από απαγορευμένα γραφήματα ως ελλάσσονα. Μπορεί να υποστηριχθεί ότι, δεν είναι τόσο το ίδιο το τελικό αποτέλεσμα, όσο ολόκληρη η θεωρία που αναπτύχθηκε στην πορεία που είχε, και συνεχίζει να έχει, τεράστιο αντίκτυπο τόσο στη συνδυαστική όσο και στην αλγοριθμική Θεωρία Γραφημάτων. Μία από τις κυριότερες συνεισφορές τους, η οποία κατέχει και κεντρικό ρόλο στη δουλειά τους, είναι η κατασκευή ενός αλγορίθμου που λύνει το πρόβλημα των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ σε χρόνο $f(k) \cdot n^{3}$, όπου είναι το πλήθος των διακεκριμένων μονοπατιών που μας ζητείται να βρούμε. Το βασικό συστατικό της απόδειξής τους είναι η ονομαστή {\em τεχνική της άσχετης κορυφής} (για την οποία οι πλήρεις αποδείξεις δόθηκαν σε επόμενο μέρος της σειράς) που χρησιμοποιήθηκε ευρέως στην πορεία. Όσο σπουδαίο κι αν αποδείχθηκε πως είναι το παραπάνω αποτέλεσμα, η συνάρτηση $f$ που εξαρτάται από το $k$ και εμφανίζεται στη χρονική πολυπλοκότητα του αλγορίθμου, είναι ασύλληπτα μεγάλη ακόμη και για πολύ μικρές τιμές του $k$. Για τον λόγο αυτόν, πολλοί ερευνητές θέλησαν να βελτιώσουν αυτήν την παραμετρική εξάρτηση από το $k$, είτε προσπαθώντας να απλοποιήσουν τις περίπλοκες αποδείξεις των δομικών θεωρημάτων για τη γενική περίπτωση, είτε επικεντρώνοντας την προσοχή τους σε συγκεκριμένες κλάσεις γραφημάτων των οποίων τα δομικά χαρακτηριστικά θα οδηγούσαν, ίσως, σε απλούστερες αποδείξεις και καλύτερη παραμετρική εξάρτηση. Ένα μεγάλο βήμα όσον αφορά την πρώτη κατεύθυνση (παρόλο που το φράγμα για το $f(k)$ είναι $2^{2^{2^{2^{\Omega(k)}}}}$, το οποίο είναι, σαφώς, ακόμη τεράστιο) έγινε από τους Ken-ichi Kawarabayashi και Paul Wollan στο \cite{Wollan}. Ένα αποφασιστικό βήμα προς τη δεύτερη κατεύθυνση, για την κλάση των {\em επίπεδων γραφημάτων}, έγινε από τους Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, και Dimitrios M. Thilikos στο \cite{PPDP}, όπου αποδεικνύουν ένα φράγμα για το $f(k)$ που είναι απλά εκθετικό ως προς $k$. Βασιζόμενοι σε αυτήν την τελευταία εργασία, μελετάμε μια επέκταση του προβλήματος των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ στην κλάση των {\em πρωτεύοντων-δυϊκών γραφημάτων} και χρησιμοποιώντας την ιδέα άσχετης κορυφής, αποδεικνύουμε ένα δομικό θεώρημα το οποίο λέει ότι αν το δεντροπλάτος του πρωτεύοντος-δυϊκού γραφήματος μας είναι αρκούντως μεγάλο, τότε υπάρχει (και μπορεί να εντοπιστεί αλγοριθμικά) ένα τμήμα του το οποίο είναι άσχετο και του οποίου η αφαίρεση από τη γράφημα οδηγεί σε ένα απλούστερο και ισοδύναμο στιγμιότυπο του προβλήματος. Επίσης, εξηγούμε πως ένας αλγόριθμος για το πρόβλημα των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ για την κλάση των πρωτεύοντων-δυϊκών γραφημάτων μπορεί να χρησιμοποιηθεί για την κατασκευή αλγορίθμων για προβλήματα σε ενεπίπεδα γραφήματα, όπου είναι απαραίτητο να λαμβάνεται υπόψην η τοπολογία της επίπεδης εμβάπτισης που δίνεται ως είσοδος.
Defended: 03 Ιουνίου 2016.