Graph Motif Problems Parameterized by Dual

Authors

  • Guillaume Fertin
  • Christian Komusiewicz

DOI:

https://doi.org/10.7155/jgaa.00538

Keywords:

Subgraph problem , Vertex-colored graphs , NP-hard problem , Fixed-parameter tractability

Abstract

Let $G=(V,E)$ be a vertex-colored graph, where $C$ is the set of colors used to color $V$. The ${\rm G{\small RAPH}~M{\small OTIF}}$ (or $\rm GM$) problem takes as input $G$, a multiset $M$ of colors built from $C$, and asks whether there is a subset $S\subseteq V$ such that (i) $G[S]$ is connected and (ii) the multiset of colors obtained from $S$ equals $M$. The ${\rm C{\small OLORFUL}~G{\small RAPH}~M{\small OTIF}}$ (or ${\rm CGM}$) problem is the special case of $\rm GM$ in which $M$ is a set, and the ${\rm L{\small IST-COLORED}~G{\small RAPH}~M{\small OTIF}}$ (or $\rm LGM$) problem is the extension of $\rm GM$ in which each vertex $v$ of $V$ may choose its color from a list $\mathcal L(v)\subseteq C$ of colors.
We study the three problems $\rm GM$, $\rm CGM$, and $\rm LGM$, parameterized by the dual parameter $\ell:=|V|-|M|$. For general graphs, we show that, assuming the strong exponential time hypothesis, $\rm CGM$ has no $(2-\epsilon)^\ell\cdot |V|^{\mathcal O(1)}$-time algorithm, which implies that a previous algorithm, running in $\mathcal O(2^\ell\cdot |E|)$ time is optimal [Betzler et al., IEEE/ACM TCBB 2011]. We also prove that $\rm LGM$ is W[1]-hard with respect to $\ell$ even if we restrict ourselves to lists of at most two colors. Finally, we show that if the input graph is a tree, then $\rm GM$ can be solved in $\mathcal O(3^\ell\cdot |V|)$ time but admits no polynomial-size problem kernel, while $\rm CGM$ can be solved in $\mathcal O(\sqrt{2}^{\ell} + |V|)$ time and admits a polynomial-size problem kernel.

Downloads

Download data is not yet available.

Downloads

Published

2020-03-01

How to Cite

Fertin, G., & Komusiewicz, C. (2020). Graph Motif Problems Parameterized by Dual. Journal of Graph Algorithms and Applications, 24(3), 371–396. https://doi.org/10.7155/jgaa.00538

Issue

Section

Articles

Categories