Parameterized algorithms for maximum-weight matching

Abstract

Die Methoden der parametrisierte Algorithmentheorie wurden ursprünglich dazu entwickelt Berechnungsprobleme mit super-polynomieller Laufzeit schneller lösen zu können. Diese algorithmischen Methoden können aber auch dazu verwendet werden Algorithmen für polynomielle Berechnungsprobleme zu konstruieren. In dieser Arbeit wenden wir parametrisierte algorithmische Methoden auf das Maximum-Weight-Matching-Problem an. Ein Maximum-Weight-Matching auf einem gewichteten Graphen ist eine Menge von Kanten von maximalem Gewicht, sodass keine zwei Kanten einen gemeinsamen Knoten als Ende haben. Das Berechnungsproblem ein Maximum-Weight-Matching in einem gegebenen gewichteten Graphen zu finden ist ein weit verbreitetes Problem und es existiert ein wohlbekannter Algorithmus, welcher eine Laufzeit in O(n (m + n log n)) aufweist, wobei n die Anzahl der Knoten und m die Anzahl der Kanten im Graphen bezeichnen. In dieser These stellen wir neue parametrisierte Algorithmen für das Maximum-Weight-Matching-Problem vor, welche exakte Lösungen erzeugen und in Bezug auf die ausgewählten Parameter schneller sind als jeder bekannte exakte nicht-parametrisierte Algorithmus. Zuerst analysieren wir Edmonds' klassischen Maximum-Weight-Matching-Algorithmus unter parametrisierten Gesichtspunkten. Zweitens präsentieren wir einen parametrisierten Algorithmus für das Maximum-Weight-Matching-Problem, welcher eine Laufzeit in O(k (m + n log n)) besitzt, wobei die Zahl k die minimale Größe eines Feedback Vertex Set im gegebenen Graphen ist. Falls k in O(n^(1 - c)), für eine Konstante c > 0, enthalten ist, dann läuft dieser Algorithmus asymptotisch schneller als jeder bekannte exakte nicht-parametrisierte Algorithmus. Wenn der Graph diese Eigenschaft nicht besitzt, dann läuft der parametrisierte Algorithmus in der gleichen asymptotischen Zeit wie der schnellste bekannte nicht-parametrisierte Algorithmus. Der dritte Beitrag dieser These ist ein Kernelization-Algorithmus, welcher einen Problem-Kernel der Größe O(k^2) erzeugt und eine Laufzeit von O(k m) aufweist, wobei die Zahl k nun die minimale Größe eines Vertex Cover im gegebenen Graphen bezeichnet. Dieser Kernelization-Algorithmus kann mit dem oben erwähnten parametrisierten Algorithmus kombiniert werden, um einen Algorithmus zu erhalten, welcher eine Laufzeit von O(k m + k^3 log k) aufweist, wobei hier die Zahl k die minimale Größe eines Vertex Cover im gegebenen Graphen ist. Diese Ergebnisse gehören nach unserem Kenntnisstand zu den ersten strukturellen parametrisierten Algorithmen für das Maximum-Weight-Matching-Problem.

Parameterized algorithm design methods were originally conceived for solving computationally hard problems, that is, problems with super-polynomial running time. But parameterized methods can also be used to construct algorithms for computational problems with polynomial running time. In this thesis we apply parameterized algorithm design to the maximum-weight matching problem, which is a common computational problem in graph theory that asks, given an edge-weighted graph, to compute a set of edges having pairwise disjoint ends such that their sum of weights is maximized. There exists a well known unparameterized exact algorithm running in O(n (m + n log n)) time where n and m are the number of vertices and the number of edges in the input graph, respectively. In this thesis we present new parameterized algorithms for the maximum-weight matching problem which compute exact solutions and are faster with respect to the selected parameters than any known unparameterized exact algorithm. There are three main contributions. First we present an exposition of Edmonds' classical maximum-weight matching algorithm from a parameterized point of view. Second we introduce a parameterized algorithm for the maximum-weight matching problem running in O(k (m + n log n)) time where k is the feedback vertex number. This algorithm is asymptotically faster than any known unparameterized exact algorithm if k is in O(n^(1 - c)) for some constant c > 0, and in the worst case it is asymptotically as fast as any known unparameterized exact algorithm. Third we develop a kernelization algorithm yielding a kernel of size O(k^2) running in O(k m) time where k is the vertex cover number. This kernelization algorithm may be combined with the parameterized algorithm mentioned above to obtain an algorithm running in O(k m + k^3 log k) time where k is the vertex cover number. The results presented in this thesis are, to the best of our knowledge, among the first structural fixed-parameter results for the maximum-weight matching problem.