Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00525
On the Approximability of the Minimum Weight $t$partite Clique Problem
Vol. 24, no. 3, pp. 171190, 2020. Regular paper.
Abstract The ${\rm M{\small INIMUM}~W\small{EIGHT}}$ $t$${\rm {\small PARTITE}~C{\small LIQUE}~P{\small ROBLEM}~MW} t {\rm CP}$ is the problem of finding a $t$clique with minimum weight in a complete edgeweighted $t$partite graph. The motivation for studying this problem is its potential in modelling the problem of identifying sets of commonly existing putative coregulated, coexpressed genes, called gene clusters. In this paper, we show that ${\rm MW} t {\rm CP}$ is NPhard, APXhard in the general case. We also present a 2approximation algorithm that runs in $O(n^2)$ for the metric case and has 1+$
\frac{1}{t}$approximation performance guarantee for the ultrametric subclass of instances. We further show how relaxing or tightening the application of the metricity property affects the approximation ratio. Finally insights on the application ${\rm MW} t {\rm CP}$ to gene cluster discovery are presented.

Submitted: August 2018.
Reviewed: January 2019.
Revised: March 2019.
Reviewed: July 2019.
Revised: September 2019.
Accepted: March 2020.
Final: March 2020.
Published: April 2020.
Communicated by
Fabio Vandin

Journal Supporters
