The minimum maximal k-partial-matching problem

Abstract

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 NPComplete. 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.