The multicolored graph realization problem

Abstract

We introduce the multicolored graph realization problem (MGR). The input to this problem is a colored graph ( G , phi ), i.e., a graph G together with a coloring phi on its vertices. We associate each colored graph ( G , phi ) with a cluster graph ( G phi ) 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 phi . 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 phi , 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 phi 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 phi 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. (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).