Cross and Part : Beyond the Known Boundaries [HBNI Th197]

Abstract

This thesis is divided into two parts, and deals with the parameterized complexity analysis of two classes of problems: (i) graph partitioning problems and (ii) crossing minimisation problems. The first of these, graph partitioning problems, involve testing whether it is possible to partition the vertex set of a graph subject to a set of constraints, or testing whether it is possible to modify a graph slightly by way of vertex deletions, edge deletions etc. so that the vertex set of the resulting graph can be partitioned subject to a set of constraints. A large number of problems in algorithmic graph theory fall into these two categories, and have been studied extensively in the parameterized complexity frame-work. The first part of this thesis considers two problems of the first type, specifically, ABOVE GUARANTEE M AX -CUT and MINIMUM DIRECTED BISECTION , and a family of problems of the second type, specifically DELETION TO LIST M ATRIX P ARTITION . Our first problem involves testing whether an n-vertex connected graph has a cut of size at least n 1 + k. And the second problem involves testing whether a semicomplete digraph has a bisection of size at most k. We show that both the problems are fixed-parameter tractable (when parameterized by k), and that they admit polynomial kernels. In particular, we show that the latter problem, i.e., the MINIMUM DIRECTED BISECTION problem on semicomplete digraphs, admits a sub-exponential time (i.e., 2 o(k) n O(1) time) algorithm, a rather uncommon feature for a parameterized problem (except for problems on planar graphs). And to design our kernel for this problem, we use splitters, a commonly used pseudorandom object. We also study the “deletion version” of the LIST MATRIX PARTITION problem, introduced by Feder et al. [STOC 1999 and SIAM J. Discrete Math.

2003]. Here, the goal is to check if k vertices can be deleted from a given graph so that the vertices of the resulting graph can be partitioned subject to a set of constraints, where the constraints are dictated by a (fixed) symmetric matrix M over {0, 1, ⇤}. This problem generalises many widely-studied problems in algorithmic graph theory such as VERTEX COVER , SPLIT VERTEX DELETION , MULTIWAY CUT (with a constant number of terminals) etc. We establish an almost complete classification (into P, para-NP-hard, quasi-FPT or FPT) of the parameterized complexity of the DELETION TO LIST M-PARTITION problem, when M is of order at most 3 and when M is of order 4 and has only 0s and 1s as diagonal entries.

The second part of the thesis deals with crossing minimisation problems. Here, the goal is to test if a given graph embedded in the plane contains a certain subgraph with at most a given number of pairwise edge crossings. We restrict our study to the case when the input graph is bipartite and has a particular embedding called a two-layered embedding. A two-layered embedding of a bipartite graph G with vertex bipartition V (G) = X [ Y is a drawing of G in the plane where the vertices of X are placed at (distinct) points on a straight line L X and the vertices of Y at (distinct) points on another straight line L Y , such that L X and L Y are parallel to each other. The edges are embedded as line segments between their endpoints. And a crossing in a two-layered graph is a pair of edges that intersect at a point other than their possible common endpoint. We study the parameterized complexity of the following two problems. (i) Given an n-vertex two- layered graph and a non-negative integer k, does G contain a perfect matching with at most k crossings? And (ii) given an n-vertex two-layered graph, a pair of vertices s,t 2 V (G) and a non-negative integer k, does G contain a path from s to t with at most k crossings? We show that when parametrized by k, the former problem admits a sub-exponential time parameterized algorithm and a quadratic kernel, whereas the latter problem is W[1]-hard, but admits an XP algorithm.