The multicolored graph realization problem
Abstract
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. © 2022 The Author(s)
Collections
Related items
Showing items related by title, author, creator and subject.
-
Block Elimination Distance
Diner, Ö.Y.; Giannopoulou, A.C.; Stamoulis, G.; Thilikos, D.M. (Springer Science and Business Media Deutschland GmbH, 2021)We introduce the parameter of block elimination distance as a measure of how close a graph is to some particular graph class. Formally, given a graph class G, the class B(G) contains all graphs whose blocks belong to G and ... -
Contraction and deletion blockers for perfect graphs and H-free graphs
Diner, Öznur Yaşar; Paulusma, Daniel; Picouleau, Christophe; Ries, Bernard (Elsevier Science, 2018)We study the following problem: for given integers d k and graph G can we reduce some fixed graph parameter pi of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic ... -
Orthogonal projection and liftings of Hamilton-decomposable Cayley graphs on abelian groups
Alspach, Brian; Çalışkan, Cafer; Kreher, Donald L. (Elsevier Science Bv, 2013)In this article we introduce the concept of (p alpha)-switching trees and use it to provide sufficient conditions on the abelian groups G and H for when CAY (G x H