Maximum weight edge-constrained matchings

Practical questions arising from (for instance) biological applications can often be expressed as classical optimization problems with specific, new features. We are interested here in the version of the maximum weight matching problem (on a graph GG) obtained by (1) defining a set FF of pairs of incompatible edges of GG and (2) asking that the matching contains at most one edge in each given pair. Such a matching is called an odd matching  . The graph T(F)=(VF,F)T(F)=(VF,F), where VFVF is the set of edges of GG occurring in at least one pair of FF, is called the trace-graph   of GG and FF.We motivate the introduction of the maximum weight odd-matching (abbreviated as Odd-MWM) problem and study its complexity with respect to two parameters: the type of graph GG and the graph class TT to which T(F)T(F) belongs.Our contribution includes:
• A proof that Odd-MWM is NP-complete for 3-degree bipartite graphs when T(F)T(F) is a matching (i.e. when TT is the class of 1-regular graphs), even if the weight function is constant.
• A proof that Odd-MWM is NP-complete (for 3-degree bipartite graphs as well as for any larger class) if and only if TT is a class of graphs with unbounded induced matching. Otherwise, Odd-MWM is polynomial.
• A (Δ(T(F))+1)(Δ(T(F))+1)-approximate algorithm for Odd-MWM on general graphs. This algorithm becomes a χ(T(F))χ(T(F))-approximate algorithm when the graph class TT admits a polynomial algorithm for minimum vertex coloring.