Path and cycle hitting problems: algorithms and complexity

Abstract

Most graph-theoretic problems are known to be NP-complete on general graphs. It is considered unlikely that there exist polynomial-time algorithms for solving them. Motivated by the fact that many of these problems have real-world applications, researchers have been primarily focused on designing faster and faster exact exponential-time algorithms and better and better approximation algorithms for solving them. Another direction of research - the one that we follow in this thesis -, which gained a lot of momentum in recent years due to the discovery of new powerful tools within the framework of Parameterized Complexity, is to study these problems on particular graphs that exhibit various kinds of internal structure. By designing algorithms that leverage this internal structure, we may provide better running time and/or solution quality guarantees on these particular graphs. We may also show that a problem's hardness persists on these graphs, thusly yielding further insight into the kinds of structure that make the problem hard to solve. In this thesis, we study terminal set problems: given a (vertex-weighted) graph and a vertex subset of the graph, called the terminal set, we search for a minimum-sized (minimum-weighted) vertex subset of the graph which intersects (hits) every vertex subset of the graph that contains a terminal and induces a subgraph exhibiting a particular structure dependent on the problem. This class of problems contains prominent graph-theoretic problems which have applications both within and beyond the field of Computer Science. We focus our study on two particular problems. The one is a cycle hitting problem and is known in the relevant literature as the subset feedback vertex set (SFVS) problem: given a (vertex-weighted) graph and a terminal set, we search for a minimum-sized (minimum-weighted) vertex subset of the graph which hits every vertex subset of the graph that contains a terminal and induces a cycle. We study SFVS on subclasses of AT-free graphs and on subclasses of chordal graphs, which are graphs that are known to exhibit rich internal structure. We provide polynomial-time algorithms for solving weighted SFVS on the following graph classes: interval graphs, permutation graphs, cobipartite graphs and rooted path graphs. And we show that unweighted SFVS is NP-complete on undirected path graphs. Moreover, for weighted SFVS, we provide an algorithm for solving it on graphs with leafage at most k and we show that it is W[1]-hard parameterized by k. We also study SFVS on H-free graphs, which are graphs that exhibit a kind of internal structure as a result of absence of another. For weighted SFVS, we provide a polynomial-time algorithm for solving it on 4K_{1}-free graphs and we show that it is NP-complete on 5K_{1}-free graphs. For unweighted SFVS, we provide an algorithm for solving it on (k+1)K_{1}-free graphs. SFVS consists a generalization of the classical feedback vertex set (FVS) problem: given a (vertex-weighted) graph, we search for a minimum-sized (minimum-weighted) vertex subset of the graph which hits every vertex subset of the graph that induces a cycle. Weighted FVS is known to be polynomial-time solvable on AT-free graphs and on chordal graphs. We provide an algorithm for solving it on (k+1)K_{1}-free graphs and for unweighted FVS, we show that it is W[1]-hard parameterized by k via a reduction which is different than the one existing in the literature. The other problem that we focus on is a path hitting problem and is known in the relevant literature as the node multiway cut (NMC) problem: given a (vertex-weighted) graph and a terminal set, we search for a minimum-sized (minimum-weighted) terminal-free vertex subset of the graph which hits every vertex subset of the graph that induces a path between two terminals. For unweighted NMC, we provide a polynomial-time algorithm for solving it on 3K_{1}-free graphs and show that it is NP-complete on 4K_{1}-free graphs via a reduction which relies on the constraint that the solution to NMC is terminal-free. Motivated by this fact, we also consider NMC without this constraint and we call it the unconstrained node multiway cut (UNMC) problem. For weighted UNMC, we provide a polynomial-time algorithm for solving it on 3K_{1}-free graphs and we show that it is NP-complete on 4K_{1}-free graphs. For unweighted UNMC, we provide an algorithm for solving it on (k+1)K_{1}-free graphs and we show that it is W[1]-hard parameterized by k. This thesis is structured as follows: Chapter 1 consists an introduction to the subject of study. Part I provides the necessary theoretical background: Elements of Complexity Theory and Graph Theory are given in Chapters 2 and 3 respectively and the definitions of the studied graph-theoretical problems along with previously known results on their complexity are given in Chapter 4. Part II provides our algorithmic and complexity-theoretic results: After providing the necessary preliminaries in Chapter 5, we present our results on subclasses of AT-free graphs, on subclasses of chordal graphs and on H-free graphs in Chapters 6, 7 and 8 respectively. Chapter 9 concludes our thesis with some remarks and open problems providing directions for future research.

Τα περισσότερα γραφοθεωρητικά προβλήματα είναι γνωστό πως είναι NP-πλήρη στα γενικά γραφήματα. Δεν θεωρείται πίθανο να υπάρχει αλγόριθμος πολυωνυμικού χρόνου για την επίλυσή τους. Με κίνητρο το γεγονός ότι πολλά από αυτά τα προβλήματα έχουν εφαρμογές στον πραγματικό κόσμο, οι ερευνητές έχουν επικεντρωθεί στην σχεδίαση όλο και γρηγορότερων ακριβών αλγορίθμων εκθετικού χρόνου και όλο και καλύτερων προσεγγιστικών αλγορίθμων για την επίλυσής τους. Μία άλλη κατεύθυνση της έρευνας - αυτή που ακολουθούμε στην παρούσα διατριβή -, η οποία έλαβε μεγάλη ώθηση τα τελευταία χρόνια λόγω της ανακάλυψης νέων ισχυρών εργαλείων στο πλαίσιο της Παραμετροποιημένης Πολυπλοκότητας, είναι η μελέτη αυτών των προβλημάτων σε συγκεκριμένα γραφήματα που εμφανίζουν διαφόρων ειδών εσωτερική δομή. Σχεδιάζοντας αλγορίθμους που εκμεταλλεύονται αυτή την εσωτερική δομή, ενδέχεται να παράσχουμε καλύτερες εγγυήσεις σε χρόνο εκτέλεσης ή/και ποιότητα λύσης σε αυτά τα συγκεκριμένα γραφήματα. Ενδέχεται επίσης να δείξουμε ότι η δυσκολία ενός προβλήματος διατηρείται σε αυτά τα γραφήματα, παράγοντας με αυτόν τον τρόπο περαιτέρω γνώση πάνω στα είδη δομής που κάνουν το πρόβλημα δύσκολο στην επίλυση. Στην παρούσα διατριβή, μελετούμε προβλήματα συνόλου τερματικών κορυφών: δοθέντων ενός γραφήματος (με βάρη στις κορυφές) και ενός υποσυνόλου κορυφών των γραφήματος, που καλείται το σύνολο τερματικών κορυφών, αναζητούμε υποσύνολο κορυφών του γραφήματος ελαχίστου μεγέθους (βάρους) το οποίο τέμνει (κρούει) κάθε υποσύνολο κορυφών των γραφήματος που περιέχει τερματική κορυφή και επάγει υπογράφημα που εμφανίζει συγκεκριμένη δομή που εξαρτάται από το πρόβλημα. Αυτή η κλάση προβλημάτων περιέχει εξέχοντα γραφοθεωρητικά προβλήματα τα οποία έχουν εφαρμογές τόσο εντός όσο και πέραν της Επιστήμης Υπολογιστών. Εστιάζουμε την μελέτη μας σε δύο συγκεκριμένα προβλήματα. Το ένα είναι πρόβλημα κρούσης κύκλων και είναι γνωστό στην σχετική βιβλιογραφία ως το πρόβλημα στοχευμένα άκυκλου επαγόμενου υπογραφήματος (SFVS): δοθέντων ενός γραφήματος (με βάρη στις κορυφές) και ενός συνόλου τερματικών κορυφών, αναζητούμε υποσύνολο κορυφών του γραφήματος ελαχίστου μεγέθους (βάρους) το οποίο κρούει κάθε υποσύνολο κορυφών του γραφήματος που περιέχει τερματική κορυφή και επάγει κύκλο. Μελετούμε το SFVS σε υποκλάσεις των AT-ελεύθερων γραφημάτων και σε υποκλάσεις των χορδικών γραφημάτων, τα οποία είναι γραφήματα που είναι γνωστό ότι εμφανίζουν πλούσια εσωτερική δομή. Παρέχουμε αλγορίθμους πολυωνυμικού χρόνου για την επίλυση του έμβαρου SFVS στις ακόλουθες κλάσεις γραφημάτων: γραφήματα διαστημάτων, γραφήματα μεταθέσεων, συνδιμερή γραφήματα και γραφήματα μονοπατιών ριζωμένων δένδρων. Kαι δείχνουμε ότι το μη-έμβαρο SFVS είναι NP-πλήρες στα γραφήματα μονοπατιών μη-κατευθυντικών δένδρων. Επιπλέον, για το έμβαρο SFVS, παρέχουμε έναν αλγόριθμο για την επίλυση του στα γραφήματα με φύλλωμα το πολύ k και δείχνουμε είναι W[1]-δύσκολο παραμετροποιημένο από το k. Μελετούμε επίσης το SFVS στα H-ελεύθερα γραφήματα, τα οποία είναι γραφήματα που εμφανίζουν ένα είδος εσωτερικής δομής ως αποτέλεσμα απουσίας ενός άλλου. Για το έμβαρο SFVS, παρέχουμε έναν αλγόριθμο πολυωνυμικού χρόνου για την επίλυση του στα 4K_{1}-ελεύθερα γραφήματα και δείχνουμε ότι είναι NP-πλήρες στα 5K_{1}-ελεύθερα γραφήματα. Για το μη-έμβαρο SFVS, παρέχουμε έναν αλγόριθμο για την επίλυση του στα (k+1)K_{1}-ελεύθερα γραφήματα. Το SFVS αποτελεί γενίκευση του κλασικού προβλήματος άκυκλου επαγόμενου υπογραφήματος (FVS): δοθέντων ενός γραφήματος (με βάρη στις κορυφές), αναζητούμε υποσύνολο κορυφών του γραφήματος ελαχίστου μεγέθους (βάρους) το οποίο κρούει κάθε υποσύνολο κορυφών του γραφήματος που επάγει κύκλο. Το έμβαρο FVS είναι γνωστό πως είναι επιλύσιμο σε πολυωνυμικό χρόνο στα AT-ελεύθερα γραφήματα και στα χορδικά γραφήματα. Παρέχουμε έναν αλγόριθμο για την επίλυση του στα (k+1)K_{1}-ελεύθερα γραφήματα και για το μη-έμβαρο FVS, δείχνουμε ότι είναι W[1]-δύσκολο παραμετροποιημένο από το k μέσω μίας αναγωγής η οποία είναι διαφορετική από αυτή που υπάρχει στη βιβλιογραφία. Το άλλο πρόβλημα στο οποίο εστιάζουμε είναι ένα πρόβλημα κρούσης μονοπατιών και είναι γνωστό στη σχετική βιβλιογραφία ως το πρόβλημα διαχωρισμού συνόλου κορυφών (NMC): δοθέντων ενός γραφήματος (με βάρη στις κορυφές) και ένα σύνολο τερματικών κορυφών, αναζητούμε υποσύνολο κορυφών του γραφήματος ελαχίστου μεγέθους (βάρους) το οποίο δεν περιέχει τερματικές κορυφές και κρούει κάθε υποσύνολο κορυφών του γραφήματος που επάγει μονοπάτι μεταξύ δύο τερματικών κορυφών. Για το μη-έμβαρο NMC, παρέχουμε έναν αλγόριθμο πολυωνυμικού χρόνου για την επίλυση του στα 3K_{1}-ελεύθερα γραφήματα και δείχνουμε ότι είναι np-πλήρες στα 4K_{1}-ελεύθερα γραφήματα μέσω μίας αναγωγής η οποία στηρίζεται στον περιορισμό ότι η λύση στο NMC δεν περιέχει τερματικές κορυφές. Με κίνητρο αυτό το γεγονός, θεωρούμε επίσης το NMC χωρίς αυτόν τον περιορισμό και το καλούμε πρόβλημα απεριόριστου διαχωρισμού συνόλου κορυφών (UNMC). Για το έμβαρο UNMC, παρέχουμε έναν αλγόριθμο πολυωνυμικού χρόνου για την επίλυση του στα 3K_{1}-ελεύθερα γραφήματα και δείχνουμε ότι είναι NP-πλήρες στα 4K_{1}-ελεύθερα γραφήματα. Για το μη-έμβαρο UNMC, παρέχουμε έναν αλγόριθμο για την επίλυση του στα (k+1)K_{1}-ελεύθερα γραφήματα και δείχνουμε ότι είναι W[1]-δύσκολο παραμετροποιημένο από το k. Η παρούσα διατριβή δομείται ως ακολούθως: Το Κεφάλαιο 1 αποτελεί μια εισαγωγή στο αντικείμενο μελέτης. Το Μέρος I παρέχει το απαραίτητο θεωρητικό υπόβαθρο: Στοιχεία της Θεωρίας Πολυπλοκότητας και της Θεωρίας Γραφημάτων δίνονται στα Κεφάλαια 2 και 3 αντίστοιχα και οι ορισμοί των υπό μελέτη προβλημάτων μαζί με προηγουμένως γνωστά αποτελέσματα σχετικά με την πολυπλοκότητά τους δίνονται στο Κεφάλαιο 4. Το Μέρος II παρέχει τα αποτελέσματα μας σε αλγορίθμους και πολυπλοκότητα: Μετά την παροχή των απαραίτητων προκαταρκτικών στο Κεφάλαιο 5, παρουσιάζουμε τα αποτελέσματά μας σε υποκλάσεις των AT-ελεύθερων γραφημάτων, σε υποκλάσεις των χορδικών γραφημάτων και σε Η-ελεύθερα γραφήματα στα Κεφάλαια 6, 7 και 8 αντίστοιχα. Το Κεφάλαιο 9 ολοκληρώνει την διατριβή μας με μερικά σχόλια και ανοικτά προβλήματα που παρέχουν κατευθύνσεις για μελλοντική έρευνα.