The minimum maximal k‐partial‐matching problem

In this paper, we introduce a new problem related to bipartite graphs called minimum maximal k‐partial‐matching (MMKPM) which has been modelled by using a relaxation of the concept of matching in a graph. The MMKPM problem can be viewed as a generalization of the classical Hitting Set and Set Cover problems. This property has been used to prove that the MMKPM problem is NP‐Complete. An integer linear programming formulation and a greedy algorithm have been proposed. The problem can be applied to the design process of finite state machines with input multiplexing for simplifying the complexity of multiplexers.