\subsection{Grundy domination number}
\label{sec:grundy}

This problem was introduced in \cite{GrundyDom} and proved to be NP-complete even for chordal graphs.


A sequence $S = \seq{v_1, \ldots, v_k}$ of distinct vertices of a graph $G$ is a \emph{dominating sequence} if $\{v_1, \ldots, v_k\}$ is a dominating set of $G$, and $S$ is called a \emph{legal (dominating) sequence} if (in addition) $N[v_i] - \bigcup_{j=1}^{i-1} N[v_j] \neq \emptyset$ for each $i$.
We say that $v_i$ \emph{footprints} the vertices in $N[v_i] - \bigcup_{j=1}^{i-1} N[v_j]$, and that $v_i$ is the \emph{footprinter} of every $u \in N[v_i] - \bigcup_{j=1}^{i-1} N[v_j]$ (notice that every vertex in $V(G)$ has a unique footprinter).
We are interested in the maximum length of a legal dominating sequence in $G$.


Given a legal sequence $S$, every vertex $v \in V(G)$ can be associated with a pair $(p_v, f_v)$, where $p_v$ is the position of $v$ in $S$ (or $\notInSeq$ if $v$ is not in $S$) and $f_v$ is the position in $S$ of the footprinter of $v$.

Directly from the definition of legal sequences we can deduce the following statement. A set $\setst{(p_v, f_v)}{v \in V(G)}$ determines a legal sequence if and only if the following conditions are satisfied:
\begin{enumerate}
\item for all $v \in V(G)$, there exists a unique $u \in N_G[v]$ such that $f_v = p_u$, and 
 $f_v \leq p_w$ for all $w \in N_G[v]$ (i.e., $v$ is properly footprinted),
\item for all $v \in V(G)$, if $p_v \neq \notInSeq$ then there exists $u \in N_G[v]$ such that $f_u = p_v$ (i.e., if $v$ appears in the sequence then it footprints at least one vertex), and
\item $p_v \neq p_u$ for all $u,v \in V(G)$ such that $u \neq v$ and $p_u \neq \notInSeq$ (i.e., two vertices that appear in the sequence cannot have the same position in it).
\end{enumerate}


Notice that conditions 1 and 2 are locally checkable, but the last one is not. However, we claim that the Grundy domination problem can be reduced to the following {\rLCproblem{1}}.
Let $n = |V(G)|$ and $\notInSeq = n+1$.
\begin{itemize}
\item $L_{v} = (\{1, \ldots, n\} \cup \{\notInSeq\}) \times \{1, \ldots, n\}$;

\item $(\WeightSet, \wlesseq, \weightsSum) = (\mathbb{R} \cup \{-\infty\}, \geq, +)$;

\item for all $f \in \{1, \ldots, n\}$, $\textsc{w}_{v, (\notInSeq, f)} = 0$ and $\textsc{w}_{v, (p, f)} = 1$ for all $p \neq \notInSeq$;

\item $\begin{array}[t]{rrl}
check(v, c)	& =		& (\existsUniqueFormula{u \in N_G[v]}{c(v)_2 = c(u)_1})\\
			& \land	& (\forallFormula{u \in N_G[v]}{c(v)_2 \leq c(u)_1})\\
			& \land	& (c(v)_1 \neq \notInSeq \Rightarrow \existsFormula{u \in N_G[v]}{c(v)_1 = c(u)_2})\\
			& \land	& (c(v)_1 \neq \notInSeq \Rightarrow \forallFormula{u \in N_G(v)}{c(v)_1 \neq c(u)_1}).
\end{array}$
\end{itemize}


Let $G$ be a graph. Let $c$ be a proper coloring of $G$ in the previous {\rLCproblem{1}}, and let $(p_v, f_v) = c(v)$ for all $v \in V(G)$.
Conditions 1 and 2 are trivially satisfied.
Suppose that the last condition is not satisfied. Then there are two different vertices $u, v$ such that $p_u = p_v \neq \notInSeq$.
By definition of $check$, we know that
\begin{itemize}
\item $u \notin N_G[v]$,
\item if there exists a vertex $w$ such that $f_w > p_v = p_u$ then $v \notin N_G[w]$ and $u \notin N_G[w]$ (thus, $w \notin N_G[v]$ and $w \notin N_G[u]$), and
\item if there exists a vertex $w \in N_G[u]$ such that $f_w = p_v = p_u$ then $w \notin N_G[v]$.
\end{itemize}
Therefore, $N_G[u] \cap N_G[v] = F$ such that $f_w < p_u = p_v$ for all $w \in F$. Now we can assign colors $(p_w', f_w')$ for every $w \in V(G)$, such that
$$p_w' = \begin{cases}
p_w		& \text{if $p_w \leq p_u$ and $w \neq v$}\\
p_w + 1	& \text{otherwise}
\end{cases}
$$
and
$$f_w' = \begin{cases}
f_w		& \text{if $f_w < p_u$, or $f_w = p_u$ and $w \notin N_G[v]$}\\
f_w + 1	& \text{otherwise.}
\end{cases}
$$
That is, we move one position forward all the vertices that appear after $u$ in $S$ and increase the necessary $f_w$. It is easy to see that this new assignment preserves the ``legality'' of $u$ (i.e., if $N_G[u] - \setst{z}{z \in N_G[w] \land p_w < p_u} \neq \emptyset$ then $N_G[u] - \setst{z}{z \in N_G[w] \land p_w' < p_v'} \neq \emptyset$) and also of all the other vertices.


In order to give a polynomial-time algorithm for the Grundy domination problem in bounded treewidth graphs, we define a constant partial neighborhood system as follows:
\begin{itemize}
\item $\NeighborhoodSet{v}{(p, f)} = \{0,1,2\} \times \BoolSet \times \BoolSet \times \BoolSet$;

\item $n \neighborhoodSum{v}{(p, f)} n' = (\min(n_1 + n_1', 2), n_2 \land n_2', n_3 \lor n_3', n_4 \land n_4')$;

\item $\toNeighborhood{v}{(p_v, f_v)}(u, (p_u, f_u)) = n$ where:
	\begin{itemize}
	\item $n_1 = \begin{cases}
	1	& \text{if $f_v = p_u$}\\
	0	& \text{otherwise,}
	\end{cases}$
	\item $n_2 = (f_v \leq p_u)$,
	\item $n_3 = (p_v = f_u)$,
	\item $n_4 = (p_v \neq p_u)$;
	\end{itemize}

\item $\begin{array}[t]{rrl}
check_{v,(p, f)}(n)
	& =		& (n_1 < 2 \land (n_1 = 1 \Rightarrow f \neq p) \land (n_1 = 0 \Rightarrow f = p))\\
	& \land	& (n_2 \land f \leq p)\\
	& \land	& (p \neq \notInSeq \Rightarrow (n_3 \lor p = f))\\
	& \land	& (p \neq \notInSeq \Rightarrow n_4).
\end{array}$
\end{itemize}

We can also model the Grundy total domination problem (defined in \cite{GrundyTotalDom}) in a very similar way, by simply removing the cases where a vertex can footprint itself.

For both problems, since $\mathcal{C}$ is $O(|V(G)|^2)$, and we defined a constant partial neighborhood system, the time complexity of the algorithm is polynomial in $|V(G)|$ for a graph $G$ in a family of bounded treewidth graphs.
{"config": "arxiv", "file": "2006.00681/8-Grundy.tex"}