TY - JOUR
T1 - On Tree-Constrained Matchings and Generalizations
AU - Canzar, Stefan
AU - Elbassioni, Khaled
AU - Klau, Gunnar W.
AU - Mestre, Julián
N1 - Publisher Copyright:
© 2013, Springer Science+Business Media New York.
PY - 2013/1
Y1 - 2013/1
N2 - We consider the following Tree-Constrained Bipartite Matching problem: Given a bipartite graph G=(V1,V2,E) with edge weights (Formula presented.), a rooted tree T1 on the set V1 and a rooted tree T2 on the set V1, find a maximum weight matching (Formula presented.)in G, 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 (Formula presented.)-hard and thus, unless (Formula presented.), 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 LP-relaxation, which we also show to have an integrality gap of 2−o(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ρ-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 ρ. We finally give an almost matching integrality gap example, and an inapproximability result showing that the dependence on ρ is most likely unavoidable.
AB - We consider the following Tree-Constrained Bipartite Matching problem: Given a bipartite graph G=(V1,V2,E) with edge weights (Formula presented.), a rooted tree T1 on the set V1 and a rooted tree T2 on the set V1, find a maximum weight matching (Formula presented.)in G, 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 (Formula presented.)-hard and thus, unless (Formula presented.), 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 LP-relaxation, which we also show to have an integrality gap of 2−o(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ρ-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 ρ. We finally give an almost matching integrality gap example, and an inapproximability result showing that the dependence on ρ is most likely unavoidable.
KW - Approximation algorithms
KW - Computational biology
KW - Inapproximability
KW - k-partite matching
KW - Local ratio technique
KW - Rooted trees
UR - http://www.scopus.com/inward/record.url?scp=84922000598&partnerID=8YFLogxK
U2 - 10.1007/s00453-013-9785-0
DO - 10.1007/s00453-013-9785-0
M3 - Article
AN - SCOPUS:84922000598
SN - 0178-4617
VL - 71
SP - 98
EP - 119
JO - Algorithmica (New York)
JF - Algorithmica (New York)
IS - 1
ER -