  We introduce the Multicolored Graph Realization problem (MGRP). The input to
the problem is a colored graph $(G,\varphi)$, i.e., a graph together with a
coloring on its vertices. We can associate to each colored graph a cluster
graph ($G_\varphi)$ in which, after collapsing to a node all vertices with the
same color, 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 problem
is to decide whether there is a multicolored set $S$ such that, after
identifying each vertex in $S$ with its color class, $G[S]$ coincides with
$G_\varphi$.
  The MGR problem is related to the class of generalized network problems, most
of which are NP-hard. For example the generalized MST problem. MGRP is a
generalization of the Multicolored Clique Problem, which is known to be
W[1]-hard when parameterized by the number of colors. Thus MGRP remains
W[1]-hard, when parameterized by the size of the cluster graph and when
parameterized by any graph parameter on $G_\varphi$, among those for treewidth.
We look to instances of the problem in which both the number of color classes
and the treewidth of $G_\varphi$ are unbounded. We show that MGRP is
NP-complete when $G_\varphi$ is either chordal, biconvex bipartite, complete
bipartite or a 2-dimensional grid. Our hardness results follows from suitable
reductions from the 1-in-3 monotone SAT problem. 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 also graphs with bounded
degree. We complement those results by showing combined parameterizations under
which the MGR problem became tractable.
