A note on the hardness results for the labeled perfect matching problems in bipartite graphs
RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 315-324.

In this note, we strengthen the inapproximation bound of O(logn) for the labeled perfect matching problem established in J. Monnot, The Labeled perfect matching in bipartite graphs, Information Processing Letters 96 (2005) 81-88, using a self improving operation in some hard instances. It is interesting to note that this self improving operation does not work for all instances. Moreover, based on this approach we deduce that the problem does not admit constant approximation algorithms for connected planar cubic bipartite graphs.

DOI : 10.1051/ro:2008020
Classification : 68Q17, 68R10, 68W25, 90C59
Mots-clés : labeled matching, bipartite graphs, approximation and complexity, inapproximation bounds 
@article{RO_2008__42_3_315_0,
     author = {Monnot, J\'er\^ome},
     title = {A note on the hardness results for the labeled perfect matching problems in bipartite graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {315--324},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {3},
     year = {2008},
     doi = {10.1051/ro:2008020},
     mrnumber = {2444490},
     zbl = {1157.68053},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2008020/}
}
TY  - JOUR
AU  - Monnot, Jérôme
TI  - A note on the hardness results for the labeled perfect matching problems in bipartite graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2008
SP  - 315
EP  - 324
VL  - 42
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2008020/
DO  - 10.1051/ro:2008020
LA  - en
ID  - RO_2008__42_3_315_0
ER  - 
%0 Journal Article
%A Monnot, Jérôme
%T A note on the hardness results for the labeled perfect matching problems in bipartite graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2008
%P 315-324
%V 42
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2008020/
%R 10.1051/ro:2008020
%G en
%F RO_2008__42_3_315_0
Monnot, Jérôme. A note on the hardness results for the labeled perfect matching problems in bipartite graphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 315-324. doi : 10.1051/ro:2008020. http://www.numdam.org/articles/10.1051/ro:2008020/

[1] P. Alimonti and V. Kann, Hardness of approximating problems on cubic graphs, in Proc. CIAC'97, Lect. Notes Comput. Sci. 1203 (1997) 288-298. | MR

[2] S. Arora and M. Sudan, Improved low-degree testing and its applications. Combinatorica 23 (2003) 365-426. | MR | Zbl

[3] K. Cameron, Coloured matchings in bipartite graphs. Discrete Math. 169 (1997) 205-209. | MR | Zbl

[4] M. Costa, D. De Werra, C. Picouleau and B. Ries, Bicolored matchings in some classes of graphs. Graphs Comb. 23 (2007) 47-60. | MR | Zbl

[5] A. Itai, M. Rodeh and S. Tanimoto, Some matching problems in bipartite graphs. J. ACM 25 (1978) 517-525. | MR | Zbl

[6] J. Monnot, On Complexity and Approximability of the Labeled Maximum/Perfect Matching Problems, in Proc. ISAAC'05, Lect. Notes Comput. Sci. 3827 (2005) 934-943. | MR

[7] J. Monnot, The Labeled perfect matching in bipartite graphs. Inf. Proc. Lett. 96 (2005) 81-88. | MR

[8] A. Paz and S. Moran, Non deterministic polynomial optimisation problems and their approximation, Theor. Comput. Sci. 95 (1981) 251-277. | MR | Zbl

[9] M.B. Richey and A.P. Punnen, Minimum Perfect Bipartite Matchings and Spanning Trees under Categorization. Discrete Appl. Math. 39 (1992) 147-153. | MR | Zbl

Cité par Sources :