Chromatic kernel and its applications

In this paper, we study the following Chromatic kernel (CK) problem: given an (Formula presented.) -partite graph (called a chromatic correlation graph) (Formula presented.) with (Formula presented.) and each partite set (Formula presented.) containing a constant number (Formula presented.) of vertices, compute a subgraph (Formula presented.) of (Formula presented.) with exactly one vertex from each partite set and the maximum number of edges or the maximum total edge weight, if (Formula presented.) is edge-weighted (among all such subgraphs). CK is a new problem motivated by several applications and no existing algorithm directly solves it. In this paper, we first show that CK is NP-hard even if (Formula presented.) , and cannot be approximated within a factor of (Formula presented.) unless P = NP. Then, we present a random-sampling-based PTAS for dense CK. As its application, we show that CK can be used to determine the pattern of chromosome associations in the nucleus for a population of cells. We test our approach by using random and real biological data; experimental results suggest that our approach yields near optimal solutions, and significantly outperforms existing approaches.