The multicolored graph realization problem.

We introduce the multicolored graph realization problem (MGR). The input to this problem is a colored graph (G , φ) , i.e., a graph G together with a coloring φ on its vertices. We associate each colored graph (G , φ) with a cluster graph (G φ) in which, after collapsing all vertices with the same color to a node, we remove multiple edges and self-loops. A set of vertices S is multicolored when S has exactly one vertex from each color class. The MGR problem is to decide whether there is a multicolored set S so that, after identifying each vertex in S with its color class, G [ S ] coincides with G φ. The MGR problem is related to the well-known class of generalized network problems, most of which are NP-hard, like the generalized Minimum Spanning Tree problem. The MGR is a generalization of the multicolored clique problem, which is known to be W [ 1 ] -hard when parameterized by the number of colors. Thus, MGR remains W [ 1 ] -hard, when parameterized by the size of the cluster graph. These results imply that the MGR problem is W [ 1 ] -hard when parameterized by any graph parameter on G φ , among which lies treewidth. Consequently, we look at the instances of the problem in which both the number of color classes and the treewidth of G φ are unbounded. We consider three natural such graph classes: chordal graphs, convex bipartite graphs and 2-dimensional grid graphs. We show that MGR is NP-complete when G φ is either chordal, biconvex bipartite, complete bipartite or a 2-dimensional grid. Our reductions show that the problem remains hard even when the maximum number of vertices in a color class is 3. In the case of the grid, the hardness holds even for graphs with bounded degree. We provide a complexity dichotomy with respect to cluster size. [ABSTRACT FROM AUTHOR]