Abstract
dc:descriptionMost 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.
Degree
thesis:*- Grantor dc:publisher
- University of Ioannina
- Year dc:date
- 2024
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Tzimas, Spyridon
- Τζίμας, Σπυρίδων
Subjects
dc:subject × 39- Θεωρία γραφημάτων
- Υπολογιστική πολυπλοκότητα
- Παραμετρική πολυπλοκότητα
- Γραφήματα διαστημάτων
- Γραφήματα μεταθέσεων
- Συνδιμερή γραφήματα
- Γραφήματα μονοπατιών ριζωμένων δένδρων
- Γραφήματα μονοπατιών μη-κατευθυντικών δένδρων
- Χορδικά γραφήματα
- Φύλλωμα
- Αριθμός ανεξάρτητου συνόλου
- Graph theory
- Computational complexity
- Parameterized complexity
- Interval graphs
- Permutation graphs
- Cobipartite graphs
- Rooted path graphs
- Undirected path graphs
- Chordal graphs
- Leafage
- Independent set number
- Feedback vertex set
- Subset feedback vertex set
- Node multiway cut
- Μαθηματικά
- Φυσικές Επιστήμες
- Διακριτά μαθηματικά και Συνδυαστική
- Εφαρμοσμένα μαθηματικά
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμη ηλεκτρονικών υπολογιστών
- Επιστήμη ηλεκτρονικών υπολογιστών, θεωρία και μέθοδοι
- Mathematics
- Natural Sciences
- Discrete Mathematics and Combinatorics
- Applied Mathematics
- Computer and Information Sciences
- Computer Science
- Computer science, theory and methods
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/56381