On (in)tractability of connection and cut problems

Abstract

Connection and cut problems are general graph problems widely studied over the years. Roughly, connection problems aim to obtain a minimum/maximum number of required elements whose inclusion yields a connected graph satisfying certain conditions, while cut problems aims to obtain a minimum/maximum number of required elements whose removal yields a (disconnected) graph with more connected components. This thesis addresses connection and cut problems from the perspective of graph classes and computational complexity. Specifically, we analyse the computational complexity of Terminal connection (TCP), which can be seen as a generalisation of the classical Steiner tree problem. We propose several complexity results for TCP and for its strict variant (S-TCP), when some of the input parameters are fixed, and they are restricted to specific graph classes, such as split graphs, rooted directed path graphs, and graphs of bounded clique-width. We mainly concentrate on results that differentiate the complexity of TCP from the complexity of Steiner tree. Additionally, we analyse the computational complexity of the classical MaxCut problem. We propose the first complexity classification for the problem with respect to interval graphs of bounded interval count, by proving that it remains NP-complete on interval graphs of interval count 4. We also prove that MaxCut is NP-complete on permutation graphs, settling a long-standing open question from Ongoing Guide to NP-completeness by David S. Johnson. Finally, we investigate the complexity of computing the zig-zag number of a directed graph, which is a directed width measure defined over cuts of a graph. We prove that k-zig-zag number is in NP for every fixed k, and that 2-zig-zag number is already an NP-complete problem