Abstract
In this thesis, we continue the research on well-known NP-hard problems
by looking at them from two lenses, namely, parameterized complexity and
restriction of input to classes of graphs forbidding certain subgraphs. In the first part, we study the parameterized as well as classical complexity of the well-known problem Edge-Multiway Cut with input restricted to planar graphs. We show that for the parameter terminal face cover number, we can solve Edge Multiway Cut in subexponential time. We also show that both Edge and Node Multiway Cut are NP-hard on planar, subcubic graphs.
In the second part, we describe a framework to classify the complexity of problems on H-subgraph-free graphs. We demonstrate that a large number of well-known problem fit into this framework. We end this part with the study of the complexity of problems that almost fit the framework, on H-subgraph-free graphs.
Original language | English |
---|---|
Qualification | Doctor of Philosophy |
Awarding Institution |
|
Supervisors/Advisors |
|
Award date | 21 Oct 2024 |
Place of Publication | Utrecht |
Publisher | |
Electronic ISBNs | 978-94-6510-268-9 |
DOIs | |
Publication status | Published - 21 Oct 2024 |
Keywords
- Algorithm Design
- Graph Theory
- Parameterized Complexity
- Graph Classes
- Algorithmic Graph Theory
- Structural Graph Theory