Maximum transversal in partial Latin squares and rainbow matchings (Q869577)

A \(k\)-plex is a partial Latin square of order \(n\) containing \(kn\) entries such that exactly \(k\) entries lie in each row and column and each of \(n\) symbols occurs exactly \(k\) times [\textit{I. M. Wanless}, ''A generalization of transversals for Latin squares,'' Electron. J. Comb. 9, No.1, Research paper R12, 15 p. (2002); printed version J. Comb. 9, No.1 (2002; Zbl 0993.05033)]. A duplex is a \(k\)-plex with \(k=2\). The main theorem of the paper shows that the problem of determining whether there is a transversal of size \(k\) in a duplex is an \(\mathcal{NP}\)-complete problem (Theorem 2). Proof is based on the lemma : The MAX-IS problem is \(\mathcal{NP}\)-complete for any subgraph \(G\) of a graph \(H\) where, in \(H\), all vertices are of degree 3 and in \(G\), the number of vertices of degree one and two are each even numbers and all vertices of \(G\) except those of degree one can be covered by cycles of length even. (The MAX-IS problem is to determine whether there is an independent set of vertices of a given cardinality in a graph) The idea of \textbf{rainbow matching} is introduced. For each edge in a graph, assign a subset (= color set) from the set of colors \(\{1, 2, 3,\dots,k\}\). A rainbow matching is a set of distinct edges whose color sets have a system of distinct representatives (SDR). The size of a rainbow matching is the cardinality of the set of distinct edges. Theorem 4 restates Theorem 2 in terms of rainbow matching. It is also shown that a special case of the rainbow matching problem has a polynomial time solution. Open questions on independent paths, maximum size of a transversal in \(k\)-plexes and perfect rainbow matching are mentioned.