Cutting-Edge Algorithms for Monotone Graph Classes

Sukanya Pandey

Research output: ThesisDoctoral thesis 1 (Research UU / Graduation UU)

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 languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Utrecht University
Supervisors/Advisors
  • Bodlaender, Hans, Supervisor
  • van Leeuwen, Erik Jan, Co-supervisor
Award date21 Oct 2024
Place of PublicationUtrecht
Publisher
Electronic ISBNs978-94-6510-268-9
DOIs
Publication statusPublished - 21 Oct 2024

Keywords

  • Algorithm Design
  • Graph Theory
  • Parameterized Complexity
  • Graph Classes
  • Algorithmic Graph Theory
  • Structural Graph Theory

Fingerprint

Dive into the research topics of 'Cutting-Edge Algorithms for Monotone Graph Classes'. Together they form a unique fingerprint.

Cite this