Ο φοιτητής του προγράμματος Ηλίας Κυπραίος θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Parameterizing Block Treedepth by Bounded Depth Forest Deletion
την Τετάρτη 1 Απριλίου 2026 και ώρα 15:15, στην αίθουσα Α56 του τμ. Πληροφορικής και Τηλεπικοινωνιών του ΕΚΠΑ
Σύνοψη Διπλωματικής:
Οι δομικές παράμετροι γραφημάτων διαδραματίζουν κεντρικό ρόλο στη σύγχρονη Θεωρία Γραφημάτων και τον σχεδιασμό αλγορίθμων. Παρέχουν έναν τρόπο μέτρησης της δομικής πολυπλοκότητας των γραφημάτων και συχνά επιτρέπουν σε υπολογιστικά δύσκολα προβλήματα να καταστούν επιλύσιμα όταν η παράμετρος είναι μικρή. Στο πλαίσιο της Παραμετρικής Πολυπλοκότητας, πολλά κλασικά NP-δύσκολα προβλήματα επιδέχονται αποδοτικούς αλγορίθμους όταν περιορίζονται σε γραφήματα με φραγμένες δομικές παραμέτρους.
Σε αυτή τη διατριβή, μελετάμε το δισυνεκτικό δεντροβάθος, μια γενίκευση του δεντροβάθους όπου η αφαίρεση κορυφών συμβαίνει στα τεμάχια του δοθέντος γραφήματος, τόσο από δομική όσο και από αλγοριθμική σκοπιά. Αρχικά, παρουσιάζουμε έναν εναλλακτικό ορισμό του δισυνεκτικού δεντροβάθους, εμπνευσμένο από τον χαρακτηρισμό του δεντροβάθους μέσω των ασθενών χρωματικών αριθμών. Αντί να περιγράφουμε την παράμετρο μέσω διαγραφής κορυφών, ερμηνεύουμε εκ νέου τη διαδικασία ως διαγραφή συνόλων ακμών που αντιστοιχούν στις προσπίπτουσες ακμές των κορυφών. Αυτά τα σύνολα ακμών σχηματίζουν φυσικά αστέρια, γεγονός που οδηγεί σε μια διατύπωση βασισμένη σε αστροδιαμερίσεις του συνόλου των ακμών, σε συνδυασμό με έγκυρες σειρές διαγραφής αυτών των αστέρων. Αυτή η οπτική γωνία παρέχει μια σαφέστερη ερμηνεία της διαδικασίας διαγραφής.
Επίσης, εισάγουμε και μελετάμε μια νέα παράμετρο γραφημάτων που ονομάζεται αφαίρεση κορυφών προς αστροδάσος. Για ένα γράφημα G, η παράμετρος αυτή μετρά τον ελάχιστο αριθμό κορυφών των οποίων η αφαίρεση μετασχηματίζει το G σε ένα δάσος του οποίου οι συνεκτικές συνιστώσες είναι αστέρια. Η παράμετρος αυτή αποτελεί μέρος μιας ευρύτερης οικογένειας παραμέτρων, των αφαίρεση κορυφών προς d-δάσος, όπου το εναπομείναν γράφημα απαιτείται να είναι ένα δάσος φραγμένου βάθους d, αποτελώντας περιορισμό του συνόλου ανάδρασης κορυφών. Η περίπτωση του δάσους αστεριών αντιστοιχεί στην ειδική περίπτωση όπου το βάθος είναι το πολύ δύο.
Η κύρια αλγοριθμική συνεισφορά αυτής της διατριβής αφορά την παραμετρική πολυπλοκότητα του προβλήματος απόφασης ΔΙΣΥΝΕΚΤΙΚΟ ΔΕΝΤΡΟΒΑΘΟΣ. Συγκεκριμένα, εξετάζουμε το πρόβλημα όταν αυτό παραμετροποιείται από τον αριθμό αφαίρεσης κορυφών για αστροδάσος. Χρησιμοποιώντας μια σειρά ειδικά σχεδιασμένων κανόνων αναγωγής, αναπτύσσουμε έναν αλγόριθμο πυρηνοποίησης που ανάγει κάθε στιγμιότυπο σε ένα ισοδύναμο στιγμιότυπο του οποίου το μέγεθος φράσσεται πολυωνυμικά από την παράμετρο. Κατά συνέπεια, το πρόβλημα είναι παραμετρικά βατό (FPT) ως προς αυτή την παράμετρο.
Η επιτροπή,
Αρχοντία Γιαννοπούλου (Συνεπιβλέπουσα),
Τμήμα Πληροφορικής, Ε.Κ.Π.Α.
Δημήτρης Ζώρος (Συνεπιβλέπων),
Εξωτερικός συνεργάτης
Σταύρος Κολλιόπουλος,
Τμήμα Πληροφορικής, Ε.Κ.Π.Α.
Βασίλης Νάκος,
Τμήμα Πληροφορικής, Ε.Κ.Π.Α.