Connected and Disconnected Matchings

Abstract

Matching problems in graphs have been studied for a long time, achieving important results in both theoretical and practical aspects. Over the decades, many variations of matching problems were studied. Some of them can be solved in polynomial time, while others can not, unless P = NP. In this thesis, we briefly present the history of matchings and a survey of some of its variations along with its state of the art. We also give results on one of these variations: P-matchings. A matching M is a P- matching if the subgraph induced by the endpoints of the edges of M satisfies property P. As examples, for appropriate choices of P, the problems Induced Matching, Uniquely Restricted Matching, Acyclic Matching, Connected Matching and Disconnected Matching arise. For many of these problems, finding a maximum P-matching is a knowingly NP-hard problem. Two exceptions, that are the focus of this thesis, are connected matchings and disconnected matchings, where P is that the graph is connected and disconnected, respectively. While we can obtain a maximum connected matching in polynomial time, the complexity of finding a maximum disconnected matching was still unknown, though asked since 2005 by Goddard, Hedetniemi, Hedetniemi, and Laskar [Generalized subgraph-restricted matchings in graphs, Discrete Mathematics, 293 (2005) 129 – 138]. In this thesis, we answer this question. In fact, we consider the generalized problem of finding c-disconnected matchings; such matchings are ones whose vertex sets induce subgraphs with at least c connected components. We show that, for every fixed c ≥ 2, this problem is NP-complete even if we restrict the input to bounded diameter bipartite graphs, while can be solved in polynomial time if c = 1. For the case when c is part of the input, we show that the problem is NP-complete for chordal graphs and bounded degree graphs while being solvable in polynomial time for interval graphs. Then, we explore the parameterized complexity of the problem. We present an FPT algorithm under the treewidth parameterization, and an XP algorithm for graphs with a polynomial number of minimal separators when parameterized by c. We complement these results by showing that, unless NP ⊆ coNP=poly, the related Induced Matching problem does not admit a polynomial kernel when parameterized by vertex cover and size of the matching nor when parameterized by vertex deletion distance to clique and size of the matching. As for connected matchings, we give a linear-time algorithm for finding a maximum connected matching if a maximum matching is given. So, we turn our attention to a generalization of connected matchings that considers edge-weighted graphs and whose problem we name Maximum Weight Connected Matching. This problem is motivated by the usual Maximum Weight Matching, studied for decades, and with many applications, including the well-known Assignment problem. Besides, some other P-matchings, such as acyclic matchings and induced matchings, were also considered under weighted graphs before. In Maximum Weight Connected Matching, we want to find a matching M such that the endpoints of its edges induce a connected subgraph and the sum of the edge weights of M is maximum. Unlike the unweighted Connected Matching problem, which can be solved in polynomial time for general graphs, we show that Maximum Weight Connected Matching is NP-hard even for bounded diameter bipartite graphs, starlike graphs, planar bipartite graphs, and subcubic planar graphs, while solvable in linear time for trees and graphs having a degree at most two. When we restrict edge weights to be non-negative only, we show that the problem turns out to be polynomially solvable for chordal graphs, while it remains NP-hard for most of the other cases. We also consider the parameterized complexity of Maximum Weight Connected Matching. On the positive side, we present a single exponential time algorithm when parameterized by treewidth. As for kernelization, we show that, even when restricted to binary weights, its decision problem, Weighted Connected Matching, does not admit a polynomial kernel when parameterized by vertex cover number under standard complexity-theoretical hypotheses.