NP-completeness of cell formation problem with grouping efficacy objective

Abstract

In the current paper we provide a proof of NP-completeness for the Cell Formation Problem (CFP) with the fractional grouping efficacy objective function. First the CFP with a linear objective function is considered. Following the ideas of Pinheiro et al. (2016) we show that it is equivalent to the Bicluster Graph Editing Problem (BGEP), which is known to be NP-complete due to the reduction from the 3-Exact 3-Cover Problem – 3E3CP (Amit, 2004). Then we suggest a polynomial reduction of the CFP with the linear objective to the CFP with the grouping efficacy objective. It proves the NP-completeness of this fractional CFP formulation. Along with the NP-status our paper presents important connections of the CFP with the BGEP and 3E3CP. Such connections could be used for ”transferring” of known theoretical properties, efficient algorithms, polynomial cases, and other features of well-studied graph editing and exact covering problems to the CFP.

Keywords:

• cell formation problem
• bicluster graph editing problem
• grouping efficacy
• np-complete

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

Sections 1, 2, 5 and Theorems 1, 2 in Section 3 were prepared within the framework of the Basic Research Program at the National Research University Higher School of Economics (NRU HSE). Propositions 1, 2 and Theorem 3 in Section 4 were formulated and proved with the support of Russian Science Foundation grant RSF [grant number 14-41-00039].