Cutting-Edge Algorithms for Monotone Graph Classes

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.