On structural parameterizations of graph motif and chromatic number

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]-hard when parameterized by the distance to split graphs, and para-NP-hard when parameterized by the distance to co-graphs (which are the class of P4-free graphs). On the other hand, it is known to be FPT 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 P<inf>4</inf>-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 FPT 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.