Δοθέντος ενός γραφήματος με βάρη στις κορυφές του ως είσοδο, το (έμβαρο)
πρόβλημα του
ΑκϊΚΛΟΤ
Ε
παγομενοϊ
Τ
πογραφηματος
(F V S ) ζητά την εύρεση
ενός ελαχίστου βάρους υποσυνόλου των κορυφών του γραφήματος εισόδου των
οποίων η αφαίρεση από αυτό έχει ως αποτέλεσμα αυτό να μην έχει πλέον επαγόμε-
νο κύκλο. Το F V S βρίσκεται μεταξύ των κλασσικών προβλημάτων της Αλγοριθ-
μικής Θεωρίας Γραφημάτων και έχει βρει πολλές εφαρμογές σε άλλα γνωστικά
πεδία με το πέρασμα των χρόνων, με εφαρμογές στην ικανοποίηση περιορισμών
και στην Μπεϊσιανή συμπερασματολογία, στην οπτική δικτύωση και στην υπολο
γιστική βιολογία να είναι μερικές πρόσφατες προσθήκες. Ως φυσικό επακόλουθο,
οι αλγόριθμοι επίλυσης του F V S ήταν πάντα αντικείμενο ενεργής έρευνας. Τόσο
ακριβείς όσο και προσεγγιστικοί αλγόριθμοι έχουν προταθεί για την επίλυση του
F V S σε γενικά γραφήματα. Τ ο F V S είναι
NP
-πλήρες στα γενικά γραφήματα,
στα επίπεδα γραφήματα, στα διμερή γραφήματα και στα επίπεδα διμερή γραφήμα
τα. Συνεπώς, το F V S θεωρείται απίθανο να είναι πολυωνυμικά επιλύσιμο σε αυτές
τις κλάσεις γραφημάτων. Αναφέρουμε επίσης πως το F V S είναι
FPT
στα γενικά
γραφήματα. Τ ο F V S είναι πολυωνυμικά επιλύσιμο στα γραφήματα διαστημάτων
σε
Ο(η
+ m) χρόνο, στα γραφήματα μεταθέσεων και στα γραφήματα τραπεζίων
σε O (nm ) χρόνο, στα συνσυγκρίσιμα γραφήματα και στα κυρτά διμερή γραφήμα
τα σε 0 ( n 2m ), στα A T -ελεύθερα γραφήματα σε 0 ( n 8m 2) χρόνο, στα χορδικά
γραφήματα σε Ο (η 6) χρόνο και στα γραφήματα φραγμένου πλάτους κλίκας σε
Ο (η) χρόνο, όπου η και m είναι το πλήθος των κορυφών και των ακμών του
γραφήματος εισόδου αντίστοιχα.
Στην παρούσα διατριβή, μελετούμε μία γενίκευση του F V S που καλείται το
πρόβλημα του
Σ
τοχεϊμενα
Α
κϊκλοϊ
Ε
παγομενοϊ
Υ
πογραφηματος
. Δοθέντω ν
ενός γραφήματος με βάρη στις κορυφές του και ένα υποσύνολο S των κορυφών του
ως είσοδο, το (έμβαρο) πρόβλημα του
Σ
τοχεϊμενα
Α
κϊκλοϊ
Υ
πογραφηματος
(S F V S ) ζητά την εύρεση ενός ελαχίστου βάρους υποσυνόλου των κορυφών του
γραφήματος εισόδου των οποίων η αφαίρεση από αυτό έχει ως αποτέλεσμα αυτό να μην έχει πλέον επαγόμενο κύκλο που να περνά από κορυφή που ανήκει στο S .
Εφόσον οι ενδεχόμενες γενικεύσεις των εφαρμογών του F V S μπορεί να απαιτούν
την επίλυση μίας γενίκευσης του F V S στη θέση του ίδιου του F V S , η έλλειψη α
ποδοτικών αλγορίθμων για την επίλυση του S F V S μπορεί να αποτελεί τροχοπέδη
στην πραγματοποίησή τους. Αυτή η παρατήρηση μας ωθεί να επιδιώξουμε την με
λέτη του S F V S . Τόσο ακριβείς όσο και προσεγγιστικοί αλγόριθμοι έχουν επίσης
προταθεί και για την επίλυση του S F V S σε γενικά γραφήματα. Το γεγονός ότι το
S F V S αποτελεί γενίκευση του F V S συνεπάγεται ότι είναι και αυτό
NP
-πλήρες
στα γενικά γραφήματα, στα επίπεδα γραφήματα, στα διμερή γραφήματα και στα
επίπεδα διμερή γραφήματα. Η πρώτη σημαντική διαφορά στην συμπεριφορά των
δύο προβλημάτων είναι ότι, σε αντίθεση με το F V S το οποίο είναι P στα χορδικά
γραφήματα, έχει δειχθεί ότι το S F V S είναι
NP
-πλήρες στα διαχωρίσιμα γραφήμα
τα, μία υποκλάση των χορδικών γραφημάτων. Επίσης σε αντίθεση με το F V S ,
δεν υπάρχουν πολυωνυμικά αποτέλεσματα όπου η είσοδος περιορίζεται σε κλάσεις
γραφημάτων αναφορικά με το S F V S στη βιβλιογραφία. Στην παρούσα διατριβή,
προτείνουμε νέους αλγορίθμους δυναμικού προγραμματισμού για την επίλυση του
S F V S στα γραφήματα διαστημάτων σε Ο (η + m + 1) χρόνο και στα γραφήματα
μεταθέσεων σε 0 ( m 3) χρόνο, όπου
η, m
και 1
£
Ο (η 3) είναι το πλήθος των
κορυφών, των ακμών και των επαγόμενων τριγώνων του γραφήματος εισόδου
αντίστοιχα— τα πρώτα πολυωνυμικά αποτελέσματα αναφορικά με το S F V S .
Η παρούσα διατριβή είναι δομημένη ως ακολούθως: Το Κεφάλαιο 1 είναι ε
ίναι εισαγωγικό κεφάλαιο που εφοδιάζει όλους τους απαραίτητους ορισμούς από
την Θεωρία Πολυκλοκότητας και την Θεωρία Γραφημάτων. Επίσης φιλοξενεί
πληροφορίες για τα F V S και S F V S . Στο Κεφάλαιο 2, δίνουμε τους καλύτερους
πολυωνυμικούς αλγορίθμους δυναμικού προγραμματισμού για την επίλυση του
F V S στα γραφήματα διαστημάτων και στα γραφήματα μεταθέσεων που υπάρχουν
στη βιβλιογραφία και στη συνέχεια προτείνουμε νέους αλγορίθμους δυναμικού
προγραμματισμού που παρουσιάζουν την ίδια χρονική πολυπλοκότητα και αποτε
λούν τους προπομπούς των αλγορίθμων μας για την επίλυση του S F V S στις ίδιες
κλάσεις γραφημάτων. Το Κεφάλαιο 3 φιλοξενεί τους προαναφερθέντες πολυωνυ-
μικούς αλγορίθμους δυναμικού προγραμματισμού μας για την επίλυση του S F V S
στα γραφήματα διαστημάτων και στα γραφήματα μεταθέσεων. Το Κεφάλαιο 4
ολοκληρώνει την παρούσα διατριβή με μία ενημέρωση της κατάστασης των F V S
και S F V S και μία συζήτηση πάνω σε μελλοντική έρευνα και ανοικτά προβλήματα
αναφορικά με το S F V S . Τέλος, υπάρχει το Παράρτημα Α, ένα παράρτημα που
φιλοξενεί ορισμούς μαθηματικών εννοιών που χρησιμοποιούνται στο κύριο μέρος
της παρούσας διατριβής και οι οποίες μελετώνται σε πεδία των μαθηματικών εκτός
της Θεωρίας Πολυπλοκότητας και της Θεωρίας Γραφημάτων.
(EL)
Given a graph with weights on its vertices as input, the (weighted) Feed- back Vertex Set (FVS) problem asks for a minimum-weight subset of the input graph’s vertices whose removal from it results in it no longer having an induced cycle. FVS finds itself among the classical problems of Algorithmic Graph Theory and has found many applications in other fields of study over the years, with applications in constraint satisfaction and Bayesian inference, optical networking and computational biology being some recent additions. As a natural consequence, FVS solving algorithms have always been a sub- ject of active research. Both exact and approximation algorithms have been
proposed for solving FVS on general graphs. FVS is NP-complete on general
graphs, planar graphs, bipartite graphs and planar bipartite graphs. There-
fore, FVS is considered unlikely to be polynomially solvable on those graphs classes. We also mention that FVS is FPT on general graphs. FVS is poly-
nomially solvable on interval graphs in O(n + m) time, on permutation graphs and trapezoid graphs in O(nm) time, on cocomparability graphs and convex bipartite graphs in O(n2m) time, on AT-free graphs in O(n8m2) time, on chordal graphs in O(n6) time and on graphs of bounded cliquewidth in O(n) time, where n and m are the number of vertices and edges of the input graph respectively.
In this thesis, we study a generalization of FVS called the Subset Feed- back Vertex Set problem. Given a graph with weights on its vertices and a subset S of its vertices as input, the (weighted) Subset Feedback Vertex Set (SFVS) problem asks for a minimum-weight subset of the input graph’s vertices whose removal from it results in it no longer having an induced cycle that passes through a vertex which is an element of S. Since potential gener- alizations of FVS applications may require solving a generalization of FVS in place of FVS itself, the absence of efficient SFVS solving algorithms may ham- per their realisation. The above observation compels us to pursue the study of SFVS. Both exact and approximation algorithms have also been proposed for solving SFVS on general graphs. The fact that SFVS is a generalization of
FVS implies that it is NP-complete on general graphs, planar graphs, bipar-
tite graphs and planar bipartite graphs as well. The first significant difference in the behaviour of the two problems is that, unlike FVS which is P on chordal graphs, SFVS was shown to be NP-complete on split graphs, a subclass of
chordal graphs. Also unlike FVS, there is no polynomial result where the in- put is restricted to graph classes regarding SFVS to be found in literature. In this thesis, we propose novel dynamic programming algorithms for solving SFVS on interval graphs in O(n + m + l) time and on permutation graphs in
O(m3) time, where n, m and l ∈ O(n3) are the number of vertices, edges and
induced triangles of the input graph respectively—the first polynomial results
regarding SFVS.
This thesis is structured as follows: Chapter 1 is an introductory chapter that supplies all the necessary definitions from Complexity Theory and Graph Theory. It also hosts information on FVS and SFVS. In Chapter 2, we give the best polynomial FVS solving dynamic programming algorithms on interval graphs and permutation graphs found in literature and subsequently propose novel dynamic programming algorithms which excibit the same time complex- ity and are the precursors of our algorithms for solving SFVS on the same graph classes. Chapter 3 hosts our aforementioned polynomial SFVS solving dynamic programming algorithms on interval graphs and permutation graphs. Chapter 4 concludes this thesis with an update on the state of FVS and SFVS and a talk on future work and open problems regarding SFVS. Lastly, there is Appendix A, an appendix hosting definitions of mathematical concepts that are used in the main matter of this thesis and which are subjects of fields of mathematics other that Complexity Theory and Graph Theory.
(EN)
