Parameterized and approximation algorithms for finding two disjoint matchings

We first present a randomized fixed-parameter algorithm for the NP-hard problem of deciding if there are two matchings M1M1 and M2M2 in a given graph G   such that |M1|+|M2||M1|+|M2| is a given number k  . The algorithm runs in O(2kk(m+n))O(2kk(m+n)) expected time and can be derandomized to run in O(22k+12log2⁡(2k)kn(m+n))O(22k+12log2⁡(2k)kn(m+n)) time, where n (respectively, m) is the number of vertices (respectively, edges) in G. We then extend the algorithm to the weighted version of the problem. We further present a combinatorial approximation algorithm for the NP-hard problem of finding two disjoint matchings in a given edge-weighted graph G   so that their total weight is maximized. The algorithm achieves an approximation ratio close to 0.76 and runs in O(m+n3α(n))O(m+n3α(n)) time, where α is the inverse Ackermann function.