Neighborhood-Aware Graph Labeling Problem Mohammad Shahverdikondori, Sepehr Elahi, Patrick Thiran, Negar Kiyavash Abstract Motivated by optimization oracles in bandits with network interference, we study the Neighborhood-Aware Graph Labeling ( NAGL ) problem. Given a graph G = ( V , E ) G=(V,E) , a label set of size L L , and local reward functions f v f_{v} accessed via evaluation oracles, the objective is to assign labels to maximize ∑ v ∈ V f v ​ ( x N ⁡ [ v ] ) \sum_{v\in V}f_{v}(x_{N[v]}) , where each term depends on the closed neighborhood of v v . Two vertices co-occur in some neighborhood term exactly when their distance in G G is at most 2 2 , so the dependency graph is the squared graph G 2 G^{2} and tw ⁡ ( G 2 ) \tw(G^{2}) governs exact algorithms and matching fine-grained lower bounds. Accordingly, we show that this dependence is inherent: NAGL is NP-hard even on star graphs with binary labels and, assuming SETH, admits no ( L − ε ) tw ⁡ ( G 2 ) ⋅ n O ⁡ ( 1 ) (L-\varepsilon)^{\tw(G^{2})}\cdot n^{O(1)} -time algorithm for any ε > 0 \varepsilon>0 . We match this with an exact dynamic program on a tree decomposition of G 2 G^{2} running in O ⁡ ( n ⋅ tw ⁡ ( G 2 ) ⋅ L tw ⁡ ( G 2 ) + 1 ) O\!\left(n\cdot\tw(G^{2})\cdot L^{\tw(G^{2})+1}\right) time. For approximation, unless 𝖯 = 𝖭𝖯 \mathsf{P}=\mathsf{NP} , for every ε > 0 \varepsilon>0 there is no polynomial-time n 1 − ε n^{1-\varepsilon} -approximation on general graphs even under the promise OPT > 0 \mathrm{OPT}>0 ; without the promise OPT > 0 \mathrm{OPT}>0 , no finite multiplicative approximation ratio is possible. In the nonnegative-reward regime, we give polynomial-time approximation algorithms for NAGL in two settings: (i) given a proper q q -coloring of G 2 G^{2} , we obtain a 1 / q 1/q -approximation; and (ii) on planar graphs of bounded maximum degree, we develop a Baker-type polynomial-time approximation scheme (PTAS), which becomes an efficient PTAS (EPTAS) when L L is constant. EPFL, Switzerlandmohammad.shahverdikondori@epfl.ch EPFL, Switzerlandsepehr.elahi@epfl.ch EPFL, Switzerlandpatrick.thiran@epfl.ch EPFL, Switzerlandnegar.kiyavash@epfl.ch ccs Theory of computation Graph algorithms analysis ccs Theory of computation Parameterized complexity and exact algorithms ccs Theory of computation Approximation algorithms analysis keywords graph labeling, graph squares, treewidth, fixed-parameter algorithms, SETH-tight lower bounds, hardness of approximation, planar graphs † † runningtitle: Neighborhood-Aware Graph Labeling Problem † † runningauthor: M. Shahverdikondori, S. Elahi, P. Thiran, N. Kiyavash † † event-title: 53rd EATCS International Colloquium on Automata, Languages, and Programming (ICALP) † † event-shorttitle: ICALP 2026 † † event-acronym: ICALP † † year: 2026 † † event-date: July 7–10, 2026 † † event-location: London, United Kingdom 1 Introduction A wide range of combinatorial optimization problems on graphs are characterized by the presence of local interactions coupled with a global objective . In such problems, decisions made at individual vertices or edges affect only a small neighborhood, yet these local effects overlap and interact, making the global optimization problem highly nontrivial. This phenomenon arises in numerous settings, including graph labeling problems, graphical models and constraint networks [ 28 , 40 , 15 ] , and graph-based energy minimization and labeling formulations [ 9 , 29 ] , as well as networked decision-making on graphs [ 1 , 25 ] . Understanding how local dependencies influence global computational complexity is a central theme in algorithmic graph theory. In this work, we study the Neighborhood-Aware Graph Labeling ( NAGL ) problem. The input is an undirected graph G=(V,E) and a finite label set \mathcal{L} with L\coloneqq|\mathcal{L}| . Each vertex v is assigned a label x_{v}\in\mathcal{L} and receives a numerical reward that is a function of the labels in its closed neighborhood N[v] (i.e., the neighborhood including the vertex itself). The goal is to maximize the total reward F(x)=\sum_{v\in V}f_{v}(x_{N[v]}) . The computational difficulty of NAGL stems from the objective being a sum of overlapping neighborhood terms: modifying a single label x_{u} can change every local reward f_{v}(x_{N[v]}) for which u\in N[v] . This overlap is captured by the squared graph G^{2} : two vertices can appear together in some local term f_{w} exactly when their distance in G is at most 2 . In particular, each closed neighborhood N[v] induces a clique in G^{2} , making \tw(G^{2}) the appropriate treewidth parameter for exact dynamic programming. The primary motivation for studying NAGL is to address the computational tractability of algorithms arising in recent work on multi-armed bandits with network interference [ 26 , 1 , 25 ] . In this class of problems, each action corresponds to assigning labels (e.g., treatments or interventions) to all nodes of an interference graph, and the reward of each node depends not only on its own assigned label but also on the labels assigned to its neighbors. Such models naturally arise, for example, in vaccination or information diffusion scenarios, where the treatment of an individual may affect the health outcomes or behavior of nearby individuals in a social or contact network [ 17 ] . Learning algorithms for bandits with interference typically maintain estimates or upper confidence bounds on the local reward functions, and then assume access to an oracle that computes a globally optimal labeling given these local estimates. See, e.g., [ 25 , 1 ] . This oracle problem is precisely an instance of NAGL . While the statistical aspects of learning under interference have received attention, the computational complexity of this underlying optimization problem has not been previously examined. Characterizing the hardness of this oracle and developing efficient algorithms are therefore crucial for the practical applicability of these learning methods. Our results provide a tight characterization of the computational feasibility of this oracle. More broadly, NAGL can be viewed as a graph labeling problem with higher-order (neighborhood) rewards, generalizing classical pairwise formulations used, e.g., in energy minimization via graph cuts [ 9 , 29 ] and inference in graphical models [ 28 , 40 ] . Equivalently, NAGL can be viewed as a weighted constrained satisfaction problem (WCSP) with primal graph G^{2} [ 15 , 21 ] , which provides intuition for why \tw(G^{2}) governs the complexity of exact algorithms, via treewidth-based inference methods [ 15 , 32 ] . Our model, algorithms, and proofs are done in NAGL ’s graph-native language motivated by network interference optimization, giving self-contained arguments specialized to squared-neighborhood structure rather than using WCSP machinery. This graph-first perspective is also what enables our approximation regimes both in terms of a coloring of the squared graph and a Baker-type PTAS/EPTAS for planar graphs, which exploit structure beyond \tw(G^{2}) [ 4 ] . We further discuss the related work in \Cref app:related_work, deferred proofs appear in \Cref apd:proofs, and experimental results are reported in \Cref apd:experiments. Contributions. Our main contributions are as follows: • We prove that NAGL is NP-hard under the standard evaluation-oracle model for local reward functions. We further show that, assuming SETH, there exists no algorithm running in time (L-\varepsilon)^{\tw(G^{2})}\cdot n^{O(1)} for any \varepsilon>0 . We also establish strong inapproximability for the general version of NAGL (allowing negative rewards). In particular, unless \mathsf{P}=\mathsf{NP} , NAGL admits no polynomial-time algorithm with any bounded multiplicative approximation guarantee, even on star graphs. Moreover, unless \mathsf{P}=\mathsf{NP} , for every \varepsilon>0 there exists no polynomial-time n^{1-\varepsilon} -approximation algorithm for general graphs, even on instances with strictly positive optimum. • We introduce Clique-Focused Dynamic Programming (CFDP), an exact dynamic programming algorithm over a tree decomposition of G^{2} with running time O\bigl(n\cdot\tw(G^{2})\cdot L^{\tw(G^{2})+1}\bigr) . For constant L this yields a single-exponential fixed-parameter tractable (FPT) algorithm parameterized by \tw(G^{2}) . Our SETH-based lower bound proves that the base L in the running time is optimal up to polynomial factors. • In the nonnegative-reward regime, given a proper q -coloring of G^{2} we obtain a 1/q -approximation in time O\!\left(L^{\Delta(G)+1}\right)\cdot n^{O(1)} . Without a coloring as input, a greedy coloring yields a 1/(\Delta(G^{2})+1) -approximation, and hence a 1/(\Delta(G)^{2}+1) -approximation using \Delta(G^{2})\leq\Delta(G)^{2} . • In the nonnegative-reward regime, if G is planar with \Delta(G) a constant, we obtain a Baker-type PTAS for NAGL . For every \varepsilon\in(0,1) , we compute a (1-\varepsilon) -approximate labeling in time L^{O(\Delta(G)^{2}/\varepsilon)}\cdot n^{O(1)} . For constant L , this yields an EPTAS. 2 Preliminaries and problem setup We define NAGL and recall the graph-theoretic notions used throughout the paper. We model interactions by an undirected graph G=(V,E) with n\coloneqq|V| . For m\in\mathbb{N} , we write [m]\coloneqq\{1,2,\ldots,m\} . For each v\in V , let N[v]\coloneqq\{v\}\cup\{u\in V:\{u,v\}\in E\} denote its closed neighborhood. Let \mathcal{L} be a finite set of labels and write L\coloneqq|\mathcal{L}| . We view L as an explicit parameter and keep track of its dependence in our running-time bounds. Function x:V\to\mathcal{L} , called a labeling, specifies the labels assigned to all vertices in G . 1 1 1 Generalization of the results to finite label sets with vertex-dependent cardinalities is straightforward. For any subset S\subseteq V , we denote by x_{S} the restriction of x to the vertices in S . For each vertex v\in V , the function f_{v}:\mathcal{L}^{|N[v]|}\to\mathbb{R} , called the reward function of vertex v , specifies the reward of this vertex as a function of the labels assigned to its closed neighborhood. We assume an evaluation-oracle model in which each f_{v} is given by a succinct representation supporting polynomial-time evaluation: given v\in V and an assignment a:N[v]\to\mathcal{L} , we can compute f_{v}(a) in time polynomial in the instance encoding size, and oracle values have polynomial-bit encoding, so the decision version of NAGL lies in NP. While we allow rewards to be negative in general, our multiplicative approximation statements will be stated only under explicit nonnegativity assumptions (see \Cref sec:color-approx and \Cref sec:planar-ptas). The objective of the NAGL problem is to find a labeling x^{\star}\in\mathcal{L}^{V} that maximizes the total reward, that is, x^{\star}\in\argmax_{x\in\mathcal{L}^{V}}F(x),\qquad F(x)=\sum_{v\in V}f_{v}(x_{N[v]}). (1) We write \mathrm{OPT}\coloneqq\max_{x\in\mathcal{L}^{V}}F(x)=F(x^{\star}) for the optimal value. We study the computational complexity of solving ( 1 ) as a function of structural properties of the underlying graph G . To keep the exposition self-contained, we briefly review the relevant graph-theoretic notions used throughout the paper. Definition 1 (Squared Graph) . Given an undirected graph G=(V,E) , the squared graph of G , denoted by G^{2} , is the graph on the same vertex set V in which two distinct vertices u,v\in V are connected by an edge if and only if their distance in G is at most two. Definition 2 (Tree Decomposition) . A tree decomposition of an undirected graph G=(V,E) is a pair (T,\{X_{i}\}_{i\in I}) , where T is a tree and each node i\in I is associated with a subset X_{i}\subseteq V , called a bag, such that the following conditions hold: 1. For every vertex v\in V , there exists at least one bag X_{i} such that v\in X_{i} . 2. For every edge \{u,v\}\in E , there exists a bag X_{i} such that \{u,v\}\subseteq X_{i} . 3. For every vertex v\in V , the set of nodes \{i\in I:v\in X_{i}\} induces a connected subtree of T . Definition 3 (Treewidth) . The width of a tree decomposition (T,\{X_{i}\}_{i\in I}) is defined as \max_{i\in I}|X_{i}|-1 . The treewidth of a graph G , denoted by \tw(G) , is the minimum width over all tree decompositions of G . Treewidth is a graph parameter that quantifies how “tree-like” a graph is; for instance, every tree has treewidth 1 . A large class of NP-hard problems becomes tractable on graphs of bounded treewidth via dynamic programming over a tree decomposition, with run time typically exponential in \tw(G) and polynomial in n ; prominent examples include Maximum Independent Set and Max-Cut [ 14 ] . Closely related notions also play a central role in probabilistic graphical models, where the complexity of exact inference scales exponentially with the treewidth [ 28 , 40 ] . For NAGL , although the objective ( 1 ) is defined over G , the relevant dependency structure is captured by the squared graph G^{2} . To see the intuition behind this, observe that each term f_{v} depends on all the labels in N[v] ; consequently, any two distinct interacting vertices are adjacent in G^{2} . Motivated by this observation, we will express both algorithmic and hardness statements in terms of the label-set size L and the parameter \tw(G^{2}) , which may be substantially larger than \tw(G) . The following remark shows that the model extends naturally to settings in which each reward function depends on labels beyond the immediate neighborhood. Remark 4 . Suppose the reward function f_{v} of a vertex v depends on the labels of a set D(v)\subseteq V (not necessarily equal to N[v] ). This can be captured as an instance of NAGL on an augmented graph H on vertex set V in which v is adjacent to every vertex in D(v)\setminus\{v\} . All statements in the paper apply to H by replacing G with H . In particular, if each f_{v} depends on all vertices within distance at most k from v in G , H=G^{k} . 3 Computational hardness of NAGL In this section, we establish computational hardness results for NAGL under the evaluation-oracle input model described in \Cref sec: setup. We give a reduction from k - SAT (and hence already from 3-SAT ) showing that NAGL is NP-hard even on star graphs. This reduction yields a SETH-tight lower bound in terms of \tw(G^{2}) and L that we will later match with a dynamic programming algorithm in \Cref sec:alg. We then complement these exact lower bounds with strong inapproximability. 3.1 SETH-tight lower bounds via SAT on a star graph Definition 5 (Strong Exponential Time Hypothesis (SETH) [ 24 , 33 ] ) . SETH asserts that for every \delta>0 there exists an integer k\geq 3 such that k - SAT on N variables cannot be solved in time (2-\delta)^{N}\cdot N^{O(1)} . Assuming SETH, we establish a tight lower bound for NAGL parameterized by \tw(G^{2}) and L via a reduction from k -SAT to NAGL on a star graph, as stated in the following lemma. Lemma 6 ( k -SAT to NAGL on a star) . Fix an integer L\geq 2 . Given a k -CNF formula \varphi with N variables, one can construct in polynomial time an instance of NAGL with label set \mathcal{L}=[L] on a star graph G with t+1 vertices, where t\coloneqq\lceil N/\log_{2}L\rceil , such that all local rewards take values in \{0,1\} and the optimal value satisfies \mathrm{OPT}=1 if \varphi is satisfiable and \mathrm{OPT}=0 otherwise. Moreover, G^{2} is a clique on t+1 vertices and hence \tw(G^{2})=t . Proof. Let t\coloneqq\lceil N/\log_{2}L\rceil , so that L^{t}\geq 2^{N} . Let G be the star with center c and leaves u_{1},\ldots,u_{t} . For each leaf u_{i} , set f_{u_{i}}\equiv 0 . We define the center reward f_{c} to ignore the label of c and depend only on the leaf labels. Fix a labeling x\in\mathcal{L}^{V} . For each i\in[t] , map x_{u_{i}}\in\{1,\ldots,L\} to the digit d_{i}\coloneqq x_{u_{i}}-1\in\{0,\ldots,L-1\} and interpret (d_{1},\ldots,d_{t}) as the base- L integer I(x)\coloneqq\sum_{i=1}^{t}d_{i}\,L^{i-1} . If I(x)\geq 2^{N} , set f_{c}(x_{N[c]})\coloneqq 0 . Otherwise, let \sigma(x)\in\{0,1\}^{N} be the N -bit binary representation of I(x) (padded with leading zeros), and define f_{c}(x_{N[c]})\coloneqq 1 iff \varphi evaluates to true under the assignment \sigma(x) , and 0 otherwise. Crucially, this evaluation takes time polynomial in |\varphi| (and in t\log L to compute I(x) ), hence polynomial in the instance size. Since all leaves have reward 0 , we have F(x)=f_{c}(x_{N[c]})\in\{0,1\} for every labeling x . If \varphi is satisfiable, let \sigma^{\star}\in\{0,1\}^{N} be a satisfying assignment and let I^{\star}<2^{N} be its integer value. Because L^{t}\geq 2^{N} , I^{\star} has a base- L representation using at most t digits, which yields labels for the leaves and hence a labeling x with I(x)=I^{\star} . For this labeling, \sigma(x)=\sigma^{\star} and thus F(x)=1 . Conversely, if \varphi is unsatisfiable then for every labeling x we have f_{c}(x_{N[c]})=0 , and hence F(x)=0 . Therefore \mathrm{OPT}=1 if and only if \varphi is satisfiable. Finally, any two distinct leaves are at distance 2 in G , so G^{2} is the clique K_{t+1} . Hence \tw(G^{2})=\tw(K_{t+1})=t . ∎ Remark 7 (Why the oracle model matters) . Lemma 6 relies on the fact that each local reward function is accessed via a succinct representation that supports polynomial-time evaluation. If f_{c} were given explicitly as a table over all assignments to N[c] , then the input would have size \Theta(L^{|N[c]|})=\Theta(L^{t+1}) , which is exponential in N (since L^{t}\geq 2^{N} ). Thus, the reduction is polynomial-time only in the evaluation-oracle model. Theorem 8 (NP-hardness on star graphs) . The NAGL problem is NP-hard even when the input graph G is a star and the label set is binary. Proof. We reduce from 3 - SAT , which is NP-hard. Given an instance \varphi with N variables, apply \Cref lem:sat-star with L=2 to construct in polynomial time an NAGL instance on a star graph with binary labels. By \Cref lem:sat-star, the constructed instance satisfies \mathrm{OPT}=1 if and only if \varphi is satisfiable. ∎ Theorem 9 (SETH-tight lower bound parameterized by \tw(G^{2}) ) . Fix an integer L\geq 2 . Assuming SETH, for every \varepsilon>0 there is no algorithm that solves NAGL with label set size L in time (L-\varepsilon)^{\tw(G^{2})}\cdot n^{O(1)} . This holds even when the input graph is restricted to be a star and all local rewards take values in \{0,1\} . Proof. Fix L\geq 2 and \varepsilon>0 . If L-\varepsilon\leq 1 (equivalently, \varepsilon\geq L-1 ), then the claimed running time bound is polynomial in n ; combined with \Cref lem:sat-star this would contradict SETH. Hence we may assume 10 . By SETH, there exists an integer k\geq 3 such that k - SAT on N variables cannot be solved in time (2-\delta)^{N}\cdot N^{O(1)} . Let k be this integer, and let \varphi be an instance of k - SAT with N variables. Construct the corresponding NAGL instance via \Cref lem:sat-star. The constructed graph is a star and satisfies \tw(G^{2})=t where t=\lceil N/\log_{2}L\rceil . Moreover, the instance has n=t+1=O(N) vertices, so n^{O(1)}\leq N^{O(1)} . Running \mathcal{A} on this instance decides satisfiability of \varphi in time \displaystyle(L-\varepsilon)^{t}\cdot n^{O(1)} \displaystyle\leq(L-\varepsilon)^{N/\log_{2}L+1}\cdot N^{O(1)} \displaystyle=(L-\varepsilon)\cdot 2^{\gamma N}\cdot N^{O(1)} \displaystyle=2^{\gamma N}\cdot N^{O(1)}\qquad\text{(absorbing constants into $N^{O(1)}$)}=(2-\delta)^{N}\cdot N^{O(1)}. This contradicts SETH. ∎ 3.2 Inapproximability We next establish hardness of approximation for NAGL . We use the standard multiplicative approximation ratio for maximization problems with nonnegative objective values (all hardness instances in this section have rewards in \{0,1\} ). Given a function \rho:\mathbb{N}\to[1,\infty) , a polynomial-time \rho(n) -approximation algorithm is required to output, on every instance on n vertices, a labeling x such that F(x)\geq\mathrm{OPT}/\rho(n) . Lemma 10 (Gap-at-zero barrier for multiplicative approximation) . Unless \mathsf{P}=\mathsf{NP} , for every function \rho:\mathbb{N}\to[1,\infty) there is no polynomial-time \rho(n) -approximation algorithm for NAGL , even when G is a star and all local rewards take values in \{0,1\} . Proof. Using \Cref lem:sat-star, a multiplicative approximation would distinguish \mathrm{OPT}=0 from \mathrm{OPT}=1 and decide satisfiability; see \Cref apd:inapprox-proofs. ∎ The previous lemma is a gap-at-zero barrier: without a promise that \mathrm{OPT}>0 , no algorithm can guarantee any finite multiplicative ratio. To obtain an inapproximability statement that remains informative under the promise \mathrm{OPT}>0 , we next reduce from the Maximum Independent Set ( MIS ) problem. Given a graph G=(V,E) , a set I\subseteq V is independent if it contains no edge of G , and we write \alpha(G) for the maximum size of an independent set. The reduction below produces NAGL instances with \mathrm{OPT}=\alpha(G) , and hence \mathrm{OPT}\geq 1 whenever |V|\geq 1 . Theorem 11 ( n^{1-\varepsilon} -inapproximability of NAGL ) . Unless \mathsf{P}=\mathsf{NP} , for every \varepsilon>0 there is no polynomial-time n^{1-\varepsilon} -approximation algorithm for NAGL . This holds even on instances with L=2 and \mathrm{OPT}>0 . Proof. We reduce from MIS by encoding independent sets as labelings with F(x)=|I(x)| ; see \Cref apd:inapprox-proofs. ∎ 3.3 On the parameter \tw(G^{2}) Our SETH-based lower bound rules out algorithms running in time (L-\varepsilon)^{\tw(G^{2})}\cdot n^{O(1)} (for constant L ), and in \Cref sec:alg we give a matching dynamic program. We briefly relate \tw(G^{2}) to more standard structural parameters of G . A first takeaway is that bounding \tw(G) alone does not control \tw(G^{2}) . For instance, if G is a star on n vertices, then \tw(G)=1 , but G^{2} is the clique K_{n} and thus \tw(G^{2})=n-1 . This is consistent with \Cref thm:np-hard-star, which shows that NAGL remains NP-hard even on star graphs. Bounding the maximum degree \Delta(G) alone is also insufficient: there are bounded-degree graph families with \tw(G)=\Omega(n) (e.g., bounded-degree expanders), and since G is a subgraph of G^{2} we have \tw(G^{2})\geq\tw(G)=\Omega(n) [ 22 , 20 ] . On the positive side, \tw(G^{2}) can be bounded in terms of \tw(G) and \Delta(G) . A standard bag-expansion argument gives \tw(G^{2})\leq(\tw(G)+1)\bigl(\Delta(G^{2})+1\bigr)-1\leq(\tw(G)+1)\bigl(1+\Delta(G)^{2}\bigr)-1 , where we used \Delta(G^{2})\leq\Delta(G)^{2} ; see, e.g., the discussion on the treewidth of the graph powers in [ 23 ] . 4 Algorithm and upper bound We give an exact algorithm for NAGL by dynamic programming over a tree decomposition of the squared graph G^{2} . The algorithm assumes that a width- t tree decomposition of G^{2} is given as part of the input; computing such a decomposition can be done using standard algorithms with an additional f(t)\,n^{O(1)} overhead [ 7 ] . Since N[v] is a clique in G^{2} for every v\in V , each local reward f_{v}(x_{N[v]}) can be evaluated inside a single bag. Therefore, the relevant parameter is \tw(G^{2}) . 4.1 Preliminaries: nice tree decompositions and cliques Define H\coloneqq G^{2} . We use a rooted nice tree decomposition (T,\{X_{i}\}_{i\in I}) of H with root r and empty root bag, of width t , as in [ 14 , Ch. 7.2] . Definition 12 (Nice tree decomposition) . Let H be an undirected graph. A nice tree decomposition of H is a tree decomposition (T,\{X_{i}\}_{i\in I}) together with a root r\in I such that X_{r}=\emptyset and every leaf has empty bag. Every node i\in I is of exactly one of the following types. • Leaf: i has no children and X_{i}=\emptyset . • Introduce: i has a single child j and X_{i}=X_{j}\cup\{a\} for some a\notin X_{j} . • Forget: i has a single child j and X_{i}=X_{j}\setminus\{a\} for some a\in X_{j} . • Join: i has exactly two children j_{1},j_{2} and X_{i}=X_{j_{1}}=X_{j_{2}} . It is standard that any width- t tree decomposition can be converted in polynomial time into a nice tree decomposition of the same width and with |I|=O(n\cdot t) nodes (see Ch. 7.2 of [ 14 ] ). In particular, |X_{i}|\leq t+1 for all i\in I . Lemma 13 (Cliques in bags [ 8 ] ) . Let (T,\{X_{i}\}_{i\in I}) be a tree decomposition of H . For every clique W in H there exists i\in I such that W\subseteq X_{i} . For every v\in V , the set N[v] is a clique in H since any two vertices in N[v] have distance at most 2 in G . Therefore, by \Cref lem:clique-in-bag, for each v there exists a bag X_{i} with N[v]\subseteq X_{i} , so f_{v}(x_{N[v]}) can be evaluated from a single bag-labeling. 4.2 Exact dynamic programming on G^{2} We name the algorithm CFDP (Clique-Focused Dynamic Programming) to reflect the fact that it exploits the clique structure of the neighborhoods and the corresponding property of tree decompositions. Below we give a description of the algorithm; the correctness proof is deferred to \Cref apd:proof-cfdp. Assigning reward terms to bags Fix any mapping \beta:V\to I such that N[v]\subseteq X_{\beta(v)} for all v\in V . Such a mapping can be constructed in polynomial time from (T,\{X_{i}\}_{i\in I}) . For each i\in I , let V_{i}\coloneqq\{v\in V:\beta(v)=i\} . For a labeling \ell:X_{i}\to\mathcal{L} , define \Phi_{i}(\ell)\coloneqq\sum_{v\in V_{i}}f_{v}\!\bigl(\ell_{N[v]}\bigr) . Then for every global labeling x\in\mathcal{L}^{V} we have F(x)=\sum_{i\in I}\Phi_{i}\bigl(x_{X_{i}}\bigr). (2) Dynamic program For a node i\in I , let T_{i} denote the set of nodes in the subtree of T rooted at i , and let U_{i}\coloneqq\bigcup_{j\in T_{i}}X_{j} be the set of vertices of H appearing in bags of this subtree. For a bag-labeling \ell:X_{i}\to\mathcal{L} , define \mathrm{DP}_{i}(\ell)\coloneqq\max\left\{\sum_{j\in T_{i}}\Phi_{j}\bigl(x_{X_{j}}\bigr):x\in\mathcal{L}^{U_{i}},\;x_{X_{i}}=\ell\right\} . We process the decomposition bottom-up. For each node type, the recurrence is as follows: \mathrm{DP}_{i}(\ell)=\begin{cases}0,&\text{if $i$ is a leaf (so $X_{i}=\emptyset$ and $\ell=\emptyset$),}\\ \mathrm{DP}_{j}\bigl(\ell_{X_{j}}\bigr)+\Phi_{i}(\ell),&\text{if $i$ introduces $a$ and $X_{i}=X_{j}\cup\{a\}$,}\\ \max_{c\in\mathcal{L}}\;\mathrm{DP}_{j}\bigl(\ell\cup\{a\mapsto c\}\bigr)+\Phi_{i}(\ell),&\text{if $i$ forgets $a$ and $X_{i}=X_{j}\setminus\{a\}$,}\\ \mathrm{DP}_{j_{1}}(\ell)+\mathrm{DP}_{j_{2}}(\ell)+\Phi_{i}(\ell),&\text{if $i$ is a join node and $X_{i}=X_{j_{1}}=X_{j_{2}}$.}\end{cases} Since the root bag is empty, the optimal value equals \mathrm{DP}_{r}(\emptyset) . An optimal labeling can be recovered by standard backpointers at forget nodes. Theorem 14 . There is an algorithm (CFDP) that, given an instance of NAGL on a graph G=(V,E) with label set \mathcal{L} ( L=|\mathcal{L}| ) and local reward functions \{f_{v}\}_{v\in V} , and a rooted nice tree decomposition (T,\{X_{i}\}_{i\in I}) of H\coloneqq G^{2} of width t , computes a labeling x^{\star}\in\mathcal{L}^{V} maximizing F(x) . The running time is O\bigl(n\cdot t\cdot L^{t+1}\bigr) . The space usage is O(|I|\cdot L^{t+1}) . If only the optimal value is required, the tables can be computed in a postorder traversal while discarding children after use, using O(h\cdot L^{t+1}) working space, where h is the height of T . Running time intuition. Each bag has size at most t+1 , hence there are at most L^{t+1} states per node. A standard implementation processes each node in O(L^{t+1}) time (including forget nodes via a single scan over child states) and a nice decomposition has O(n\cdot t) nodes [ 14 , Ch. 7.2] , yielding O(n\cdot t\cdot L^{t+1}) total time, up to polynomial factors in the input representation. Derivations of the stated bounds and further implementation details appear in \Cref subsec:cfdp-complexity. 4.3 Upper bound and tightness Given a width- t tree decomposition of H=G^{2} , CFDP computes an optimal labeling in time O\bigl(n\cdot t\cdot L^{t+1}\bigr) . In particular, taking t=\tw(G^{2}) yields an algorithm running in time O\bigl(n\cdot\tw(G^{2})\cdot L^{\tw(G^{2})+1}\bigr) . For binary labels L=2 this is 2^{O(\tw(G^{2}))}\cdot n^{O(1)} , i.e., a single-exponential FPT algorithm parameterized by \tw(G^{2}) . For constant L this is L^{O(\tw(G^{2}))}\cdot n^{O(1)} . Remark 15 (Tightness under SETH) . Fix an integer L\geq 2 . By \Cref thm:seTH-tight, assuming SETH there is no algorithm for NAGL running in time (L-\varepsilon)^{\tw(G^{2})}\cdot n^{O(1)} for any \varepsilon>0 . Together with the O\bigl(n\cdot\tw(G^{2})\cdot L^{\tw(G^{2})+1}\bigr) running time of CFDP, this shows that the base L in the exponential dependence on \tw(G^{2}) is optimal under SETH up to polynomial factors. 5 A coloring-based approximation for sparse graphs The inapproximability results of \Cref subsec:inapprox show that NAGL is NP-hard and hard to approximate on general graphs. In many interference-bandit applications, reward values are nonnegative (often in [0,1] ) and the interference graph is sparse, so each neighborhood N[v] is small [ 1 , 26 , 25 ] . Under such nonnegativity assumptions (and, when stating multiplicative ratios, assuming \mathrm{OPT}>0 so the guarantee is nonvacuous), meaningful approximation becomes possible. In this section we give an approximation algorithm whose approximation ratio depends only on a coloring of the squared graph G^{2} . In \Cref sec:planar-ptas we obtain a Baker-type PTAS for planar graphs. Finally, \Cref apd:submod treats the budgeted monotone submodular variant. Throughout this section, we assume that f_{v}(\cdot)\geq 0 for all v\in V . The following lemma states a key property of the color classes induced by a coloring of the squared graph G^{2} , which plays a central role in our algorithm. Lemma 16 (Disjoint neighborhoods within a G^{2} -independent set) . Let u,v\in V be distinct vertices. i.e., \{u,v\}\notin E(G^{2}) (equivalently, \dist_{G}(u,v)\geq 3 ). Then N[u]\cap N[v]=\emptyset . Consequently, for any proper coloring \psi of G^{2} , the sets \{N[v]:\psi(v)=c\} are pairwise disjoint for every color c . Proof. If N[u]\cap N[v]\neq\emptyset , then \dist_{G}(u,v)\leq 2 , hence \{u,v\}\in E(G^{2}) , a contradiction, and the second claim follows since each color class is independent in G^{2} . ∎ Algorithm Let H\coloneqq G^{2} and \psi:V\to[q] be any proper coloring of H with color classes C_{c}\coloneqq\{v\in V:\psi(v)=c\} . 1. For each vertex v , compute m_{v}\;\coloneqq\;\max\{f_{v}(a)\;|\;a:N[v]\to\mathcal{L}\} and fix a maximizer a_{v}:N[v]\to\mathcal{L} . (This can be done by enumerating all L^{|N[v]|} assignments to N[v] .) 2. For each color c\in[q] , assemble a labeling x^{(c)}\in\mathcal{L}^{V} by setting, for every v\in C_{c} and every u\in N[v] , x^{(c)}_{u}\coloneqq a_{v}(u) . Because the closed neighborhoods \{N[v]:v\in C_{c}\} are disjoint ( \Cref lem:disjoint-neighborhoods), no vertex receives conflicting labels. 3. Assign an arbitrary default label to all remaining vertices, compute M_{c}\coloneqq\sum_{v\in C_{c}}m_{v} , and output \hat{x}\coloneqq x^{(c^{\star})} where c^{\star}\;\in\;\argmax_{c\in[q]}\;M_{c} . Theorem 17 (Color-class maximization given a G^{2} -coloring) . Assume f_{v}(\cdot)\geq 0 for all v\in V . Given a proper q -coloring \psi of G^{2} , the above algorithm outputs a labeling \hat{x} such that F(\hat{x})\;\geq\;\frac{1}{q}\cdot\mathrm{OPT} . The algorithm performs \sum_{v\in V}L^{|N[v]|} oracle evaluations to compute \{m_{v}\} and runs in time O\left(L^{\Delta(G)+1}\right)\cdot n^{O(1)} . In particular, if L is constant and \Delta(G) is bounded, the algorithm runs in polynomial time. Proof sketch. Pick the color class maximizing M_{c} and combine its disjoint neighborhood maximizers. Full details (including the running-time bound) appear in \Cref apd:color-proof. ∎ Remark 18 . If a coloring is not provided, a greedy coloring of G^{2} can be computed in polynomial time and uses at most \Delta(G^{2})+1 colors [ 41 ] . This immediately yields a 1/(\Delta(G^{2})+1) -approximation. Moreover, since \Delta(G^{2})\leq\Delta(G)^{2} , this guarantee is a constant-factor approximation when \Delta(G) is bounded. 6 A Baker-type PTAS on planar bounded-degree graphs The coloring-based approximation of \Cref sec:color-approx yields a polynomial time 1/(\Delta(G^{2})+1) -approximation. On planar graphs of bounded maximum degree, one can do substantially better: although G^{2} need not be planar and may have large treewidth, the special neighborhood structure of NAGL (radius- 1 dependencies in G ) allows a Baker-style shifting scheme [ 4 ] . At a high level, we remove one BFS layer out of every k layers, and for each offset optimize the objective induced by vertices whose closed neighborhoods avoid the removed layer. We try all k offsets and return the best resulting labeling. A vertex can fail to be safe only if its layer or an adjacent layer is removed, so each vertex is unsafe for at most three offsets. With nonnegative rewards, this implies that some offset retains at least a (1-3/k) fraction of \mathrm{OPT} . We formalize this intuition below. Throughout this section we assume that f_{v}(\cdot)\geq 0 for all v\in V , and that the input graph G is planar with maximum degree \Delta(G) . Layering and shifting. Fix a root r_{0}\in V and perform a breadth-first search (BFS) from r_{0} . For each v\in V , let \lambda(v)\coloneqq\dist_{G}(r_{0},v) , and define the BFS layers B_{i}\coloneqq\{v\in V:\lambda(v)=i\} for i\geq 0 . For an integer k\geq 3 and an offset s\in\{0,1,\ldots,k-1\} , define the removed set R_{s}\;\coloneqq\;\{v\in V:\lambda(v)\equiv s\ (\mathrm{mod}\ k)\},\qquad G_{s}\;\coloneqq\;G[V\setminus R_{s}]. Since |\lambda(u)-\lambda(v)|\leq 1 for every edge uv\in E , removing R_{s} splits G_{s} into components contained in at most k-1 consecutive layers. Define the set of safe vertices S_{s}\;\coloneqq\;\{v\in V\setminus R_{s}:N[v]\cap R_{s}=\emptyset\}. For v\in S_{s} , we have N[v]\subseteq V\setminus R_{s} by definition. Hence the terms \{f_{v}(x_{N[v]}):v\in S_{s}\} depend only on labels of V\setminus R_{s} . The remaining vertices (V\setminus R_{s})\setminus S_{s} form a boundary whose local terms involve labels in R_{s} . For each offset s , consider the modified objective F_{s}(x)\;\coloneqq\;\sum_{v\in S_{s}}f_{v}(x_{N[v]}),\qquad x\in\mathcal{L}^{V\setminus R_{s}}. F_{s} is obtained from F by dropping exactly the terms that involve removed vertices. We compute an optimal labeling for F_{s} on G_{s} by exactly solving NAGL on each connected component of G_{s} via CFDP ( \Cref thm:cfdp-correct) after setting the local rewards of vertices outside S_{s} to 0 . We then extend the resulting partial labeling to all vertices in R_{s} by assigning an arbitrary default label. Finally, we evaluate the resulting k labelings under F and output the best one. Theorem 19 (Baker-type PTAS on planar bounded-degree graphs) . Assume f_{v}(\cdot)\geq 0 for all v\in V , and that G is planar with maximum degree \Delta(G) . For every \varepsilon\in(0,1) , there is an algorithm that outputs a labeling \hat{x}\in\mathcal{L}^{V} such that F(\hat{x})\;\geq\;(1-\varepsilon)\cdot\mathrm{OPT} , and the algorithm runs in time O\!\left(n\cdot k^{2}\cdot\Delta^{2}\cdot L^{\,O\left(k\Delta(G)^{2}\right)}\right)\cdot n^{O(1)} , where k\coloneqq\left\lceil\frac{3}{\varepsilon}\right\rceil . For constant L and \Delta(G) , this is an EPTAS. Proof. Set k\coloneqq\lceil 3/\varepsilon\rceil and consider the k offsets s\in\{0,1,\ldots,k-1\} . We first show that some offset preserves almost all of \mathrm{OPT} on the safe vertices, and then argue that our algorithm finds a labeling achieving at least that value. Let x^{\star} be an optimal labeling for the original instance. For each offset s , define \mathrm{OPT}_{s}\;\coloneqq\;\sum_{v\in S_{s}}f_{v}\!\bigl(x^{\star}_{N[v]}\bigr) . That is, \mathrm{OPT}_{s} is the contribution of vertices that are safe under offset s in the optimal labeling x^{\star} . We claim that each vertex v\in V belongs to S_{s} for all but at most three offsets s . Indeed, v\notin S_{s} iff v\in R_{s} or v has a neighbor in R_{s} . Since \lambda(\cdot) is a BFS layering, any neighbor u of v satisfies |\lambda(u)-\lambda(v)|\leq 1 . Thus v\notin S_{s} can occur only when s\equiv\lambda(v) , s\equiv\lambda(v)-1 , or s\equiv\lambda(v)+1\pmod{k} , i.e., for at most three offsets. Since all local rewards are nonnegative, \sum_{s=0}^{k-1}\mathrm{OPT}_{s}\;\geq\;\sum_{v\in V}(k-3)\cdot f_{v}\!\bigl(x^{\star}_{N[v]}\bigr)\;=\;(k-3)\cdot\mathrm{OPT}, and hence there exists an offset s such that \mathrm{OPT}_{s}\;\geq\;\left(1-\frac{3}{k}\right)\mathrm{OPT}\;\geq\;(1-\varepsilon)\mathrm{OPT}. Fix such an offset s . By definition of S_{s} , for every v\in S_{s} we have N[v]\subseteq V\setminus R_{s} . Therefore the restriction x^{\star}_{V\setminus R_{s}} is feasible for maximizing F_{s}(\cdot) and achieves value exactly \mathrm{OPT}_{s} . Consequently, the optimal value of F_{s} on G_{s} is at least \mathrm{OPT}_{s} . Our algorithm computes an optimal labeling x^{(s)} for F_{s} (by solving each component exactly and combining), hence F_{s}\!\left(x^{(s)}\right)\;\geq\;\mathrm{OPT}_{s}. Extending x^{(s)} arbitrarily to R_{s} yields a full labeling \hat{x} . Since all rewards are nonnegative, F(\hat{x})\geq F_{s}(\hat{x})=F_{s}(x^{(s)})\geq\mathrm{OPT}_{s}\geq(1-\varepsilon)\mathrm{OPT} . Fix an offset s and a connected component C of G_{s} . Each such component lies between two removed layers, so it has bounded depth in the BFS layering. Contracting the BFS layers closer to r_{0} than C (in particular the removed layer adjacent to C ) to a single vertex yields a planar graph in which C has radius O(k) , and hence \tw(C)=O(k) [ 18 ] . Using the bag-expansion bound from \Cref subsec:twG2 yields \tw(C^{2})=O\left(k\Delta(G)^{2}\right) . Thus CFDP runs in O\!\left(|C|\cdot k\Delta(G)^{2}\cdot L^{O\left(k\Delta(G)^{2}\right)}\right)\cdot n^{O(1)} time on each component, and summing over components and the k offsets yields the stated bound. Further details appear in \Cref apd:ptas-runtime. ∎ 7 Conclusion and open problems We studied the Neighborhood-Aware Graph Labeling ( NAGL ) problem, motivated by optimization oracles in bandits with network interference. We gave a standard dynamic program over a tree decomposition of G^{2} and showed that, under SETH, the base L in the exponential dependence on \tw(G^{2}) is optimal up to polynomial factors. For approximation with nonnegative rewards, we derived coloring-based algorithms and a Baker-type PTAS on planar graphs of bounded maximum degree (yielding an EPTAS for constant L ). Open problems include developing approximation guarantees driven by structure in the reward functions rather than by the graph class. In particular, it would be natural to study the restricted reward-function families that arise in the network-interference literature (e.g., exposure-mapping or other low-complexity neighborhood summaries) and ask which such families admit polynomial-time approximation algorithms, possibly even on general graphs. \crefname appendixAppendixAppendices \Crefname appendixAppendixAppendices \crefalias sectionappendix \crefalias subsectionappendix Appendices Appendix A Further discussion on related work Treewidth-based exact algorithms and dynamic programming Dynamic programming on tree decompositions is a central technique for designing exact algorithms for NP-hard graph problems, with running times typically exponential in the treewidth of the input graph. Classic examples include Maximum Independent Set , Vertex Cover , General Factor , and various connectivity problems (e.g., Hamiltonicity variants), all of which admit treewidth-parameterized algorithms via bag-based DP (see, e.g., [ 14 , 6 , 5 , 8 , 3 , 34 ] ). ETH- and SETH-based lower bounds further suggest that, for many problems, this exponential dependence on treewidth is essentially unavoidable [ 13 , 14 , 33 ] . In contrast, the local-interaction structure of NAGL makes the squared graph G^{2} the relevant object for complexity analysis. As discussed in \Cref subsec:twG2, the problem cannot be made tractable by assuming that either \tw(G) or \Delta(G) is constant. Instead, tractability requires both quantities to be small. Similar phenomena have been observed in prior work. One example is the Minimum Stable Cut problem, which is shown to admit algorithms with running time exponential in \tw(G)\cdot\Delta(G) [ 31 ] . Although that problem is also a combinatorial optimization problem with neighborhood-based objective functions, its underlying source of hardness differs from that of NAGL , since in our setting \tw(G^{2}) can be significantly smaller than \tw(G)\cdot\Delta(G) . A recent epidemic-control formulation with local interactions also exploits treewidth-parameterized optimization methods; see [ 17 ] . Graph labeling and local interaction models A large body of work studies graph labeling objectives in which the global score decomposes into unary and pairwise terms. \sum_{v\in V}g_{v}(x_{v})\;+\;\sum_{(u,v)\in E}g_{uv}(x_{u},x_{v}). This covers standard formulations in networked resource allocation and MAP inference in pairwise Markov random fields (MRFs), and is a dominant modeling choice in computer vision tasks such as image segmentation and stereo matching [ 9 , 29 , 40 , 28 ] . For these pairwise models, exact inference and MAP can be performed by variable elimination and junction-tree style algorithms whose time and space complexity are exponential in the treewidth of the original graph G , with typical bounds of the form O\!\left(n\cdot L^{\tw(G)+1}\right) for label alphabet size L [ 32 , 15 ] . Equivalently, NAGL can be viewed as a weighted constraint satisfaction problem (or factor graph) with one factor whose scope is N[v] for each v\in V . The corresponding primal graph is exactly G^{2} [ 15 , 21 ] . Our work can be seen as a strict generalization of the unary/pairwise setting. In particular, NAGL allows arbitrary neighborhood reward functions f_{v}(x_{N[v]}) , which in general cannot be represented as sums over edges. This leads to a fundamentally different structural parameter, namely \tw(G^{2}) . Combinatorial bandits and bandits with interference (oracle motivation) A recurring theme in multi-armed bandit models in sequential learning with large or structured action spaces is the use of an offline optimization oracle . Given estimated rewards (or upper confidence bounds), the learner repeatedly selects an action maximizing a global objective over an exponentially large decision set. This paradigm is standard in combinatorial bandits [ 10 , 11 , 12 , 36 , 16 , 38 ] . It becomes particularly salient in multi-armed bandits with network interference [ 26 , 1 , 25 ] , where each round assigns an arm (label) to every unit (node) and each unit’s reward depends on the joint assignment within its closed neighborhood. Closely related but distinct, [ 19 ] studies learning peer influence probabilities under a contextual bandit model with edge-level interventions. Interference-aware algorithms typically maintain local models for each node as a function of its neighborhood assignment. They then require maximizing the sum of these local objectives to choose a globally consistent joint assignment. This offline step coincides exactly with NAGL (with labels corresponding to arms and node rewards given by the current local estimates). This oracle is made explicit, for example, in the PUCB-I algorithm of [ 25 ] and in the elimination-based approach of [ 1 ] , where repeated global maximization is used as a subroutine across epochs. Our results complement this line of work by characterizing the computational and approximability limits of this oracle and by providing an optimal exact algorithm under bounded \tw(G^{2}) . Appendix B Omitted proofs This section presents the omitted proofs of the main text. B.1 Proof of Theorem 14 Proof. We prove the correctness of CFDP. The running time and space bounds are analyzed in \Cref subsec:cfdp-complexity. Let H\coloneqq G^{2} . Let (T,\{X_{i}\}_{i\in I}) be the rooted nice tree decomposition of H given to the algorithm, with root r . For every v\in V , recall that N[v] denotes the closed neighborhood of v in G . By \Cref lem:clique-in-bag, for every v\in V there exists a bag containing N[v] . Fix any mapping \beta:V\to I such that N[v]\subseteq X_{\beta(v)} for all v\in V . For each i\in I , define V_{i}\coloneqq\{v\in V:\beta(v)=i\} . For a labeling \ell:X_{i}\to\mathcal{L} , recall \Phi_{i}(\ell)\coloneqq\sum_{v\in V_{i}}f_{v}\!\bigl(\ell_{N[v]}\bigr) . By ( 2 ), for every labeling x\in\mathcal{L}^{V} we have F(x)=\sum_{i\in I}\Phi_{i}\bigl(x_{X_{i}}\bigr) . For a node i\in I , recall that T_{i} denotes the set of nodes in the subtree of T rooted at i . Define U_{i}\coloneqq\bigcup_{j\in T_{i}}X_{j} . For fixed i and \ell:X_{i}\to\mathcal{L} , the quantity \sum_{j\in T_{i}}\Phi_{j}\bigl(x_{X_{j}}\bigr) depends only on the restriction x_{U_{i}} . Moreover, any labeling of U_{i} consistent with \ell can be extended arbitrarily to a labeling of V without affecting \sum_{j\in T_{i}}\Phi_{j}(x_{X_{j}}) . Therefore, \max\left\{\sum_{j\in T_{i}}\Phi_{j}\bigl(x_{X_{j}}\bigr):x\in\mathcal{L}^{V},\;x_{X_{i}}=\ell\right\}=\max\left\{\sum_{j\in T_{i}}\Phi_{j}\bigl(x_{X_{j}}\bigr):x\in\mathcal{L}^{U_{i}},\;x_{X_{i}}=\ell\right\}. (3) Let \mathrm{OPT}_{i}(\ell) denote this common value. We prove by induction on the decomposition that for every i\in I and every \ell:X_{i}\to\mathcal{L} , the value computed by CFDP satisfies \mathrm{DP}_{i}(\ell)=\mathrm{OPT}_{i}(\ell) . Leaf. Let i be a leaf. Then X_{i}=\emptyset . Since N[v]\neq\emptyset for every v\in V , we have V_{i}=\emptyset and thus \Phi_{i}(\emptyset)=0 . Hence \mathrm{OPT}_{i}(\emptyset)=0=\mathrm{DP}_{i}(\emptyset) . Introduce. Let i be an introduce node with child j and X_{i}=X_{j}\cup\{a\} . We claim that a\notin U_{j} . Indeed, if a\in X_{k} for some k\in T_{j} , then by the connectedness condition of tree decompositions the vertex a must also belong to X_{j} , contradicting a\notin X_{j} . Consequently, in the maximization defining \mathrm{OPT}_{i}(\ell) , the contribution of the subtree T_{j} depends on \ell only through its restriction \ell_{X_{j}} , and its optimal value is \mathrm{OPT}_{j}(\ell_{X_{j}}) . Using T_{i}=T_{j}\cup\{i\} , we obtain \mathrm{OPT}_{i}(\ell)=\Phi_{i}(\ell)+\mathrm{OPT}_{j}\bigl(\ell_{X_{j}}\bigr), which matches the introduce recurrence. By the induction hypothesis, \mathrm{DP}_{j}\bigl(\ell_{X_{j}}\bigr)=\mathrm{OPT}_{j}\bigl(\ell_{X_{j}}\bigr) . Therefore \mathrm{DP}_{i}(\ell)=\mathrm{OPT}_{i}(\ell) . Forget. Let i be a forget node with child j and X_{i}=X_{j}\setminus\{a\} . Fix \ell:X_{i}\to\mathcal{L} . For any x\in\mathcal{L}^{U_{i}} with x_{X_{i}}=\ell , let c\coloneqq x_{a} and define \ell^{\prime}\coloneqq\ell\cup\{a\mapsto c\} . Then \ell^{\prime}:X_{j}\to\mathcal{L} and x_{X_{j}}=\ell^{\prime} . Since T_{i}=T_{j}\cup\{i\} and \Phi_{i} depends only on labels on X_{i} , we obtain \mathrm{OPT}_{i}(\ell)=\Phi_{i}(\ell)+\max_{c\in\mathcal{L}}\;\mathrm{OPT}_{j}\bigl(\ell\cup\{a\mapsto c\}\bigr), which matches the forget recurrence. By the induction hypothesis, this implies \mathrm{DP}_{i}(\ell)=\mathrm{OPT}_{i}(\ell) . Join. Let i be a join node with children j_{1},j_{2} and X_{i}=X_{j_{1}}=X_{j_{2}} . We claim that U_{j_{1}}\cap U_{j_{2}}=X_{i} . If a vertex v belongs to both U_{j_{1}} and U_{j_{2}} , then it appears in some bag in each of the two subtrees. By the connectedness condition, every bag on the path between these occurrences contains v , in particular X_{i} contains v . Thus U_{j_{1}}\cap U_{j_{2}}\subseteq X_{i} . The reverse inclusion is immediate since X_{i}\subseteq U_{j_{1}}\cap U_{j_{2}} . Moreover, U_{i}=U_{j_{1}}\cup U_{j_{2}} . Fix a labeling \ell:X_{i}\to\mathcal{L} . Since U_{j_{1}}\cap U_{j_{2}}=X_{i} , any pair of labelings x_{1}\in\mathcal{L}^{U_{j_{1}}} and x_{2}\in\mathcal{L}^{U_{j_{2}}} with {x_{1}}_{X_{i}}={x_{2}}_{X_{i}}=\ell can be combined into a labeling x\in\mathcal{L}^{U_{i}} . Moreover, for such an x we have \sum_{k\in T_{j_{1}}}\Phi_{k}\bigl(x_{X_{k}}\bigr)=\sum_{k\in T_{j_{1}}}\Phi_{k}\bigl((x_{1})_{X_{k}}\bigr) and \sum_{k\in T_{j_{2}}}\Phi_{k}\bigl(x_{X_{k}}\bigr)=\sum_{k\in T_{j_{2}}}\Phi_{k}\bigl((x_{2})_{X_{k}}\bigr) . It follows that \max_{x\in\mathcal{L}^{U_{i}},\,x_{X_{i}}=\ell}\left(\sum_{k\in T_{j_{1}}}\Phi_{k}\bigl(x_{X_{k}}\bigr)+\sum_{k\in T_{j_{2}}}\Phi_{k}\bigl(x_{X_{k}}\bigr)\right)=\mathrm{OPT}_{j_{1}}(\ell)+\mathrm{OPT}_{j_{2}}(\ell). Using T_{i}=T_{j_{1}}\cup T_{j_{2}}\cup\{i\} , we obtain \mathrm{OPT}_{i}(\ell)=\Phi_{i}(\ell)+\mathrm{OPT}_{j_{1}}(\ell)+\mathrm{OPT}_{j_{2}}(\ell), which matches the join recurrence. By the induction hypothesis, this implies \mathrm{DP}_{i}(\ell)=\mathrm{OPT}_{i}(\ell) . This completes the induction. Finally, since X_{r}=\emptyset and U_{r}=V , we have \mathrm{DP}_{r}(\emptyset)=\mathrm{OPT}_{r}(\emptyset)=\max_{x\in\mathcal{L}^{V}}\;\sum_{i\in I}\Phi_{i}\bigl(x_{X_{i}}\bigr) . By ( 2 ), this equals \max_{x\in\mathcal{L}^{V}}F(x) . CFDP therefore computes the optimal value. Moreover, storing the maximizing choice at each forget step yields a consistent set of backpointers. At join nodes we recurse into both children with the same bag labeling \ell , and consistency is ensured by the shared interface X_{i} . Following these backpointers reconstructs a labeling x^{\star}\in\mathcal{L}^{V} achieving \mathrm{DP}_{r}(\emptyset) . Thus CFDP outputs an optimal labeling for NAGL . ∎ B.2 Running time and space of CFDP We justify the bounds stated in \Cref thm:cfdp-correct. Let t be the width of the decomposition of G^{2} . Each bag has size at most t+1 , hence each DP table has at most L^{t+1} entries. Since |I|=O(n\cdot t) , it suffices to bound the work per node. For introduce and join nodes, each table entry is computed from a constant number of child entries, so the transition can be implemented in O(1) time per state. For forget nodes, although the recurrence takes a maximum over L labels, the table can be computed in O(L^{t+1}) time by scanning all child states \ell^{\prime}:X_{j}\to\mathcal{L} once, updating the parent key \ell=\ell^{\prime}_{X_{i}} via \mathrm{DP}^{\prime}_{i}(\ell)\leftarrow\max\{\mathrm{DP}^{\prime}_{i}(\ell),\mathrm{DP}_{j}(\ell^{\prime})\} , and finally setting \mathrm{DP}_{i}(\ell)=\mathrm{DP}^{\prime}_{i}(\ell)+\Phi_{i}(\ell) . Thus, every node can be processed in O(L^{t+1}) time, yielding a total DP running time of O(|I|\cdot L^{t+1})=O(n\cdot t\cdot L^{t+1}) . Computing all values \Phi_{i}(\ell) over all nodes i\in I and states \ell:X_{i}\to\mathcal{L} requires O(n\cdot L^{t+1}) oracle evaluations, since the sets V_{i} form a partition of V . Under the representation assumptions of \Cref sec: setup, each query f_{v}(\cdot) can be carried out in time \mathrm{poly}(|\text{input}|) . Thus, the overall running time can be written as O\bigl(n\cdot t\cdot L^{t+1}\bigr)\cdot\mathrm{poly}(|\text{input}|) , and the preprocessing does not change the exponential dependence on t and L . Storing all tables uses O(|I|\cdot L^{t+1}) space. If only the optimal value is required, the tables can be computed in a postorder traversal while discarding children after use, using O(h\cdot L^{t+1}) working space, where h is the height of T . Recovering an optimal labeling via backpointers requires O(|I|\cdot L^{t+1}) space in the worst case. B.3 Omitted proofs for inapproximability Proof of Lemma 10 . Consider an instance produced by \Cref lem:sat-star, for which F(x)\in\{0,1\} for every labeling x and \mathrm{OPT}\in\{0,1\} . Suppose \mathcal{A} is a polynomial-time \rho(n) -approximation algorithm and let \hat{x} be its output. If the underlying formula is satisfiable, then \mathrm{OPT}=1 and thus F(\hat{x})\geq 1/\rho(n)>0 , which forces F(\hat{x})=1 . If the formula is unsatisfiable, then \mathrm{OPT}=0 and hence F(x)=0 for all labelings x , implying F(\hat{x})=0 . Therefore, given \varphi , we can construct the corresponding NAGL instance from \Cref lem:sat-star, run \mathcal{A} , and output sat iff F(\hat{x})=1 . Since F(\hat{x}) can be evaluated in polynomial time in the oracle model, this decides satisfiability in polynomial time, implying \mathsf{P}=\mathsf{NP} . ∎ Proof of Theorem 11 . Suppose, for contradiction, that there exists a polynomial-time \rho(n) -approximation algorithm \mathcal{A} for NAGL , where \rho(n)=n^{1-\varepsilon} for some \varepsilon>0 and n\coloneqq|V| . Let G=(V,E) be an arbitrary graph. We construct an instance of NAGL on the same graph G with binary label set \mathcal{L}=\{1,2\} . For each v\in V , define f_{v}(x_{N[v]})\coloneqq\begin{cases}1&\text{if }x_{v}=2\text{ and }x_{u}=1\text{ for all }u\in N[v]\setminus\{v\},\\ 0&\text{otherwise.}\end{cases} For a labeling x\in\{1,2\}^{V} , let I(x)\coloneqq\{v\in V:x_{v}=2\text{ and }x_{u}=1\text{ for all }u\in N[v]\setminus\{v\}\} . Then I(x) is an independent set in G (since adjacent vertices cannot both satisfy the defining condition), and moreover F(x)=\sum_{v\in V}f_{v}(x_{N[v]})=|I(x)| . Hence F(x)\leq\alpha(G) for every labeling x . Conversely, for any independent set I\subseteq V , the labeling x=\mathbf{1}_{I} (setting x_{v}=2 iff v\in I ) satisfies F(x)=|I| . Therefore \mathrm{OPT}=\alpha(G) . Apply \mathcal{A} to this NAGL instance to obtain \hat{x} with F(\hat{x})\geq\mathrm{OPT}/\rho(n)=\alpha(G)/\rho(n) . Since |I(\hat{x})|=F(\hat{x}) , the set I(\hat{x}) is a \rho(n) -approximation for MIS on G . This contradicts the n^{1-\varepsilon} -inapproximability of MIS (equivalently, Max Clique on the complement graph) unless \mathsf{P}=\mathsf{NP} [ 42 ] . ∎ B.4 Proof of Theorem 17 Proof of Theorem 17 . Let x^{\star} be an optimal labeling. For each color c\in[q] , define \mathrm{OPT}_{c}\coloneqq\sum_{v\in C_{c}}f_{v}\bigl(x^{\star}_{N[v]}\bigr) . Since \{C_{c}\}_{c\in[q]} partitions V , we have \sum_{c=1}^{q}\mathrm{OPT}_{c}=\mathrm{OPT} . Hence there exists c\in[q] with \mathrm{OPT}_{c}\geq\mathrm{OPT}/q . Fix such a color c . For every v\in C_{c} , we have m_{v}\geq f_{v}\bigl(x^{\star}_{N[v]}\bigr) by definition of m_{v} as a maximum over all assignments to N[v] . Therefore, M_{c}\;=\;\sum_{v\in C_{c}}m_{v}\;\geq\;\sum_{v\in C_{c}}f_{v}\bigl(x^{\star}_{N[v]}\bigr)\;=\;\mathrm{OPT}_{c}\;\geq\;\mathrm{OPT}/q. By choice of c^{\star} , we obtain M_{c^{\star}}\geq M_{c}\geq\mathrm{OPT}/q . By construction of \hat{x} and \Cref lem:disjoint-neighborhoods, for every v\in C_{c^{\star}} we have \hat{x}_{N[v]}=a_{v} and thus f_{v}\bigl(\hat{x}_{N[v]}\bigr)=f_{v}(a_{v})=m_{v} . Since all local rewards are nonnegative, we conclude F(\hat{x})\;=\;\sum_{v\in V}f_{v}\bigl(\hat{x}_{N[v]}\bigr)\;\geq\;\sum_{v\in C_{c^{\star}}}f_{v}\bigl(\hat{x}_{N[v]}\bigr)\;=\;\sum_{v\in C_{c^{\star}}}m_{v}\;=\;M_{c^{\star}}\;\geq\;\mathrm{OPT}/q. The running time follows by enumerating all L^{|N[v]|} assignments to each N[v] to compute m_{v} and a maximizer a_{v} , plus O(n) overhead to compute the scores M_{c} and assemble \hat{x} . ∎ Corollary 20 (Greedy coloring instantiation and bounded-degree regime) . Without a coloring as input, one can compute a greedy coloring of G^{2} using at most \Delta(G^{2})+1 colors [ 41 ] . Since every vertex has at most \Delta(G)^{2} vertices within distance at most 2 in G , we have \Delta(G^{2})\leq\Delta(G)^{2} and obtain a (\Delta(G)^{2}+1) -approximation. The coloring overhead is polynomial in n . B.5 Running time details for Theorem 19 We justify the running-time bound in the proof of \Cref thm:planar-ptas. Fix an offset s and a connected component C of G_{s} . Contract all vertices in BFS layers closer to r_{0} than C into a single vertex z (and delete all other components) to obtain a planar graph \widetilde{G} containing C\cup\{z\} . For every v\in C , following the BFS tree from v toward r_{0} reaches a vertex in R_{s} after at most k-1 steps, hence \dist_{\widetilde{G}}(v,z)\leq k-1 . Thus the (graph-theoretic) radius of \widetilde{G}[C\cup\{z\}] is at most k-1 . Planar graphs have linear local treewidth, and in particular treewidth bounded by a function of the radius [ 18 ] , hence \tw(C)=O(k) . By the bag-expansion bound discussed in \Cref subsec:twG2, we have \tw(C^{2})\;\leq\;(\tw(C)+1)\bigl(\Delta(C^{2})+1\bigr)-1\;\leq\;(\tw(C)+1)\bigl(\Delta^{2}+1\bigr)-1\;=\;O(k\Delta^{2}), We use \Delta(C^{2})\leq\Delta(C)^{2}\leq\Delta^{2} . Applying CFDP ( \Cref thm:cfdp-correct) to each component costs O\!\left(|C|\cdot k\Delta^{2}\cdot L^{O(k\Delta^{2})}\right)\cdot n^{O(1)} time. Summing over components gives O\!\left(n\cdot k\Delta^{2}\cdot L^{O(k\Delta^{2})}\right)\cdot n^{O(1)} per offset. Multiplying by the k offsets yields the stated running time. Remark 21 (Beyond radius- 1 neighborhoods) . The constant 3 in the shifting loss arises from radius- 1 dependence: a term f_{v} is affected only if v lies within graph distance 1 of the removed layer. More generally, if each f_{v} depends on all vertices within distance at most p of v in G (equivalently, on G^{p} as in \Cref sec: setup), the same argument yields a (1-(2p+1)/k) -approximation by discarding the (2p+1) layers within distance p of the removed class. Appendix C Budgeted monotone submodular variant Many interference and activation/coverage models use binary decisions (treat/activate) subject to a cardinality budget, where each node’s utility depends on its own status and on an exposure induced by treated neighbors (e.g., count- or threshold-based exposure mappings) [ 2 , 27 , 30 ] . In such regimes, diminishing-returns structure is often natural; below we give a local sufficient condition that implies global submodularity of the NAGL objective. We restrict to binary labels \mathcal{L}=\{0,1\} and identify a labeling x\in\{0,1\}^{V} with the active set S\coloneqq\{v\in V:x_{v}=1\} . For each v\in V , define the induced local set function g_{v}:2^{N[v]}\to\mathbb{R}_{\geq 0} (where N[v] is the closed neighborhood in G ) by g_{v}(T)\coloneqq f_{v}(\mathbf{1}_{T}) , where \mathbf{1}_{T} is the \{0,1\} -assignment on N[v] that is 1 on T and 0 otherwise. Then the NAGL objective can be written as F(S)\;=\;\sum_{v\in V}g_{v}(S\cap N[v]) . Given a budget K , our goal is to solve \max\{F(S):S\subseteq V,\ |S|\leq K\} . We assume that each g_{v} is monotone and submodular on ground set N[v] . The next lemma lifts local diminishing returns on each N[v] to global submodularity of F . Lemma 22 (Local-to-global submodularity) . If every g_{v} is monotone and submodular, then F:2^{V}\to\mathbb{R}_{\geq 0} is monotone and submodular. Proof. Fix A\subseteq B\subseteq V and s\in V\setminus B . For each v , let A_{v}\coloneqq A\cap N[v] and B_{v}\coloneqq B\cap N[v] , so A_{v}\subseteq B_{v} . If s\notin N[v] then the marginal contribution of g_{v} is 0 under both A and B ; otherwise, submodularity of g_{v} gives g_{v}(A_{v}\cup\{s\})-g_{v}(A_{v})\geq g_{v}(B_{v}\cup\{s\})-g_{v}(B_{v}) . Summing over v yields diminishing returns for F ; monotonicity follows similarly. ∎ We maximize F(S) subject to |S|\leq K via Standard Greedy, which iteratively adds a vertex with maximum marginal gain \mathrm{marg}(u\mid S)\coloneqq F(S\cup\{u\})-F(S) . Only local terms for vertices w with u\in N[w] can change when adding u , and these vertices are exactly w\in N[u] . Thus \mathrm{marg}(u\mid S) can be computed using only oracle evaluations on the neighborhoods \{N[w]:w\in N[u]\} . Theorem 23 (Nemhauser–Wolsey–Fisher [ 35 ] ) . Let S_{\mathrm{gr}} be the set returned by Standard Greedy. Under the assumptions of Lemma 22 , F(S_{\mathrm{gr}})\;\geq\;\left(1-\frac{1}{e}\right)\cdot\max\{F(S):S\subseteq V,\ |S|\leq K\} . Appendix D Experiments We evaluate CFDP and an ILP baseline in three scenarios. In the budgeted monotone submodular regime, we additionally evaluate Standard Greedy from \Cref apd:submod. Scenarios 1–2 compare exact solvers (CFDP vs. ILP) on (i) road-network subgraphs, where \tw(G^{2}) grows with n , and (ii) 2\times r ladder graphs, where \tw(G^{2}) is constant. Scenario 3 studies the budgeted monotone submodular variant on large road subgraphs, comparing Standard Greedy with ILP. D.1 Experimental setup and methods CFDP is our exact DP on a tree decomposition of G^{2} ; runtimes are end-to-end, including constructing G^{2} and computing the decomposition. We compute tree decompositions using an implementation of the algorithm of [ 39 ] . As an exact baseline we formulate NAGL as an ILP (described below), solved with Gurobi Optimizer 11.0.0. We impose a fixed wall-clock time limit of 10 hours per run; timed-out instances are omitted from the plots. Road datasets and BFS-induced subgraphs. Scenarios 1 and 3 use road networks from the Network Data Repository (NRVis) [ 37 ] . We use the MatrixMarket datasets road-minnesota 2 2 2 https://nrvis.com/./download/data/road/road-minnesota.zip and road-usroads 3 3 3 https://nrvis.com/./download/data/road/road-usroads.zip . We treat these datasets as undirected, unweighted graphs. Given a starting vertex s , we compute a breadth-first search (BFS) order with deterministic tie-breaking by sorting neighbors by their identifiers. We fix s for each dataset and reuse the resulting BFS order across all values of n . We use s=2417 for road-minnesota and s=58610 for road-usroads . For a target size n , we take the first n vertices in this order and consider the induced subgraph. This produces connected subgraphs and ensures that increasing n yields nested instances. Scenario 1 (Minnesota road; synthetic rewards). We use BFS-induced subgraphs of the Minnesota road network ( road-minnesota ) with label set size L=3 . We vary n between 40 and 500. Local reward functions are synthetic random tables over \mathcal{L}^{|N[v]|} . Scenario 2 (ladder graphs; bounded \tw(G^{2}) ). We use 2\times r ladder graphs with n=2r and label set size L=3 . We vary r between 20 and 10000 (i.e., n between 40 and 20000). Local reward functions are synthetic random tables over \mathcal{L}^{|N[v]|} . Scenario 3 (US roads; budgeted monotone submodular). We use BFS-induced subgraphs of the US road network ( road-usroads ) with binary labels L=2 . We vary n between 200 and 126146. We impose a cardinality budget K=\min\{\lfloor 0.02n\rfloor,400\} . For each n we generate five random objectives and run five repetitions per objective. The objective is constructed using a max-type local gadget with weights w_{\mathrm{hi}}=100 and w_{\mathrm{lo}} sampled uniformly from [30,90] . Concretely, for each vertex v we sample a weight w_{\mathrm{lo}}(v)\in[30,90] and define g_{v}:2^{N[v]}\to\mathbb{R}_{\geq 0} by g_{v}(T)\coloneqq 0 for T=\emptyset and, for T\neq\emptyset , g_{v}(T)\coloneqq w_{\mathrm{hi}} if v\in T and g_{v}(T)\coloneqq w_{\mathrm{lo}}(v) otherwise. We set f_{v}(x_{N[v]})\coloneqq g_{v}(\{u\in N[v]:x_{u}=1\}) . Since g_{v} is a nonnegative combination of the submodular function T\mapsto\mathbf{1}[T\neq\emptyset] and the modular function T\mapsto\mathbf{1}[v\in T] , it is monotone and submodular, hence the assumptions of \Cref lem:local-to-global-submod hold. ILP baseline. We use the following standard local-configuration ILP for NAGL . For each vertex v\in V and label \ell\in\mathcal{L} we introduce a binary variable x_{v,\ell} indicating x_{v}=\ell . For each v\in V and neighborhood assignment a:N[v]\to\mathcal{L} we introduce a binary variable y_{v,a} selecting this local configuration. \displaystyle\max \displaystyle\sum_{v\in V}\ \sum_{a:N[v]\to\mathcal{L}}f_{v}(a)\,y_{v,a} (4) \displaystyle\text{s.t.} \displaystyle\sum_{\ell\in\mathcal{L}}x_{v,\ell}=1 \displaystyle\forall v\in V, \displaystyle\sum_{a:N[v]\to\mathcal{L}}y_{v,a}=1 \displaystyle\forall v\in V, \displaystyle\sum_{a:N[v]\to\mathcal{L},\,a(u)=\ell}y_{v,a}=x_{u,\ell} \displaystyle\forall v\in V,\ u\in N[v],\ \ell\in\mathcal{L}, \displaystyle\sum_{v\in V}x_{v,1}\leq K \displaystyle\text{(Scenario\penalty\ 3 only)}, \displaystyle x_{v,\ell}\in\{0,1\},\ y_{v,a}\in\{0,1\} \displaystyle\forall v,\ell,a. D.2 Results \Cref fig:exp12-runtime compares CFDP with the ILP baseline. In Scenario 1 (left), we use Minnesota road subgraphs with random rewards ( L=3 ), where \tw(G^{2}) grows with n . CFDP is consistently faster than ILP on all sizes solvable by both methods (e.g., 15 seconds vs. 16 minutes at n=200 ), before both eventually time out (CFDP at n=340 and ILP at n=260 ). In Scenario 2 (right), we use 2\times r ladder graphs with constant \tw(G^{2}) (here \tw(G^{2})=4 for all r ). CFDP scales smoothly up to n=20000 (about 20 seconds), whereas ILP already hits the time limit at n=120 , matching the predicted dependence on \tw(G^{2}) . In Scenario 3 ( \Cref fig:exp3-runtime,fig:exp3-ratio), we consider the budgeted monotone submodular variant ( L=2 ) on subgraphs of US road network with budget K=\min\{\lfloor 0.02n\rfloor,400\} . Greedy remains below about 21 seconds even at n=126{,}146 , while ILP takes about 30 minutes ( \Cref fig:exp3-runtime). Greedy achieves approximation ratios around 0.8 with little variation across n , exceeding the worst-case guarantee 1-1/e ( \Cref fig:exp3-ratio). We omit CFDP in Scenario 3 because it targets the unbudgeted additive/local objective. Extending it to a budgeted monotone submodular objective would both introduce a factor K in the DP state space and require redesigning the DP to handle a non-local set function F , whereas the ILP adds the budget via one constraint and Greedy is the standard approach. (a) Minnesota road subgraphs. (b) Ladder graphs. Here \tw(G^{2})=4 for all r . Figure 1 : Scenario 1–2 end-to-end runtime comparison of CFDP and the ILP baseline. End-to-end includes constructing G^{2} and computing the decomposition. Each point is the mean over five repetitions, with shaded bands showing one standard deviation. (a) Runtime. (b) Approx. ratio. Figure 2 : Scenario 3 results in the budgeted monotone submodular setting. Left: runtime comparison of Greedy and ILP (mean \pm one s.d. over 25 runs). Right: box plot of the approximation ratio F(S_{\mathrm{gr}})/\mathrm{OPT} over the same runs. The dashed line marks 1-1/e . Representative graph visualizations. \Cref fig:app-exp1-bfs and \Cref fig:app-exp3-bfs visualize BFS-induced subgraphs from Scenarios 1 and 3. The BFS start vertex s is highlighted. For Scenario 3 we visualize only the first 2000 BFS vertices for readability. Figure 3 : Scenario 1: BFS-induced subgraph of the Minnesota road network ( road-minnesota ) at n=350 and m=413 . The red star marks the BFS start vertex. Figure 4 : Scenario 3: BFS-induced subgraph of the US road network ( road-usroads ) at n=120000 and m=153{,}781 . The red star marks the BFS start vertex. For readability we visualize only the first 2000 BFS vertices.