Back to search

University of Ioannina

Path and cycle hitting problems: algorithms and complexity

Abstract

dc:description

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.

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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/56381

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Tzimas, Spyridon; Τζίμας, Σπυρίδων. Path and cycle hitting problems: algorithms and complexity. University of Ioannina, 2024. http://hdl.handle.net/10442/hedi/56381