The Multicolored Graph Realization Problem

dc.authorscopusid 7401603758
dc.authorscopusid 55630908700
dc.authorscopusid 56211714900
dc.authorscopusid 7006385756
dc.contributor.author Díaz, J.
dc.contributor.author Yaşar Diner, Öznur
dc.contributor.author Diner, Ö.Y.
dc.contributor.author Serna, M.
dc.contributor.author Serra, O.
dc.contributor.other Computer Engineering
dc.date.accessioned 2023-10-19T15:05:27Z
dc.date.available 2023-10-19T15:05:27Z
dc.date.issued 2022
dc.department-temp Díaz, J., ALBCOM Research Group, Computer Science Department, Universitat Politècnica de Catalunya (UPC), Barcelona, Spain, Institut de Matemàtiques de la UPC-BarcelonaTech (IMTech), Universitat Politècnica de Catalunya (UPC), Barcelona, Spain; Diner, Ö.Y., Computer Engineering Department, Kadir Has University, Istanbul, Turkey, Mathematics Department, Universitat Politècnica de Catalunya (UPC), Barcelona, Spain; Serna, M., ALBCOM Research Group, Computer Science Department, Universitat Politècnica de Catalunya (UPC), Barcelona, Spain, Institut de Matemàtiques de la UPC-BarcelonaTech (IMTech), Universitat Politècnica de Catalunya (UPC), Barcelona, Spain; Serra, O., Mathematics Department, Universitat Politècnica de Catalunya (UPC), Barcelona, Spain, Institut de Matemàtiques de la UPC-BarcelonaTech (IMTech), Universitat Politècnica de Catalunya (UPC), Barcelona, Spain en_US
dc.description.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) en_US
dc.description.sponsorship 2018-BAP-08, PID2020-113082GB-I00; BIDEB 2219-1059B191802095; Agència de Gestió d'Ajuts Universitaris i de Recerca, AGAUR: 2017-SGR-786; Agencia Estatal de Investigación, AEI: PID2020-112581GB-C21 en_US
dc.description.sponsorship We thank the anonymous referees for their careful reading and helpful suggestions. J. Díaz and M. Serna are partially supported by funds from the Spanish Agencia Estatal de Investigación under grant PID2020-112581GB-C21 (MOTION), and from AGAUR under grant 2017-SGR-786 (ALBCOM). Ö. Y. Diner is partially supported by the Scientific and Technological Research Council Tübitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Agencia Estatal de Investigación under grant PID2020-113082GB-I00 . en_US
dc.identifier.citationcount 0
dc.identifier.doi 10.1016/j.dam.2022.06.031 en_US
dc.identifier.issn 0166-218X
dc.identifier.scopus 2-s2.0-85133340021 en_US
dc.identifier.scopusquality Q2
dc.identifier.uri https://doi.org/10.1016/j.dam.2022.06.031
dc.identifier.uri https://hdl.handle.net/20.500.12469/4902
dc.identifier.wosquality Q3
dc.khas 20231019-Scopus en_US
dc.language.iso en en_US
dc.publisher Elsevier B.V. en_US
dc.relation.ispartof Discrete Applied Mathematics en_US
dc.relation.publicationcategory Makale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı en_US
dc.rights info:eu-repo/semantics/openAccess en_US
dc.scopus.citedbyCount 0
dc.subject Convex bipartite graphs en_US
dc.subject Generalized combinatorial problems en_US
dc.subject Multicolored realization problem en_US
dc.subject Parameterized complexity en_US
dc.subject Complex networks en_US
dc.subject Graph theory en_US
dc.subject Graphic methods en_US
dc.subject Parameterization en_US
dc.subject Bipartite graphs en_US
dc.subject Combinatorial problem en_US
dc.subject Convex bipartite graph en_US
dc.subject Convex-bipartite en_US
dc.subject Generalized combinatorial problem en_US
dc.subject Graph G en_US
dc.subject Multicolored realization problem en_US
dc.subject Parameterized en_US
dc.subject Parameterized complexity en_US
dc.subject Realization problems en_US
dc.subject Color en_US
dc.title The Multicolored Graph Realization Problem en_US
dc.type Article en_US
dspace.entity.type Publication
relation.isAuthorOfPublication 84ac79d3-823a-4abf-9b15-e1383ec8a9f5
relation.isAuthorOfPublication.latestForDiscovery 84ac79d3-823a-4abf-9b15-e1383ec8a9f5
relation.isOrgUnitOfPublication fd8e65fe-c3b3-4435-9682-6cccb638779c
relation.isOrgUnitOfPublication.latestForDiscovery fd8e65fe-c3b3-4435-9682-6cccb638779c

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
4902.pdf
Size:
452.31 KB
Format:
Adobe Portable Document Format
Description:
Tam Metin / Full Text