Parameterized Algorithms for Disjoint Matchings in Weighted Graphs with Applications

Zhi-Zhong CHEN; Tatsuie TSUKIJI; Hiroki YAMADA

doi:10.1587/transfun.E99.A.1050

Parameterized Algorithms for Disjoint Matchings in Weighted Graphs with Applications

Zhi-Zhong CHEN, Tatsuie TSUKIJI, Hiroki YAMADA

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.6 pp.1050-1058

Publication Date: 2016/06/01

Publicized

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

Authors

Zhi-Zhong CHEN
  Tokyo Denki University
Tatsuie TSUKIJI
  Tokyo Denki University
Hiroki YAMADA
  Tokyo Denki University

Keyword

fixed-parameter algorithms, randomized algorithms, matchings, color-coding, universal sets

Cite this

Copy

Zhi-Zhong CHEN, Tatsuie TSUKIJI, Hiroki YAMADA, "Parameterized Algorithms for Disjoint Matchings in Weighted Graphs with Applications" in IEICE TRANSACTIONS on Fundamentals, vol. E99-A, no. 6, pp. 1050-1058, June 2016, doi: 10.1587/transfun.E99.A.1050.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.1050/_p

Copy

@ARTICLE{e99-a_6_1050,
author={Zhi-Zhong CHEN, Tatsuie TSUKIJI, Hiroki YAMADA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Parameterized Algorithms for Disjoint Matchings in Weighted Graphs with Applications},
year={2016},
volume={E99-A},
number={6},
pages={1050-1058},
abstract={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.},
keywords={},
doi={10.1587/transfun.E99.A.1050},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - Parameterized Algorithms for Disjoint Matchings in Weighted Graphs with Applications
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1050
EP - 1058
AU - Zhi-Zhong CHEN
AU - Tatsuie TSUKIJI
AU - Hiroki YAMADA
PY - 2016
DO - 10.1587/transfun.E99.A.1050
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2016
AB - 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.
ER -