Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00538
Graph Motif Problems Parameterized by Dual
Vol. 24, no. 3, pp. 371396, 2020. Regular paper.
Abstract Let $G=(V,E)$ be a vertexcolored 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 ISTCOLORED}~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:=VM$. 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 polynomialsize problem kernel, while $\rm CGM$ can be solved in $\mathcal O(\sqrt{2}^{\ell} + V)$ time and admits a polynomialsize problem kernel. 
Submitted: August 2019.
Reviewed: November 2019.
Revised: January 2020.
Reviewed: June 2020.
Revised: July 2020.
Accepted: July 2020.
Final: July 2020.
Published: July 2020.
Communicated by
Ignaz Rutter

Journal Supporters
