{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:5373775"},"canonical_url":"https://search.dev.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:5373775","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Parameterizing Block Treedepth by Bounded Depth Forest Deletion","abstract":"Οι δομικές παράμετροι γραφημάτων διαδραματίζουν κεντρικό ρόλο στη σύγχρονη Θεωρία Γραφημάτων και τον σχεδιασμό αλγορίθμων. Παρέχουν έναν τρόπο μέτρησης της δομικής πολυπλοκότητας των γραφημάτων και συχνά επιτρέπουν σε υπολογιστικά δύσκολα προβλήματα να καταστούν επιλύσιμα όταν η παράμετρος είναι μικρή. Στο πλαίσιο της Παραμετρικής Πολυπλοκότητας, πολλά κλασικά NP-δύσκολα προβλήματα επιδέχονται αποδοτικούς αλγορίθμους όταν περιορίζονται σε γραφήματα με φραγμένες δομικές παραμέτρους. Σε αυτή τη διατριβή, μελετάμε το δισυνεκτικό δεντροβάθος, μια γενίκευση του δεντροβάθους όπου η αφαίρεση κορυφών συμβαίνει στα τεμάχια του δοθέντος γραφήματος, τόσο από δομική όσο και από αλγοριθμική σκοπιά. Αρχικά, παρουσιάζουμε έναν εναλλακτικό ορισμό του δισυνεκτικού δεντροβάθους, εμπνευσμένο από τον χαρακτηρισμό του δεντροβάθους μέσω των ασθενών χρωματικών αριθμών. Αντί να περιγράφουμε την παράμετρο μέσω διαγραφής κορυφών, ερμηνεύουμε εκ νέου τη διαδικασία ως διαγραφή συνόλων ακμών που αντιστοιχούν στις προσπίπτουσες ακμές των κορυφών. Αυτά τα σύνολα ακμών σχηματίζουν φυσικά αστέρια, γεγονός που οδηγεί σε μια διατύπωση βασισμένη σε αστροδιαμερίσεις του συνόλου των ακμών, σε συνδυασμό με έγκυρες σειρές διαγραφής αυτών των αστέρων. Αυτή η οπτική γωνία παρέχει μια σαφέστερη ερμηνεία της διαδικασίας διαγραφής. Επίσης, εισάγουμε και μελετάμε μια νέα παράμετρο γραφημάτων που ονομάζεται αφαίρεση κορυφών προς αστροδάσος. Για ένα γράφημα G, η παράμετρος αυτή μετρά τον ελάχιστο αριθμό κορυφών των οποίων η αφαίρεση μετασχηματίζει το G σε ένα δάσος του οποίου οι συνεκτικές συνιστώσες είναι αστέρια. Η παράμετρος αυτή αποτελεί μέρος μιας ευρύτερης οικογένειας παραμέτρων, των αφαίρεση κορυφών προς d-δάσος, όπου το εναπομείναν γράφημα απαιτείται να είναι ένα δάσος φραγμένου βάθους d, αποτελώντας περιορισμό του συνόλου ανάδρασης κορυφών. Η περίπτωση του δάσους αστεριών αντιστοιχεί στην ειδική περίπτωση όπου το βάθος είναι το πολύ δύο. Η κύρια αλγοριθμική συνεισφορά αυτής της διατριβής αφορά την παραμετρική πολυπλοκότητα του προβλήματος απόφασης ΔΙΣΥΝΕΚΤΙΚΟ ΔΕΝΤΡΟΒΑΘΟΣ. Συγκεκριμένα, εξετάζουμε το πρόβλημα όταν αυτό παραμετροποιείται από τον αριθμό αφαίρεσης κορυφών για αστροδάσος. Χρησιμοποιώντας μια σειρά ειδικά σχεδιασμένων κανόνων αναγωγής, αναπτύσσουμε έναν αλγόριθμο πυρηνοποίησης που ανάγει κάθε στιγμιότυπο σε ένα ισοδύναμο στιγμιότυπο του οποίου το μέγεθος φράσσεται πολυωνυμικά από την παράμετρο. Κατά συνέπεια, το πρόβλημα είναι παραμετρικά βατό (FPT) ως προς αυτή την παράμετρο.","abstract_html":"Οι δομικές παράμετροι γραφημάτων διαδραματίζουν κεντρικό ρόλο στη σύγχρονη Θεωρία Γραφημάτων και τον σχεδιασμό αλγορίθμων. Παρέχουν έναν τρόπο μέτρησης της δομικής πολυπλοκότητας των γραφημάτων και συχνά επιτρέπουν σε υπολογιστικά δύσκολα προβλήματα να καταστούν επιλύσιμα όταν η παράμετρος είναι μικρή. Στο πλαίσιο της Παραμετρικής Πολυπλοκότητας, πολλά κλασικά NP-δύσκολα προβλήματα επιδέχονται αποδοτικούς αλγορίθμους όταν περιορίζονται σε γραφήματα με φραγμένες δομικές παραμέτρους. Σε αυτή τη διατριβή, μελετάμε το δισυνεκτικό δεντροβάθος, μια γενίκευση του δεντροβάθους όπου η αφαίρεση κορυφών συμβαίνει στα τεμάχια του δοθέντος γραφήματος, τόσο από δομική όσο και από αλγοριθμική σκοπιά. Αρχικά, παρουσιάζουμε έναν εναλλακτικό ορισμό του δισυνεκτικού δεντροβάθους, εμπνευσμένο από τον χαρακτηρισμό του δεντροβάθους μέσω των ασθενών χρωματικών αριθμών. Αντί να περιγράφουμε την παράμετρο μέσω διαγραφής κορυφών, ερμηνεύουμε εκ νέου τη διαδικασία ως διαγραφή συνόλων ακμών που αντιστοιχούν στις προσπίπτουσες ακμές των κορυφών. Αυτά τα σύνολα ακμών σχηματίζουν φυσικά αστέρια, γεγονός που οδηγεί σε μια διατύπωση βασισμένη σε αστροδιαμερίσεις του συνόλου των ακμών, σε συνδυασμό με έγκυρες σειρές διαγραφής αυτών των αστέρων. Αυτή η οπτική γωνία παρέχει μια σαφέστερη ερμηνεία της διαδικασίας διαγραφής. Επίσης, εισάγουμε και μελετάμε μια νέα παράμετρο γραφημάτων που ονομάζεται αφαίρεση κορυφών προς αστροδάσος. Για ένα γράφημα G, η παράμετρος αυτή μετρά τον ελάχιστο αριθμό κορυφών των οποίων η αφαίρεση μετασχηματίζει το G σε ένα δάσος του οποίου οι συνεκτικές συνιστώσες είναι αστέρια. Η παράμετρος αυτή αποτελεί μέρος μιας ευρύτερης οικογένειας παραμέτρων, των αφαίρεση κορυφών προς d-δάσος, όπου το εναπομείναν γράφημα απαιτείται να είναι ένα δάσος φραγμένου βάθους d, αποτελώντας περιορισμό του συνόλου ανάδρασης κορυφών. Η περίπτωση του δάσους αστεριών αντιστοιχεί στην ειδική περίπτωση όπου το βάθος είναι το πολύ δύο. Η κύρια αλγοριθμική συνεισφορά αυτής της διατριβής αφορά την παραμετρική πολυπλοκότητα του προβλήματος απόφασης ΔΙΣΥΝΕΚΤΙΚΟ ΔΕΝΤΡΟΒΑΘΟΣ. Συγκεκριμένα, εξετάζουμε το πρόβλημα όταν αυτό παραμετροποιείται από τον αριθμό αφαίρεσης κορυφών για αστροδάσος. Χρησιμοποιώντας μια σειρά ειδικά σχεδιασμένων κανόνων αναγωγής, αναπτύσσουμε έναν αλγόριθμο πυρηνοποίησης που ανάγει κάθε στιγμιότυπο σε ένα ισοδύναμο στιγμιότυπο του οποίου το μέγεθος φράσσεται πολυωνυμικά από την παράμετρο. Κατά συνέπεια, το πρόβλημα είναι παραμετρικά βατό (FPT) ως προς αυτή την παράμετρο.","abstract_has_math":false,"creators":["Κυπραίος Ηλίας","Kypraios Ilias"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-07-24T01:02:17Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["Ελληνικά","English","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:5373775"],"render_values":[{"text":"uoadl:5373775","href":null,"code":true}]}]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/5373775","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Κυπραίος Ηλίας","Kypraios Ilias"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2026"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","English","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:5373775","https://pergamos.lib.uoa.gr/uoa/dl/object/5373775"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Οι δομικές παράμετροι γραφημάτων διαδραματίζουν κεντρικό ρόλο στη σύγχρονη Θεωρία Γραφημάτων και τον σχεδιασμό αλγορίθμων. Παρέχουν έναν τρόπο μέτρησης της δομικής πολυπλοκότητας των γραφημάτων και συχνά επιτρέπουν σε υπολογιστικά δύσκολα προβλήματα να καταστούν επιλύσιμα όταν η παράμετρος είναι μικρή. Στο πλαίσιο της Παραμετρικής Πολυπλοκότητας, πολλά κλασικά NP-δύσκολα προβλήματα επιδέχονται αποδοτικούς αλγορίθμους όταν περιορίζονται σε γραφήματα με φραγμένες δομικές παραμέτρους. Σε αυτή τη διατριβή, μελετάμε το δισυνεκτικό δεντροβάθος, μια γενίκευση του δεντροβάθους όπου η αφαίρεση κορυφών συμβαίνει στα τεμάχια του δοθέντος γραφήματος, τόσο από δομική όσο και από αλγοριθμική σκοπιά. Αρχικά, παρουσιάζουμε έναν εναλλακτικό ορισμό του δισυνεκτικού δεντροβάθους, εμπνευσμένο από τον χαρακτηρισμό του δεντροβάθους μέσω των ασθενών χρωματικών αριθμών. Αντί να περιγράφουμε την παράμετρο μέσω διαγραφής κορυφών, ερμηνεύουμε εκ νέου τη διαδικασία ως διαγραφή συνόλων ακμών που αντιστοιχούν στις προσπίπτουσες ακμές των κορυφών. Αυτά τα σύνολα ακμών σχηματίζουν φυσικά αστέρια, γεγονός που οδηγεί σε μια διατύπωση βασισμένη σε αστροδιαμερίσεις του συνόλου των ακμών, σε συνδυασμό με έγκυρες σειρές διαγραφής αυτών των αστέρων. Αυτή η οπτική γωνία παρέχει μια σαφέστερη ερμηνεία της διαδικασίας διαγραφής. Επίσης, εισάγουμε και μελετάμε μια νέα παράμετρο γραφημάτων που ονομάζεται αφαίρεση κορυφών προς αστροδάσος. Για ένα γράφημα G, η παράμετρος αυτή μετρά τον ελάχιστο αριθμό κορυφών των οποίων η αφαίρεση μετασχηματίζει το G σε ένα δάσος του οποίου οι συνεκτικές συνιστώσες είναι αστέρια. Η παράμετρος αυτή αποτελεί μέρος μιας ευρύτερης οικογένειας παραμέτρων, των αφαίρεση κορυφών προς d-δάσος, όπου το εναπομείναν γράφημα απαιτείται να είναι ένα δάσος φραγμένου βάθους d, αποτελώντας περιορισμό του συνόλου ανάδρασης κορυφών. Η περίπτωση του δάσους αστεριών αντιστοιχεί στην ειδική περίπτωση όπου το βάθος είναι το πολύ δύο. Η κύρια αλγοριθμική συνεισφορά αυτής της διατριβής αφορά την παραμετρική πολυπλοκότητα του προβλήματος απόφασης ΔΙΣΥΝΕΚΤΙΚΟ ΔΕΝΤΡΟΒΑΘΟΣ. Συγκεκριμένα, εξετάζουμε το πρόβλημα όταν αυτό παραμετροποιείται από τον αριθμό αφαίρεσης κορυφών για αστροδάσος. Χρησιμοποιώντας μια σειρά ειδικά σχεδιασμένων κανόνων αναγωγής, αναπτύσσουμε έναν αλγόριθμο πυρηνοποίησης που ανάγει κάθε στιγμιότυπο σε ένα ισοδύναμο στιγμιότυπο του οποίου το μέγεθος φράσσεται πολυωνυμικά από την παράμετρο. Κατά συνέπεια, το πρόβλημα είναι παραμετρικά βατό (FPT) ως προς αυτή την παράμετρο.","Structural parameters of graphs play a central role in modern graph theory and algorithm design. They provide a way to measure the structural complexity of graphs and often allow computationally hard problems to become tractable when the parameter is small. Within the framework of parameterized complexity, many classical NP-hard problems admit efficient algorithms when restricted to graphs of bounded structural parameters. In this thesis, we study block treedepth, a generalization of treedepth where vertex removal occurs at the blocks of the given graph, from both structural and algorithmic perspectives. First, we present an alternative definition of block treedepth that is inspired by the characterization of treedepth via weak coloring numbers. Instead of describing the parameter through vertex deletions, we reinterpret the process in terms of deleting sets of edges that correspond to the incident edges of vertices. These edge sets naturally form stars, which leads to a formulation based on star partitions of the edge set together with valid deletion orders of these stars. This viewpoint provides a clearer interpretation of the deletion process. We also introduce and study a new graph parameter called vertex deletion to starforest. For a graph G, this parameter measures the minimum number of vertices whose removal transforms G into a forest whose connected components are stars. The parameter forms part of a broader family of parameters, vertex deletion to d-forest, where the remaining graph is required to be a forest of bounded depth d as well as a restriction of feedback vertex set. The star-forest case corresponds to the special case where the depth is at most two. The main algorithmic contribution of this thesis concerns the parameterized complexity of the BLOCK TREEDEPTH decision problem. In particular, we investigate the problem when it is parameterized by the vertex deletion to star-forest number. Using a series of tailor-made reduction rules, we develop a kernelization algorithm that reduces any instance to an equivalent instance whose size is bounded polynomially by the parameter. As a consequence, the problem is fixed-parameter tractable with respect to this parameter."]},{"key":"dc:title","label":"Title","values":["Parameterizing Block Treedepth by Bounded Depth Forest Deletion"]}]}],"canonical_facts":{"dc:creator":["Κυπραίος Ηλίας","Kypraios Ilias"],"dc:date":["2026"],"dc:description":["Οι δομικές παράμετροι γραφημάτων διαδραματίζουν κεντρικό ρόλο στη σύγχρονη Θεωρία Γραφημάτων και τον σχεδιασμό αλγορίθμων. Παρέχουν έναν τρόπο μέτρησης της δομικής πολυπλοκότητας των γραφημάτων και συχνά επιτρέπουν σε υπολογιστικά δύσκολα προβλήματα να καταστούν επιλύσιμα όταν η παράμετρος είναι μικρή. Στο πλαίσιο της Παραμετρικής Πολυπλοκότητας, πολλά κλασικά NP-δύσκολα προβλήματα επιδέχονται αποδοτικούς αλγορίθμους όταν περιορίζονται σε γραφήματα με φραγμένες δομικές παραμέτρους. Σε αυτή τη διατριβή, μελετάμε το δισυνεκτικό δεντροβάθος, μια γενίκευση του δεντροβάθους όπου η αφαίρεση κορυφών συμβαίνει στα τεμάχια του δοθέντος γραφήματος, τόσο από δομική όσο και από αλγοριθμική σκοπιά. Αρχικά, παρουσιάζουμε έναν εναλλακτικό ορισμό του δισυνεκτικού δεντροβάθους, εμπνευσμένο από τον χαρακτηρισμό του δεντροβάθους μέσω των ασθενών χρωματικών αριθμών. Αντί να περιγράφουμε την παράμετρο μέσω διαγραφής κορυφών, ερμηνεύουμε εκ νέου τη διαδικασία ως διαγραφή συνόλων ακμών που αντιστοιχούν στις προσπίπτουσες ακμές των κορυφών. Αυτά τα σύνολα ακμών σχηματίζουν φυσικά αστέρια, γεγονός που οδηγεί σε μια διατύπωση βασισμένη σε αστροδιαμερίσεις του συνόλου των ακμών, σε συνδυασμό με έγκυρες σειρές διαγραφής αυτών των αστέρων. Αυτή η οπτική γωνία παρέχει μια σαφέστερη ερμηνεία της διαδικασίας διαγραφής. Επίσης, εισάγουμε και μελετάμε μια νέα παράμετρο γραφημάτων που ονομάζεται αφαίρεση κορυφών προς αστροδάσος. Για ένα γράφημα G, η παράμετρος αυτή μετρά τον ελάχιστο αριθμό κορυφών των οποίων η αφαίρεση μετασχηματίζει το G σε ένα δάσος του οποίου οι συνεκτικές συνιστώσες είναι αστέρια. Η παράμετρος αυτή αποτελεί μέρος μιας ευρύτερης οικογένειας παραμέτρων, των αφαίρεση κορυφών προς d-δάσος, όπου το εναπομείναν γράφημα απαιτείται να είναι ένα δάσος φραγμένου βάθους d, αποτελώντας περιορισμό του συνόλου ανάδρασης κορυφών. Η περίπτωση του δάσους αστεριών αντιστοιχεί στην ειδική περίπτωση όπου το βάθος είναι το πολύ δύο. Η κύρια αλγοριθμική συνεισφορά αυτής της διατριβής αφορά την παραμετρική πολυπλοκότητα του προβλήματος απόφασης ΔΙΣΥΝΕΚΤΙΚΟ ΔΕΝΤΡΟΒΑΘΟΣ. Συγκεκριμένα, εξετάζουμε το πρόβλημα όταν αυτό παραμετροποιείται από τον αριθμό αφαίρεσης κορυφών για αστροδάσος. Χρησιμοποιώντας μια σειρά ειδικά σχεδιασμένων κανόνων αναγωγής, αναπτύσσουμε έναν αλγόριθμο πυρηνοποίησης που ανάγει κάθε στιγμιότυπο σε ένα ισοδύναμο στιγμιότυπο του οποίου το μέγεθος φράσσεται πολυωνυμικά από την παράμετρο. Κατά συνέπεια, το πρόβλημα είναι παραμετρικά βατό (FPT) ως προς αυτή την παράμετρο.","Structural parameters of graphs play a central role in modern graph theory and algorithm design. They provide a way to measure the structural complexity of graphs and often allow computationally hard problems to become tractable when the parameter is small. Within the framework of parameterized complexity, many classical NP-hard problems admit efficient algorithms when restricted to graphs of bounded structural parameters. In this thesis, we study block treedepth, a generalization of treedepth where vertex removal occurs at the blocks of the given graph, from both structural and algorithmic perspectives. First, we present an alternative definition of block treedepth that is inspired by the characterization of treedepth via weak coloring numbers. Instead of describing the parameter through vertex deletions, we reinterpret the process in terms of deleting sets of edges that correspond to the incident edges of vertices. These edge sets naturally form stars, which leads to a formulation based on star partitions of the edge set together with valid deletion orders of these stars. This viewpoint provides a clearer interpretation of the deletion process. We also introduce and study a new graph parameter called vertex deletion to starforest. For a graph G, this parameter measures the minimum number of vertices whose removal transforms G into a forest whose connected components are stars. The parameter forms part of a broader family of parameters, vertex deletion to d-forest, where the remaining graph is required to be a forest of bounded depth d as well as a restriction of feedback vertex set. The star-forest case corresponds to the special case where the depth is at most two. The main algorithmic contribution of this thesis concerns the parameterized complexity of the BLOCK TREEDEPTH decision problem. In particular, we investigate the problem when it is parameterized by the vertex deletion to star-forest number. Using a series of tailor-made reduction rules, we develop a kernelization algorithm that reduces any instance to an equivalent instance whose size is bounded polynomially by the parameter. As a consequence, the problem is fixed-parameter tractable with respect to this parameter."],"dc:identifier":["uoadl:5373775","https://pergamos.lib.uoa.gr/uoa/dl/object/5373775"],"dc:language":["Ελληνικά","English","Greek"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Parameterizing Block Treedepth by Bounded Depth Forest Deletion"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-07-24T01:02:17Z"}