Maximum transversal in partial Latin squares and rainbow matchings

In a partial Latin square P   a set of distinct entries, such that no two of which are in the same row or column is called a transversal. By the size of a transversal TT, we mean the number of its entries. We define a duplex to be a partial Latin square of order nn containing 2n2n entries such that exactly two entries lie in each row and column and each of nn symbols occurs exactly twice. We show that determining the maximum size of a transversal in a given duplex is an NPNP-complete problem. This problem relates to independent sets in certain subfamilies of cubic graphs. Generalizing the concept of transversals in edge coloring of graphs we are led to introduce the concept of rainbow matching. We show that if each color appears at most twice then it is a polynomial time problem to know whether there exists a rainbow matching of size at least ⌊n/2⌋-t⌊n/2⌋-t for each fixed tt, where nn is the order of the graph. As an application we show that for any fixed tt, there is a polynomial time algorithm which decides whether α(G)⩾n-tα(G)⩾n-t, for any graph GG on 2n2n vertices containing a perfect matching. At the end we mention some other applications of rainbow matching.