\section{Introduction}
\label{sec:introduction}

Many combinatorial optimization problems in graphs can be classified as vertex partitioning problems. The partition classes have to verify inner-properties and/or inter-properties, and there is an objective function to minimize or maximize. Some of these properties are \emph{locally checkable}, that is, the property that each vertex has to satisfy with respect to the partition involves only the vertex and its neighbors. This is the case of stable set, dominating set and $k$-coloring, among others.

In the spirit of generalizing this kind of problems,
in~\cite{bodlaender1987,bodlaender1988} Bodlaender defined the \emph{\LCCfull} ({\LCC}) and \emph{\ECCfull} ({\ECC}) problems, and showed polynomial-time algorithms to solve {\LCC} problems on bounded treewidth and bounded degree graphs, and {\ECC} problems on bounded treewidth graphs.
In~\cite{LCVSVP-thesis} Telle defined the \emph{\LCVPfull} ({\LCVP}) problems and in~\cite{LCVSVP-paper2}, Bui-Xuan, Telle and Vatshelle presented dynamic programming algorithms for {\LCVP} problems that run in polynomial time on many graph classes, including interval graphs, permutation graphs and Dilworth $k$ graphs, and in fixed-parameter single-exponential time parameterized by boolean-width.
In~\cite{Cattaneo-Psigma}, Cattan{\'{e}}o and Perdrix defined a different generalization of {\LCVP} problems that allows us to deal with properties of the subset that are not necessarily locally checkable, as for example being connected, and prove hardness results for {\LCVP} problems and such generalizations.

In this paper, we define a new framework for locally checkable problems, which we call \emph{\rLCproblems{r}}.
In a {\rLCproblem{r}}, every vertex $v$ has a list of colors $L_v$ that it can receive, along with the cost $\textsc{w}_{v,i}$ of receiving each color $i \in L_v$. There is a function $check$ that, for each vertex $v$ and each coloring $c$ of the closed neighborhood of radius $r$ of $v$, determines if the colors assigned to $v$ and the vertices at distance at most $r$ from $v$ are permitted for $v$.
We include edge labels $\ell_e$, whose values may be involved in the checking functions.
For technical reasons, other simple operators are also required, such as one that combines the costs and one that compares them.
This approach generalizes {\LCVP} problems, including other problems such as $\{k\}$-domination (which cannot be expressed as a {\LCVP} problem, at least not in an straightforward way).
We further consider a set of global properties (which might be, for example, that certain sets of the partition induce a connected or an acyclic subgraph). In this way, {\ECC} problems can be modeled within our framework.


A key notion to our paper is the \emph{treewidth} of a graph, which was introduced by Robertson and Seymour~\cite{GraphMinorsIII} (and previously considered under different names by Bertel{\`e} and Brioschi~\cite{B-B-treewidth} and Halin~\cite{Hal-tw}). Graphs of treewidth at most $k$ are called {\em partial $k$-trees}. Some graph classes with bounded treewidth include: forests (treewidth 1); pseudoforests, cacti, outerplanar graphs, and series-parallel graphs (treewidth at most~2); Halin graphs and Apollonian networks (treewidth at most~3)~\cite{GraphMinorsIII,BODLAENDER19981,treewidth-kloks,graph-classes-survey}. In addition, control flow graphs arising in the compilation of structured programs also have bounded treewidth (at most~6)~\cite{THORUP1998159}.

To solve {\rLCproblems{1}} in bounded treewidth graphs, we give an algorithm based on a rather simple computation of a recursive function traversing a special tree decomposition, using dynamic programming as it is usual with this kind of problems, but with an abstraction of the ``extra'' parameters involved in ad-hoc solutions of locally checkable problems. In order to formally describe this abstraction, we introduce the concept of \emph{partial neighborhoods}. A \emph{partial neighborhood system} gives us tools to accumulate information from the neighbors of a vertex. According to the sizes of the sets and the time complexity of the functions involved, we distinguish \emph{polynomial} and \emph{constant} partial neighborhood systems. Then our algorithm is polynomial when some mild conditions are satisfied.
The main result of this paper is the following.

\begin{theoremRep}[\ref{thm:mainTheorem}]
\THMmainTheorem
\end{theoremRep}

Furthermore, by proving that fixed powers of bounded degree and bounded treewidth graphs are also bounded degree and bounded treewidth graphs, we can enlarge the family of problems that can be solved in polynomial time for these graph classes, including distance coloring problems (packing chromatic number~\cite{eccentric-color-trees,broadcast-chromatic,BRESAR20072303,FIALA2010771}, $L(p,1)$-coloring~\cite{L21-1996,L21-1992,CHANG200353,Lp1-2005}), distance independence~\cite{distance-d-indep}, distance domination~\cite{FundamentalsDom}, and distance {\LCVP} problems~\cite{gen-dist-dom-mim-width-2019}, for bounded distances.
These results are unified in the following corollary of Section~\ref{sec:boundedDegree}.

\begin{corollaryRep}[\ref{col:polyDistBoundedTwDeg}]
\COLpolyDistBoundedTwDeg
\end{corollaryRep}

We also prove that NP-complete problems can be reduced to some {\rLCproblems{1}} in complete graphs, even when restricting the sets of colors and edge labels to $\{0,1\}$.
Thus, a generalization of the polynomiality to bounded clique-width graphs is not possible unless P=NP.

We show how to model double Roman domination, minimum chromatic violation and Grundy domination as {\rLCproblems{1}} with polynomial partial neighborhood systems. As a result, we obtain polynomial-time algorithms to solve these problems for bounded treewidth graphs. Until the date and to the best of our knowledge, no such algorithms were previously known.

Courcelle's celebrated theorem (see~\cite{COURCELLE199349}) states that every graph problem definable in Monadic Second-Order (MSO) logic can be solved in linear time for bounded treewidth graphs.
However, its main drawback is that the multiplicative constants in the running time of the algorithm generated with an MSO-formula can be extremely large~\cite{FRICK20043}.
In contrast, the statement of our problem is closer to natural language, and the time complexity of the algorithm for bounded treewidth graphs is fully detailed and involves relatively small constants.

A similar approach for a family of problems of different nature was presented in~\cite{tw-isw}. Namely, the authors define the framework of \emph{algebraic path problems}, enclosing weighted shortest path, dataflow problems, regular expressions, and other problems arising in program analysis in the area of software engineering, and they present an algorithm to solve this framework of problems in concurrent systems such that each of the components is a bounded treewidth graph.

The present paper is organized as follows.
Section~\ref{sec:preliminaries} contains the necessary preliminaries and basic definitions.
The central notion of the paper, {\rLCproblems{r}}, is formally introduced in Section~\ref{sec:problemDescription}.
In Section~\ref{sec:completeGraphs}, we study {\rLCproblems{1}} in complete graphs, under different hypothesis.
In Section~\ref{sec:boundedTreewidth} we give an algorithm to solve {\rLCproblems{1}} parameterized by treewidth.
In Section~\ref{sec:boundedDegree} we analyze the time complexity of {\rLCproblems{r}} in bounded treewidth and bounded degree graphs, and prove that fixed powers of such graphs are also bounded treewidth and bounded degree graphs.
In Section~\ref{sec:globalProp} we extend the algorithm from Section~\ref{sec:boundedTreewidth} with some global properties. In particular, this recovers the results in~\cite{bodlaender1987,bodlaender1988} for {\LCC} problems.
In Section~\ref{sec:examples} we show how to model different problems as {\rLCproblems{1}} with polynomial partial neighborhood systems, obtaining polynomial-time algorithms to solve these problems for bounded treewidth graphs.
We include in Appendix~\ref{sec:problemsDef} the definition of the locally checkable problems mentioned throughout the article.
{"config": "arxiv", "file": "2006.00681/1-Introduction.tex"}