Parameterized Algorithms for Disjoint Matchings in Weighted Graphs with Applications

Zhi-Zhong CHEN  Tatsuie TSUKIJI  Hiroki YAMADA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.6   pp.1050-1058
Publication Date: 2016/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.1050
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
fixed-parameter algorithms,  randomized algorithms,  matchings,  color-coding,  universal sets,  

Full Text: PDF(763.9KB)>>
Buy this Article



Summary: 
It is a well-known and useful problem to find a matching in a given graph G whose size is at most a given parameter k and whose weight is maximized (over all matchings of size at most k in G). In this paper, we consider two natural extensions of this problem. One is to find t disjoint matchings in a given graph G whose total size is at most a given parameter k and whose total weight is maximized, where t is a (small) constant integer. Previously, only the special case where t=2 was known to be fixed-parameter tractable. In this paper, we show that the problem is fixed-parameter tractable for any constant t. When t=2, the time complexity of the new algorithm is significantly better than that of the previously known algorithm. The other is to find a set of vertex-disjoint paths each of length 1 or 2 in a given graph whose total length is at most a given parameter k and whose total weight is maximized. As interesting applications, we further use the algorithms to speed up several known approximation algorithms (for related NP-hard problems) whose approximation ratio depends on a fixed parameter 0<ε<1 and whose running time is dominated by the time needed for exactly solving the problems on graphs in which each connected component has at most ε-1 vertices.