On structural parameterizations of graph motif and chromatic number

Show simple item record

dc.contributor.author Das, Bireswar
dc.contributor.author Enduri, Murali Krishna
dc.contributor.author Misra, Neeldhara
dc.contributor.author Vinod Reddy, I.
dc.date.accessioned 2017-03-07T05:24:35Z
dc.date.available 2017-03-07T05:24:35Z
dc.date.issued 2017
dc.identifier.citation Das, Bireswar; Enduri, Murali Krishna; Misra, Neeldhara and Vinod Reddy, I., “On structural parameterizations of graph motif and chromatic number", in Algorithms and Discrete Applied Mathematics, DOI: 10.1007/978-3-319-53007-9_11, Springer International Publishing, 2017, pp. 118-129, ISBN: 978-3-319-53006-2. en_US
dc.identifier.isbn 978-3-319-53006-2.
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/2669
dc.identifier.uri http://dx.doi.org/10.1007/978-3-319-53007-9_11
dc.description.abstract Structural parameterizations for hard problems have proven to be a promising venture for discovering scenarios where the problem is tractable. In particular, when a problem is already known to be polynomially solvable for some class of inputs, then it is natural to parameterize by the distance of a general instance to a tractable class. In the context of graph algorithms, parameters like vertex cover, twin cover, treewidth and treedepth modulators, and distances to various special graph classes are increasingly popular choices for hard problems. Our main focus in this work is the Graph Motif problem, which involves finding a connected induced subgraph in a vertex colored graph that respects a given palette. This problem is known to be hard in the traditional setting even for fairly structured classes of graphs. In particular, Graph Motif is known to be W[1]W[1] -hard when parameterized by the distance to split graphs, and para- NPNP -hard when parameterized by the distance to co-graphs (which are the class of -free graphs). On the other hand, it is known to be FPTFPT when parameterized by the distance to a clique or the distance to an independent set (or equivalently, vertex cover). Towards finding the boundary of tractability, we consider parameterizing the problem by the distance to threshold graphs, which are graphs that are both split and -free. Note that this is a natural choice of an intermediate parameter in that it is larger than the parameters for which the problem is hard and smaller than the ones for which the problem is tractable. Our main contribution is an FPTFPT algorithm for the Graph Motif problem when parameterized by the distance to threshold graphs. We also address some related structural parameterizations for Chromatic Number. Here, we show that the problem admits a polynomial kernel when parameterized by the vertex deletion distance to a clique. en_US
dc.description.statementofresponsibility by Bireswar Das, Murali Krishna Enduri, Neeldhara Misra and I. Vinod Reddy
dc.format.extent pp 118-129
dc.language.iso en_US en_US
dc.publisher Springer International Publishing en_US
dc.title On structural parameterizations of graph motif and chromatic number en_US
dc.type Book chapter en_US

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account