20110101
On TreeConstrained Matchings and Generalizations
Publication
Publication
We consider the following \textsc{TreeConstrained Bipartite Matching} problem: Given two rooted trees $T_1=(V_1,E_1)$, $T_2=(V_2,E_2)$ and a weight function $w: V_1\times V_2 \mapsto \mathbb{R}_+$, find a maximum weight matching $\mathcal{M}$ between nodes of the two trees, such that none of the matched nodes is an ancestor of another matched node in either of the trees. This generalization of the classical bipartite matching problem appears, for example, in the computational analysis of live cell video data. We show that the problem is $\mathcal{APX}$hard and thus, unless $\mathcal{P} = \mathcal{NP}$, disprove a previous claim that it is solvable in polynomial time. Furthermore, we give a $2$approximation algorithm based on a combination of the local ratio technique and a careful use of the structure of basic feasible solutions of a natural LPrelaxation, which we also show to have an integrality gap of $2o(1)$.
In the second part of the paper, we consider a natural generalization of the problem, where trees are replaced by partially ordered sets (posets). We show that the local ratio technique gives a $2k\rho$approximation for the $k$dimensional matching generalization of the problem, in which the maximum number of incomparable elements below (or above) any given element in each poset is bounded by $\rho$. We finally give an almost matching integrality gap example, and an inapproximability result showing that the dependence on $\rho$ is most likely unavoidable.
Additional Metadata  

Keywords  $k$partite matching, rooted trees, approximation algorithms, local ratio technique, inapproximability, computational biology 
THEME  Life Sciences (theme 5), Energy (theme 4) 
Publisher  CWI 
Series  CWI. Department of Modelling, Analysis and Computing [MAC] 
Note  This technical report is the full version of a conference paper (Proc. 38th International Colloquium on Automata, Languages and Programming (ICALP 2011)) with the same title and authors. 
Citation 
Canzar, S, Elbassioni, K, Klau, G.W, & Mestre, J. (2011). On TreeConstrained Matchings and Generalizations. CWI. Department of Modelling, Analysis and Computing [MAC]. CWI.

See Also 

inProceedings

inProceedings

inProceedings
