Name
Abstract | ||
|---|---|---|
In a weighted undirected graph, a matching is said to be α-robust if for all p, the total weight of its heaviest p edges is at least α times the maximum weight of a p-matching in the graph. Here a p-matching is a matching with at most p edges. In 2002, Hassin and Rubinstein [4] showed that every graph has a
\frac1Ö</font
>2\frac{1}{\sqrt 2}-robust matching and it can be found by k-th power algorithm in polynomial time.
In this paper, we show that it can be extended to the matroid intersection problem, i.e., there always exists a
\frac1Ö</font
>2\frac{1}{\sqrt 2}-robust matroid intersection, which is polynomially computable. We also study the time complexity of the robust matching problem.
We show that a 1-robust matching can be computed in polynomial time (if exists), and for any fixed number α with
\frac1Ö</font
>2 a</font
> \frac{1}{\sqrt 2} , the problem to determine whether a given weighted graph has an α-robust matching is NP-complete. These together with the positive result for
a</font
> = \frac1Ö</font
>2\alpha =\frac{1}{\sqrt 2} in [4] give us a sharp border for the complexity for the robust matching problem. Moreover, we show that the problem is strongly
NP-complete when α is a part of the input. Finally, we show the limitations of k-th power algorithm for robust matchings, i.e., for any ε> 0, there exists a weighted graph such that no k-th power algorithm outputs a
( \frac1Ö</font
>2 + e</font
>)\left( \frac{1}{\sqrt 2} + \epsilon \right)-approximation for computing the most robust matching.
|
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-15781-3_11 | european symposium on algorithms |
Keywords | Field | DocType |
weighted graph,robust matchings,robust matching problem,robust matching,2-robust matching,weighted undirected graph,1-robust matching,polynomial time,k-th power algorithm,matroid intersection,heaviest p edge,complexity,matching,robustness | Independence system,Matroid,Discrete mathematics,Graph,Combinatorics,Matroid intersection,Matroid partitioning,Independent set,Time complexity,Weighted matroid,Mathematics | Journal |
Volume | Issue | ISSN |
27 | 3 | 0302-9743 |
ISBN | Citations | PageRank |
3-642-15780-7 | 1 | 0.36 |
References | Authors | |
5 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ryo Fujita | 1 | 1 | 0.36 |
| Yusuke Kobayashi | 2 | 133 | 9.47 |
| Kazuhisa Makino | 3 | 1088 | 102.74 |