1 Graph Homomorphism and Target Parameters↩︎

A graph homomorphism \(G \to H\) is a map from the vertices of a source graph \(G\) to the vertices of a target graph \(H\) that preserves edges. Homomorphisms to a fixed target encode assignments of local states, while homomorphisms from a small pattern encode global witnesses such as cliques or subgraph counts [1], [2]. The corresponding decision problem , , asks whether there exists a homomorphism between two given graphs. Various -hard graph problems are natural special cases of \(\problemabbr{HOM}\): for example, \(G\) has a proper \(k\)-coloring if and only if there exists a homomorphism \(G\to K_k\), whereas \(G\) contains a \(k\)-clique if and only if there is a homomorphism \(K_k\to G\). On the other hand, with an \(n\)-vertex source graph \(G\) and an \(h\)-vertex target graph \(H\) is a special case of (\(2\)-) with \(n\) variables over a domain of size \(h\). Thus, \(\problemabbr{HOM}\) may be viewed as \(\problemabbr{CSP}\) over a graph template.

A straightforward brute-force algorithm (that goes through all mappings) for and \(2\)- has running time \(O(h^n)=2^{O(n\log h)}\). Traxler [3] showed that, for \(2\)-, this upper bound cannot be improved substantially: under the Exponential Time Hypothesis (), there is no algorithm solving \(2\)- in time \(h^{o(n)}=2^{o(n\log h)}\). At the same time, a naive upper bound for the problem (asking whether a given graph admits a proper \(h\)-coloring) is also \(O(h^n)=2^{O(n\log h)}\), though it can be solved in single-exponential time: the first such algorithm has running time \(O(2.45^n)\) and is due to Lawler [4], whereas the best currently known upper bound is \(O^*(2^n)\) due to Björklund, Husfeldt, and Koivisto [5] (\(O^*(\cdot)\) suppresses multiplicative factors that grow polynomially). Obtaining a similar single-exponential upper bound for would be challenging. As proved by [6], under , for any \(\varepsilon>0\) and any \(k=O(n^{1-\varepsilon})\), there is no algorithm solving for \(n\)-vertex graphs in time \(n^{o(k)}\). Since is essentially \(\problemabbr{HOM}(K_k, \cdot)\), this rules out (under ) an upper bound \(2^{o(n\log h)}\) in the regime where \(n\) is much smaller than \(h\). [7] proved the same lower bound for any regime: under , for any \(h=h(n)\), there is no algorithm solving in time \(2^{o(n\log h)}\). This holds for the general case when both graphs \(G\) and \(H\) are part of the input and are not restricted in any way. At the same time, in various applications of , one or both of these graphs may come from a restricted graph family or even be fixed. A broader discussion of homomorphism complexity dichotomies is given in 10.

In recent years, less restrictive graph parameters \(p\) have been identified that allow one to solve in time⁵ \(p(H)^{O(n)}\): treewidth [8], clique-width [9], bounded complement bandwidth [10], maximum degree [11], extended clique-width [12], track number and persistent majority number [13]. These algorithms are faster than \(O(h^n)\) and allow one to solve  in plain-exponential time \(2^{O(n)}\) in the special case when \(p(H)\) is bounded. On the other hand, as proved by [11], chromatic number is too small: under , there is no \(\chi(H)^{O(n)}\) algorithm. The known lower and upper bounds with respect to various target graph parameters as well as connections between them are summarized in 1. It is interesting to note that, for each target graph parameter \(p\) from the left part of the figure, there is no \(p(H)^{o(n)}\) algorithm, under . This follows from the general lower bound due to [7] via padding (see [obs:parameter-padding-lower-bound]). Also, the argument of [7] together with [11] can be used to prove an optimal -based lower bound \(n^{\Omega(n)}\) for graphs \(H\) with \(\chi(H)=O(1)\) (see 8).

1.1 Our Results↩︎

We study the complexity of  in terms of target degeneracy (the minimum integer \(d\) such that every nonempty subgraph has a vertex of degree at most \(d\)), which is perhaps the most natural unresolved candidate between the known algorithmic and hardness regimes: on the one hand, each of bounded treewidth, bounded maximum degree, and bounded track number implies bounded degeneracy; on the other hand, bounded degeneracy implies bounded chromatic number.

Algorithmically, degeneracy has long served as a measure of sparse structure [14]–[21], and it appears in tight kernelization bounds for sparse graph problems [22]–[25]. The \(\problemabbr{HOM}\) counting problem was studied in degenerate graphs, but the degeneracy constraint is usually placed on the large input graph into which a fixed pattern is mapped. Starting with Bressan [26], this line gives near-linear and fine-grained classifications for counting subgraphs, induced subgraphs, homomorphisms, and homomorphic cycles in degenerate graphs [27]–[34]. In those results, the pattern is fixed and the running time is measured as a function of the sparse host, whereas in \(\problemabbr{HOM}\) both \(G\) and \(H\) are part of the input. There are also related results for bounded outdegree graphs [35], bounded-degeneracy hypergraphs [36], and recognition by homomorphism counts to \(2\)-degenerate graphs [37].

Our results show that the influence of degeneracy of \(H\) on the complexity of \(\problemabbr{HOM}\) differs significantly from that of the previously studied parameters. We show that, for every nondecreasing unbounded threshold function \(D\) satisfying \(D(n)=O(n^{1/3})\) and \(D(2n)=O(D(n))\), the promise \(\operatorname{degen}(H)\le D(n)\) problem admits no \(2^{o(D(n)n)}\) algorithm under .

We then show that the plain-exponential frontier is already crossed between degeneracy \(1\) and \(2\). Targets with degeneracy at most \(1\) are forests and therefore have bounded treewidth, so they are plain-exponential by [8]. In contrast, we construct hard instances of degeneracy \(2\), provided that the target is allowed to have size quasi-polynomial in \(n\).

Finally, we formulate a new barrier showing that improving the lower bound \(2^{o(\operatorname{degen}(H)n)}\) further to \(2^{\omega(\operatorname{degen}(H)n)}\) would be challenging. Informally, the reason is that such a reduction would have to be stronger than all known fine-grained reductions from \(3\)-\(\problemabbr{SAT}\). We make it formal below.

By the Sparsification Lemma [38], \(\cc{ETH}\) can be viewed as hardness of sparse \(3\)- with \(n\) variables and \(O(n)\) clauses. An explicit sparse formula has bit length \(\Theta(n\log n)\), therefore if \(s\) denotes the bit size of the input, then sparse \(3\)- is \(2^{\Omega(s / \log s)}\) hard. Many fine-grained reductions are known for various problems; however, to the best of our knowledge, not a single one of them establishes a lower bound better than \(2^{\Omega(s / \log s)}\), where \(s\) denotes the input bit size.

A concrete example of a problem exhibiting a gap between the known lower and upper bounds is the sparse \(2\)- problem. A brute-force algorithm for the \(2\)- with \(n\) variables over a domain of size \(h\) has running time \(O(h^n)\) and there are no \(h^{o(n)}\) algorithms under \(\cc{ETH}\) [3]. However, when the number of constraints is linear, the best known lower bound is only \(h^{\Omega(n / \log n)}\) [39], [40]. The question of improving the lower bound to \(h^{\Omega(n)}\) was raised in [40]. We note that, in order to close this gap, the lower bound would have to establish a bound stronger than \(2^{\Omega(s / \log s)}\), where \(s\) denotes the input size in bits; see 5.2.

A weaker version of this hypothesis was recently considered by Kulikov and Mihajlin [41] who proved that an -based lower bound \(2^{\Omega(s)}\) violates . We show that refuting a somewhat stronger version of [hyp:nocomp] implies new circuit lower bounds: if there is a uniform generator that converts \(O(n^{0.99})\) input bits into CNF formulas over \(n\) variables that are \(2^{\Omega(n)}\)-hard under , then \(\P^{\NP}\) has truly superlinear circuit size.

Finally, we show that a reduction showing a \(2^{\omega(\operatorname{degen}(H)n)}\) lower bound for under would refute [hyp:nocomp].

1.1.0.1 Techniques.

The lower bound of [thm:main-lb] is a reduction from the problem on graphs of maximum degree \(4\). We partition \(N\) vertices of the instance into vertex-buckets of size \(r\), so that the source of the produced \(\problemabbr{HOM}\) instance has only \(O(N/r)\) vertices, while the target must supply a state for every coloring of a bucket. The difficulty is to check the constraints between buckets without making these states densely connected; we do this by assigning \(O(r)\) labels to the buckets via an equitable coloring, so that every target vertex keeps degree \(O(r)\) and hence \(\operatorname{degen}(H)=O(r)\), while \(\operatorname{degen}(H)\cdot n\) stays linear in \(N\). The list constraints of the intermediate list-homomorphism instance are then removed by attaching a small rigid frame to both graphs. The main difference between [thm:main-lb] and the previous lower bounds for \(\problemabbr{HOM}\) [7], [11] is that we bucket not only the vertices but also the constraints between them. This approach allows us to keep the target degenerate whereas making the testing problem more difficult.

For [thm:constant-deg-lb], we start from the \(\cc{ETH}\)-hardness of sparse bounded-alphabet \(2\)- [40], encode it into \(\problemabbr{HOM}\) while keeping both graphs sparse, and then subdivide every edge into a path of length three; subdivision preserves homomorphisms while making the target \(2\)-degenerate, and sparsity keeps the size growth quasi-polynomial.

The barrier of [thm:unified-nocomp] rests on the following idea: in a \(D\)-degenerate target, the set of images still available to a source vertex under some partial homomorphism always admits a record of \(O(D\log n)\) bits. This reduces \(\problemabbr{HOM}\) to a succinct homomorphism problem whose instances can be encoded using a few bits, so a reduction proving a \(2^{\omega(\operatorname{degen}(H)n)}\) lower bound would compress sparse \(3\)-\(\problemabbr{SAT}\) beyond the \(s/\log s\) scale, contradicting [hyp:nocomp].

1.1.0.2 Organization.

2 fixes notation and assumptions. 3 proves the linear degeneracy lower bound. 4 proves the constant-degeneracy quasi-polynomial-target lower bound. 5 formalizes the no-compression barrier and proves its \(\problemabbr{HOM}\) and sparse \(\problemabbr{CSP}\) consequences. 6 proves the circuit lower-bound consequence. 7 summarizes the resulting target-side picture and lists open problems. 8 gives the polynomial-target bounded-chromatic lower bound.

2 Preliminaries↩︎

All logarithms in this paper are taken base \(2\). For a positive integer \(q\), we write \([q]=\{1,\ldots,q\}\). For a nonnegative integer \(q\), by \(\operatorname{bin}(q)\) we mean a binary encoding of \(q\). For a partial function \(f\), we write \(\operatorname{dom}(f)\) for its domain. All graphs are finite, undirected, and loopless unless explicitly stated otherwise. For a graph \(G\), we write \(V(G)\) and \(E(G)\) for its vertex and edge sets, \(N_G(v)\) for the open neighborhood of \(v\), \(\Delta(G)\) for its maximum degree, and \(\overline{G}\) for its complement. For a set \(S\subseteq V(G)\), the graph \(G[S]\) denotes the subgraph induced by \(S\).

Throughout the paper, \(G\) denotes the source graph and \(H\) denotes the target graph in a homomorphism instance. We write \(n=|V(G)|\) and \(h=|V(H)|\). In reductions from a source problem, \(N\) denotes the size parameter of the original instance.

A hypergraph \(\mathcal{A}=(C,\mathcal{E})\) consists of a finite vertex set \(C\) and a family \(\mathcal{E}\) of subsets of \(C\), called hyperedges. It is \(d\)-uniform if every hyperedge has size exactly \(d\). An automorphism of \(\mathcal{A}\) is a permutation of \(C\) that preserves the hyperedge family, and \(\operatorname{Aut}(\mathcal{A})\) denotes the automorphism group.

2.1 Homomorphism Problems↩︎

A homomorphism from a graph \(G\) to a graph \(H\) is a map \(\phi\colon V(G)\to V(H)\) such that \(uv\in E(G)\) implies \(\phi(u)\phi(v)\in E(H)\). We write \(G\to H\) if such a map exists. The two-input decision problem is denoted by \(\problemabbr{HOM}\). For graph classes \(\mathcal{G}\) and \(\mathcal{H}\), the notation \(\problemabbr{HOM}(\mathcal{G},\mathcal{H})\) denotes the restriction to instances \((G,H)\) with \(G\in\mathcal{G}\) and \(H\in\mathcal{H}\). The symbol “\(\cdot\)” means that the corresponding side is unrestricted; thus \(\problemabbr{HOM}(\cdot,H)\) is the fixed-target \(H\)-coloring problem and \(\problemabbr{HOM}(\cdot,\mathcal{H})\) is the restricted variable-target problem with targets from \(\mathcal{H}\).

In the problem, , the input is a pair of graphs \((G,H)\) together with a list \(L(v)\subseteq V(H)\) for every \(v\in V(G)\). The goal is to check whether there is a homomorphism \(\phi \colon G\to H\) satisfying \(\phi(v)\in L(v)\) for every source vertex \(v\).

2.2 Graph Parameters↩︎

We use the following basic graph parameters.

• The chromatic number \(\chi(G)\) is the least number of colors in a proper vertex coloring of \(G\).

• The maximum degree \(\Delta(G)\) is the maximum degree of a vertex of \(G\).

• The degeneracy \(\operatorname{degen}(G)\) is the least integer \(d\) such that every non-empty subgraph of \(G\) has a vertex of degree at most \(d\). Equivalently, \(G\) has an ordering in which each vertex has at most \(d\) later neighbors.

The remaining target-side parameters appearing in Figure 1 are defined formally in Appendix 9, where we also state parameter implications.

2.3 Constraint Satisfaction↩︎

A finite-domain \(\problemabbr{CSP}\) instance consists of variables, a finite domain, and constraints restricting tuples of variables. In this paper, the source problems are binary CSPs. For \(h\ge2\), a \((2,h)\)-\(\problemabbr{CSP}\) instance has variables taking values in \([h]\), unary constraints \(R_x\subseteq[h]\), and binary constraints \(R_{xy}\subseteq[h]^2\) on ordered pairs of distinct variables. An assignment satisfies the instance if it satisfies every unary and binary relation. The constraint graph has one vertex for each variable and one edge for each binary constraint, with no orientation. More generally, a \((k,h)\)-\(\problemabbr{CSP}\) instance has \(n\) variables over \([h]\) and constraints of arity at most \(k\). A sparse \((k,h)\)-\(\problemabbr{CSP}\) instance is one with at most \(O(n)\) constraints. In the encoding of \(\problemabbr{CSP}\), every constraint encodes its scope and the truth table of its relation.

2.4 Boolean Circuits↩︎

A Boolean circuit \(C\) over variables \(x_1, \dotsc, x_n\) is a directed acyclic graph with nodes of in-degree zero or two. The in-degree zero nodes are labeled by variables \(x_i\) and constants \(0\) or \(1\), whereas the in-degree two nodes are labeled by binary Boolean functions. The only out-degree zero node is the output of the circuit. A circuit \(C\) computes a Boolean function \(f \colon \{ 0, 1 \}^{n} \to \{ 0, 1 \}\) in a natural way.

For a language \(L\subseteq\{0,1\}^*\), a circuit \(C\) with \(n\) input variables computes \(L\) on inputs of length \(n\) if, for every \(x\in\{0,1\}^n\), \(C(x) = 1\) exactly when \(x\in L\). For a language \(L\), let \(\cc{CC}_L[n]\) denote the minimum size of a Boolean circuit computing \(L\) on all inputs of length \(n\). For a function \(s\colon\mathbb{N}\to\mathbb{N}\), write \[L\in\cc{SIZE}[s(n)]\] if for every sufficiently large \(n\), \[\cc{CC}_L[n]\le s(n).\]

Proving lower bounds on the circuit size of explicit functions is a long-standing challenge. A counting argument due to Shannon [42] shows that almost all Boolean functions on \(n\) variables require circuits of size \(\Omega(2^n/n)\). However, the best known lower bound for an explicit function⁷ is \(3.1n-o(n)\), due to Li and Yang [43].

For a string \(a\in\{0,1\}^N\), let \(\cc{CC}[a]\) denote the minimum size of a circuit on \(k=\ceil{\log_2 N}\) input bits whose first \(N\) truth-table values are the bits of \(a\). The remaining \(2^k-N\) truth-table values are ignored.

2.5 SAT Complexity Hypotheses↩︎

A \(k\)-\(\cc{CNF}\) formula is a conjunction of clauses of width at most \(k\), and \(k\)-\(\problemabbr{SAT}\) asks whether such a formula is satisfiable. A sparse \(3\)-\(\problemabbr{SAT}\) instance on \(N\) variables has \(O(N)\) clauses.

By the Sparsification Lemma of Impagliazzo, Paturi, and Zane [38], \(\cc{ETH}\) is equivalent to the statement that sparse \(3\)-\(\problemabbr{SAT}\) has no \(2^{o(N)}\)-time algorithm.

The following bounded-degree coloring consequence of \(\cc{ETH}\) is due to Kochol, Lozin, and Randerath [44].

Throughout the paper, we use the notion of a fine-grained reduction; for its formal definition and an overview of results in fine-grained complexity, see [45].

3 Linear Dependence on Degeneracy↩︎

This section reduces on bounded-degree graphs to , on targets whose degeneracy is small. The proof has two separate parts. First, we reduce to an  instance whose target already has small degeneracy. Then, we encode the list constraints into ordinary graph homomorphism. The construction is arranged so that the target degeneracy, multiplied by the number of source vertices, stays linear in the size of the original instance. Consequently, an algorithm whose running-time exponent were sublinear in this product would solve bounded-degree faster than \(\cc{ETH}\) permits.

3.1 Proof Overview↩︎

We take a graph \(Q\) on \(N\) vertices with maximum degree at most \(4\), and partition its vertices into \(\ceil{N/r}\) vertex-buckets of size at most \(r\); we fold each vertex-bucket into a single vertex of a list-homomorphism source.

The obstacle is that folding \(r\) vertices into one source vertex forces the target to supply, for each group, a vertex for every possible color pattern in \([3]^r\). The target may therefore have \(2^{O(r^2)}\) vertices, and the whole difficulty is to verify the \(3\)-coloring constraints between groups without making these vertices densely connected. Classical reductions do exactly that: they attach to each state a consistency gadget that lists all compatible states of its neighbors, and since a single group can interact with \(\Theta(r)\) others, the resulting states have degree exponential in \(r\).

We avoid this by further partitioning \(E(Q)\) into edge-buckets of at most \(r\) edges each. The partition is chosen so that the vertex-buckets meeting in one edge-bucket have distinct labels; hence one target state can refer to them by label without ambiguity.

The list target has two kinds of state vertices, plus a test board. A bucket-state vertex stores one color string \(c\in[3]^r\) for one labeled bucket. An edge-state vertex stores only the local data for one edge-bucket: the color strings of the participating labels and, for each edge in that edge-bucket, the two bucket positions that it connects. The global test board contains small test vertices that check one edge constraint at a time.

The point of edge splitting is locality in checking. Since an edge-state vertex is adjacent only to the bucket-states of its own participating labels and to the test vertices for its own edge-bucket, its degree is \(O(r)\) even though there may be \(2^{O(r^2)}\) edge-states in total.

After constructing this sparse list-homomorphism instance, we remove the lists. We add a small rigid frame to both graphs and connect each source vertex to the frame according to the target vertices it is allowed to use. Rigidity forces every homomorphism to respect these connections, so the lists are simulated inside ordinary \(\problemabbr{HOM}\).

The rest of the section follows this order. 3.2 builds the buckets and labels. 3.3 defines the instance and proves that it is equivalent to . 3.4 replaces lists by the rigid frame. 3.5 finishes the parameter bounds and derives the \(\cc{ETH}\) contradiction.

3.2 Bucket Decomposition↩︎

Let \(Q\) be an \(N\)-vertex graph of maximum degree at most \(4\). Fix an integer \(r\ge2\). We construct an  instance \((\Lambda_r,\Gamma_r,\mathcal{L}_r)\), where \(\Lambda_r\) is the source graph, \(\Gamma_r\) is the target graph, and \(\mathcal{L}_r\) is the list assignment. Thus, for each source vertex \(v\in V(\Lambda_r)\), the set \(\mathcal{L}_r(v)\subseteq V(\Gamma_r)\) consists of the allowed images of \(v\). Later, we convert it into an ordinary homomorphism instance \((G_r,H_r)\).

The reduction groups the vertices and edges of \(Q\) into small blocks. A vertex-bucket is a set of at most \(r\) vertices of \(Q\); one source vertex of \(\Lambda_r\) will be responsible for the colors of an entire vertex-bucket. An edge-bucket is a set of at most \(r\) edges of \(Q\); one source vertex of \(\Lambda_r\) will be responsible for checking all the \(3\)-coloring constraints inside one edge-bucket. We say that a vertex-bucket participates in an edge-bucket if it contains an endpoint of some edge of that edge-bucket.

A vertex of \(\Lambda_r\) that handles an edge-bucket must know the buckets whose colors it compares, so we give every vertex-bucket a label from a small set \([L]\) with \(L=O(r)\), and we arrange that the buckets participating in any single edge-bucket carry pairwise distinct labels. The next lemma produces such a bucketing and labeling.

For the rest of the construction, we pad each vertex-bucket \(B_i\) with dummy vertices to make it of size exactly \(r\).

3.3 List-Homomorphism Instance↩︎

3.3.0.1 The target.

Fix a bucketing and labeling from 1 for the rest of the section. We define the list target graph \(\Gamma_r\). Its vertices fall into three types. A bucket-state vertex stores one color string for one labeled vertex-bucket. An edge-state vertex stores the color strings of the labels participating in one edge-bucket, together with a partial map recording which two bucket-coordinates each edge compares. The test board is a family of test vertices; each one checks a declared endpoint of an edge, or rules out one monochromatic edge.

The bucket-state set is \[S_B=\{U_{\ell,c}\colon\ell\in [L],\;c\in[3]^r\}.\] A bucket-state represents a coloring string for one bucket of label \(\ell\).

The edge-state set is \[S_E := \left\{ W_{Z,c,\Pi} \colon \begin{array}{l} \varnothing\ne Z\subseteq[L],\;|Z|\le 2r,\\ c=(c_\ell)_{\ell\in Z},\;c_\ell\in[3]^r\text{ for every }\ell\in Z,\\ \Pi \colon \operatorname{dom}(\Pi)\subseteq[r]\to Z\times[r]\times Z\times[r] \end{array} \right\}.\] That is, \(\Pi\) is a partial function from \([r]\) to \(Z \times [r] \times Z \times [r]\). If \(\Pi(p)=(a,x,b,y)\), then the edge numbered \(p\) compares coordinate \(x\) of label \(a\) with coordinate \(y\) of label \(b\); the test board, defined next, verifies this claim and the resulting color condition. We make \(\Pi\) a partial function so that an edge-state compares only the edges of its own edge-bucket.

The test board is the union of the following families: \[\begin{align} T_A&=\{A_{p,a}\colon p\in[r],\;a\in[L]\},& T_B&=\{B_{p,b}\colon p\in[r],\;b\in[L]\},\\ T_X&=\{X_{p,x}\colon p,x\in[r]\},& T_Y&=\{Y_{p,y}\colon p,y\in[r]\},\\ T_C&=\{C_{p,\gamma}\colon p\in[r],\;\gamma\in[3]\}. \end{align}\] Let \(T=T_A\cup T_B\cup T_X\cup T_Y\cup T_C\).

The list target graph has vertex set \[V(\Gamma_r)=S_B\sqcup S_E\sqcup T.\]

Its edges are defined as follows.

• State edges. For \(U_{\ell,c}\in S_B\) and \(W_{Z,d,\Pi}\in S_E\), add the edge \[U_{\ell,c}W_{Z,d,\Pi}\] if and only if \[\ell\in Z\quad\text{and}\quad d_\ell=c.\]

• Test edges. For \(W=W_{Z,c,\Pi}\in S_E\) and \(\Pi(p)=(a,x,b,y)\), add the metadata edges \[WA_{p,a},\qquad WX_{p,x},\qquad WB_{p,b},\qquad WY_{p,y}.\] For \(\gamma\in[3]\), add the color-check edge \(WC_{p,\gamma}\) if and only if \[\Pi(p)=(a,x,b,y)\quad\text{and}\quad \neg(c_a[x]=\gamma=c_b[y]).\] The expression is evaluated only when \(\Pi(p)\) is defined, which already implies \(a,b\in Z\). If \(a=b\), the same string \(c_a\) is used in both positions. See 2.

3.3.0.2 The source.

The source graph records the bucket structure of \(Q\): it has a bucket vertex for each vertex-bucket, to be sent to a bucket-state, and an edge-bucket vertex for each edge-bucket, to be sent to an edge-state. A single copy of the test board is shared by all edge-buckets.

The graph \(\Lambda_r\) contains:

• a copy \(T'\) of the entire test board \(T\);

• one bucket vertex \(u_i\) for each vertex-bucket \(B_i\);

• one edge-bucket vertex \(w_j\) for each edge-bucket \(E_j\).

Add the following edges. First, join \(w_j\) to \(u_i\) if and only if \(B_i\) participates in \(E_j\). Second, index the edges in each edge-bucket by distinct values \(p\in[|E_j|]\subseteq[r]\) and orient them arbitrarily. If the edge with index \(p\) is oriented from coordinate \(x\) in bucket \(B_\alpha\) to coordinate \(y\) in bucket \(B_\beta\), put \(a=\lambda(B_\alpha)\) and \(b=\lambda(B_\beta)\), and add the following edges: \[w_jA'_{p,a},\quad w_jX'_{p,x},\quad w_jB'_{p,b},\quad w_jY'_{p,y},\] and the three edges \(w_jC'_{p,\gamma}\), for \(\gamma\in[3]\). The same global copied test vertex may be used by many edge-buckets.

3.3.0.3 Markers and lists.

We now introduce markers, which are auxiliary names used only to define list constraints. Each source and target vertex receives a set of markers. A source vertex \(v\) may be mapped precisely to those target vertices \(x\) for which \(A_{\Lambda}(v)\subseteq A_{\Gamma}(x)\), where \(A_{\Lambda}\) and \(A_{\Gamma}\) denote the marker sets associated with the vertices of \(\Lambda\) and \(\Gamma\), respectively. Throughout this construction, we write \(\beta_L\mathrel{\vcenter{:}}=\left\lceil\log_2 L\right\rceil\) and \(\beta_r\mathrel{\vcenter{:}}=\left\lceil\log_2 r\right\rceil\) for the label- and coordinate-index lengths. The markers are:

• selector markers \(\rho_U,\rho_W,\rho_A,\rho_B,\rho_X,\rho_Y,\rho_C\);

• for every label bit \(h\in[\beta_L]\) and bit value \(b\in\{0,1\}\), markers \(\mathsf D_{h,b}\), \(\mathsf A_{h,b}\), and \(\mathsf B_{h,b}\);

• for every coordinate bit \(h\in[\beta_r]\) and bit value \(b\in\{0,1\}\), markers \(\mathsf X_{h,b}\) and \(\mathsf Y_{h,b}\);

• for every edge-index bit \(h\in[\beta_r]\) and bit value \(b\in\{0,1\}\), a marker \(\mathsf P_{h,b}\);

• color markers \(\mathsf C_1,\mathsf C_2,\mathsf C_3\).

Thus the number of markers is \[M \mathrel{\vcenter{:}}= 7+6\beta_L+ 6\beta_r+3=O(\log r).\] For \(m\in\{L,r\}\) and \(z\in[m]\), let \(\operatorname{bin}_m(z)\) be the fixed-length binary encoding of \(z-1\in\{0,\ldots,m-1\}\) with \(\left\lceil\log_2 m\right\rceil\) bits. For a label \(\ell\in[L]\), define \[\begin{align} \mathsf D(\ell)&\mathrel{\vcenter{:}}=\{\mathsf D_{h,\operatorname{bin}_L(\ell)_h}\colon h\in[\beta_L]\},\\ \mathsf A(\ell)&\mathrel{\vcenter{:}}=\{\mathsf A_{h,\operatorname{bin}_L(\ell)_h}\colon h\in[\beta_L]\},\\ \mathsf B(\ell)&\mathrel{\vcenter{:}}=\{\mathsf B_{h,\operatorname{bin}_L(\ell)_h}\colon h\in[\beta_L]\}. \end{align}\] For a coordinate \(x\in[r]\), define \[\begin{align} \mathsf X(x)&\mathrel{\vcenter{:}}=\{\mathsf X_{h,\operatorname{bin}_r(x)_h}\colon h\in[\beta_r]\},\\ \mathsf Y(x)&\mathrel{\vcenter{:}}=\{\mathsf Y_{h,\operatorname{bin}_r(x)_h}\colon h\in[\beta_r]\}. \end{align}\] For an edge index \(p\in[r]\), define \[\mathsf{Pcode}(p)\mathrel{\vcenter{:}}=\{\mathsf P_{h,\operatorname{bin}_r(p)_h}\colon h\in[\beta_r]\}.\]

3.3.0.4 Target marker sets.

The target marker sets are \[A_\Gamma(U_{\ell,c})=\{\rho_U\}\cup \mathsf D(\ell),\] \[A_\Gamma(W_{Z,c,\Pi})=\{\rho_W\},\] and, for test vertices, \[A_\Gamma(A_{p,a})=\{\rho_A\}\cup\mathsf{Pcode}(p)\cup\mathsf A(a),\qquad A_\Gamma(B_{p,b})=\{\rho_B\}\cup\mathsf{Pcode}(p)\cup\mathsf B(b),\] \[A_\Gamma(X_{p,x})=\{\rho_X\}\cup\mathsf{Pcode}(p)\cup\mathsf X(x),\qquad A_\Gamma(Y_{p,y})=\{\rho_Y\}\cup\mathsf{Pcode}(p)\cup\mathsf Y(y),\] \[A_\Gamma(C_{p,\gamma})=\{\rho_C,\mathsf C_\gamma\}\cup\mathsf{Pcode}(p).\]

3.3.0.5 Source marker sets.

The source marker sets are \[\begin{align} A_\Lambda(u_i)&=\{\rho_U\}\cup \mathsf D(\lambda(B_i)), \\ A_\Lambda(w_j)&=\{\rho_W\}, \end{align}\] and each copied test vertex has the marker set of its target namesake, for example, \(A_\Lambda(A'_{p,a})=\{\rho_A\}\cup\mathsf{Pcode}(p)\cup\mathsf A(a)\), and the same applies to \(B'_{p,b}\), \(X'_{p,x}\), \(Y'_{p,y}\), and \(C'_{p,\gamma}\).

The lists are defined by marker containment: \[\mathcal{L}_r(v)=\{x\in V(\Gamma_r)\colon A_\Lambda(v)\subseteq A_\Gamma(x)\}.\] Thus each bucket vertex \(u_i\) lists precisely to bucket-states of label \(\lambda(B_i)\), each copied test vertex has a singleton list, and each edge-bucket vertex lists to all edge-states.

3.3.0.6 Correctness.

For completeness, a proper \(3\)-coloring of \(Q\) is read off into the target: each bucket vertex goes to the bucket-state holding its true color string, and each edge-bucket vertex goes to the edge-state holding those strings and the map for its edges.

For soundness, the lists force every source vertex into its intended type, the state edges make neighboring buckets agree on their shared color strings, and a missing color-check edge would witness a monochromatic edge of \(Q\), which a list homomorphism cannot produce.

3.4 Removing the Lists↩︎

A frame is a small rigid graph equipped with many pairwise disjoint groups of vertices, the ports. Its purpose is to simulate, inside ordinary graph homomorphism, the list constraints that the reduction needs: we attach a source vertex to the ports that encode its intended type, and rigidity guarantees that these incidences survive every homomorphism. Concretely, if a source vertex is complete to a chosen set of ports (that is, adjacent to every vertex of each of these ports), then the image of that vertex under any homomorphism must be complete to the corresponding target ports.

We build the frame in two steps. First we construct a \(3\)-uniform hypergraph that admits no nontrivial automorphism yet contains \(M\) disjoint perfect matchings into triples.

Now we turn this hypergraph skeleton into a graph by blowing up each hyperedge into a rigid graph gadget, which yields the frame together with its \(M\) ports. The gadget is a copy of the fixed graph \(J\) provided by the next lemma.

We turn the construction in 6 into a graph frame. The vertex set \(C\) of the hypergraph becomes a clique, whose vertices we call central; being the unique maximum clique, it must be preserved by every homomorphism, so a homomorphism induces a permutation \(\sigma\) of \(C\). Each hyperedge is then realized by a graph gadget, which is a copy of a fixed template, attached so that it can survive only if \(\sigma\) maps hyperedges to hyperedges.

For a vertex \(z\) outside the frame and a set \(A\subseteq [M]\), we say that \(z\) has anchor set \(A\), meaning that \(z\) is adjacent to every vertex in every port \(P_i\) with \(i\in A\), and to no other vertex of the frame.

3.4.0.1 Compiling the lists.

We now convert the marked list-homomorphism instance into an ordinary homomorphism instance. The needed property for the reduction is that every list is defined by containment of a non-empty marker set over the same \(M=O(\log r)\) markers.

3.5 Finishing the Lower Bound↩︎

3.5.0.1 Target degeneracy.

Recall that degeneracy is the least \(d\) for which the vertices can be ordered so that each has at most \(d\) neighbors later in the order. We eliminate the edge-states first: although there may be \(2^{O(r^2)}\) of them, each sees only the bucket-states of the labels it stores and the tests for its own edge indices, so it has degree \(O(r)\) (12). Once the edge-states are gone, every remaining non-frame vertex sees only its \(O((\log r)^2)\) frame anchors (13), and the frame itself has only \(O((\log r)^2)\) vertices. The whole order therefore witnesses degeneracy \(O(r)\). This upper bound is the only degeneracy estimate used in the lower-bound proof.

3.5.0.2 ETH consequence.

4 The Degeneracy Threshold from One to Two↩︎

This section proves the super-exponential lower bound for \(\problemabbr{HOM}(\cdot,\mathcal{H})\) even when \(\mathcal{H}\) has constant degeneracy. The reduction uses the following bounded-alphabet \(2\)- lower bound of [39], [40].

At a high level, the proof first reduces a sparse \(\problemabbr{CSP}\) instance \(\Gamma\) from 3 to \(\problemabbr{HOM}(G_{\Gamma}, H_\Gamma)\). Then, we take a subdivision of both graphs (i.e., we replace every edge of both graphs by a path of length three). This fixed subdivision preserves the existence of a homomorphism and makes the target \(2\)-degenerate.

However, the price of this step is an increase in size. After subdivision, the source has \(|V(G_\Gamma)|+O(|E(G_\Gamma)|)\) vertices, and the target has \(|V(H_\Gamma)|+O(|E(H_\Gamma)|)\) vertices. Thus the subdivision can be used in a fine-grained lower bound only when the source graph produced by the reduction is sparse.

4.1 Sparse Pinning Frame↩︎

We begin with the construction of a frame from [11] and then state its properties. For an integer \(s\ge1\), define a graph \(F_s\) as follows. It has \(s + 1\) distinguished vertices \(z_0,z_1,\ldots,z_s\). For every \(i\in[s]\), add four more vertices \(a_i,b_i,c_i,d_i\). Add the edges of the \(5\)-cycle \[z_{i-1}a_i,\quad a_ib_i,\quad b_ic_i,\quad c_id_i,\quad d_iz_{i-1},\] and add the five edges from \(z_i\) to this cycle, \[z_iz_{i-1},\quad z_ia_i,\quad z_ib_i,\quad z_ic_i,\quad z_id_i.\] Let \(Z_s=\{z_1,\ldots,z_s\}\) be the set of these cycle-completing vertices. 4 gives an example.

The next step is to use the distinguished vertices in \(Z_s\) as pin locations for the types that occur in the reduction. In that reduction, variables and edges both serve as types: for a  variable \(v\) and a possible value \(a\), the vertex \(A_{v,a}\) has type \(v\). For a  edge \(e=(u,v)\) and an allowed pair \((a,b)\), where \(a\) corresponds to \(u\) and \(b\) corresponds to \(v\), the vertex \(R_{e,a,b}\) has type \(e\). The vertex \(R_{e,a,b}\) is adjacent to the pin \(p_e\) and to the value vertices \(A_{u,a}\) and \(A_{v,b}\), whose types are \(u\) and \(v\), respectively; both are different from the constraint type \(e\).

Let \(T\) be a finite set of types, let \(L=|T|\), put \(s=10L+10\) and construct \(F_s\), then enumerate \(T=\{t_1,\ldots,t_L\}\). For \(t_j\), define two pins \[p_{t_j}=z_{10j},\qquad q_{t_j}=z_{10j+5}.\] The spacing ensures that all pins are distinct and that the two pins of any type have no common frame neighbor. For an edge type \(e\), only the pin \(p_e\) will be used by constraint vertices.

We say that a graph is obtained from \(F_s\) by safe attachments if new vertices are added only in the following two forms. A value vertex of type \(t\) is a new vertex adjacent to the two pins \(p_t\) and \(q_t\). A constraint vertex of type \(t\) is a new vertex adjacent to the pin \(p_t\) and to two value vertices whose types are different from \(t\). See 5.

4.2 Reduction↩︎

Let \[\Gamma=(P,\Sigma,\{C_e\}_{e\in E(P)})\] be a \(2\)- instance whose constraint graph \(P\) is a simple bipartite \(3\)-regular graph on \(k\) vertices. Let \(q=|\Sigma|\). Since \(P\) is \(3\)-regular, \(|E(P)|=3k/2\). Fix an arbitrary orientation of every edge \(e\in E(P)\).

Define the type set \[T=V(P)\cup E(P).\] Then \(|T|=k+3k/2=5k/2\). Build the pinning frame \(F_s\) with \(s=10|T|+10\) and with the pin pairs \((p_t,q_t)\) for \(t\in T\) as above.

The source graph \(G_\Gamma\) starts with a copy of \(F_s\). For every variable \(v\in V(P)\), add a vertex \(x_v\) and the two pin edges \(x_vp_v\) and \(x_vq_v\). For every oriented constraint edge \(e=(u,v)\in E(P)\), add a vertex \(y_e\) and the three edges \[y_ep_e,\qquad y_ex_u,\qquad y_ex_v.\]

The target graph \(H_\Gamma\) starts with a copy of the same frame \(F_s\). For every variable \(v\in V(P)\) and every value \(a\in\Sigma\), add a value vertex \(A_{v,a}\) and the two pin edges \(A_{v,a}p_v\) and \(A_{v,a}q_v\). For every oriented constraint edge \(e=(u,v)\) and every allowed pair \((a,b)\in C_e\), add a constraint vertex \(R_{e,a,b}\) and the three edges \[R_{e,a,b}p_e,\qquad R_{e,a,b}A_{u,a},\qquad R_{e,a,b}A_{v,b}.\]

For a graph \(X\), let \(S_3(X)\) denote the graph obtained from \(X\) by replacing every edge by a path of length \(3\).

5 No-Compression Barriers for SAT Reductions↩︎

[thm:main-lb] shows that degeneracy is visible linearly in the exponent of \(\problemabbr{HOM}\), but the hard targets behind it are large: the construction needs a target of size \(h=2^{\Theta(D^2)}\) to realize degeneracy scale \(D\). This is polynomial in \(n\) only while \(D=O(\sqrt{\log n})\); for larger degeneracy the target becomes superpolynomial. It is therefore natural to ask whether the same linear dependence can be forced while the target stays polynomially bounded.

This section gives a conditional reason to expect that it cannot, at least not through the standard route. Fine-grained lower bounds for \(\problemabbr{HOM}\), like those for many neighboring problems, are ultimately reductions from sparse \(3\)-\(\problemabbr{SAT}\) via \(\cc{ETH}\) and the Sparsification Lemma. We prove that a polynomial target reduction would “compress” the \(\problemabbr{SAT}\) instance, thereby contradicting [hyp:nocomp].

The argument has four parts. First, we discuss why an explicit sparse \(3\)-\(\problemabbr{SAT}\) instance carries hardness only at scale \(s/\log s\), where \(s\) is its bit length, and we recall the No-Compression Hypothesis stating no ordinary reduction does better. Second, we apply this argument to sparse \(\problemabbr{CSP}\) instances with a linear number of constraints, showing that one cannot improve the known lower bounds for it under [hyp:nocomp]. Third, we show that degenerate targets compress the boundary information of homomorphism into short list records; this lets us reduce \(\problemabbr{HOM}\) to another problem which is compressible. Finally, we show the resulting no-compression barrier for \(\problemabbr{HOM}\).

5.1 Sparse-SAT Information Scale↩︎

The Sparsification Lemma [38] lets one run \(\cc{ETH}\) through sparse \(3\)-\(\problemabbr{SAT}\): formulas on \(N\) variables with \(O(N)\) clauses still require \(2^{\Omega(N)}\) time under \(\cc{ETH}\). If the problem is measured by an explicit bit length \(s\), then to encode a sparse formula one needs \(s = \Theta(N\log N)\). Hence the hardness of sparse \(3\)-\(\problemabbr{SAT}\) is \[2^{\Omega(N)}=2^{\Omega(s/\log s)}.\] under \(\cc{ETH}\).

To prove a lower bound above this scale for an \(s\)-bit target problem, a sparse-\(\problemabbr{SAT}\) reduction must do some compression of the formula. A broad variety of fine-grained lower bounds is known, yet to our knowledge not one of them establishes a bound better than \(2^{\Omega(s/\log s)}\) in the input bit length \(s\).

This distinction has a precedent in the barrier of Kulikov and Mihajlin for the problem [41]. The input to this problem has size \(n^2\) and the best known upper bound is of the form \(2^{O(n^2)}\). Proving an \(\alpha^{n^2}\) lower bound for this problem under \(\cc{SETH}\) for any \(\alpha > 0\) would break \(\cc{SETH}\). The hypothesis we use is the \(\cc{ETH}\) analogue of that barrier, and it does not follow from their argument.

We now state the formal version of the no-compression principle used in the rest of the section.

5.2 Application to Sparse CSP↩︎

Note that for fixed \(k\), the condition holds for every \(h=h(n)\to\infty\) with \(h^k=O(\log n)\). However, for constant \(h\), one has \(n\log h=\Theta(n)\) and \(s/\log s=\Theta(n)\), so it does not rule out \(\cc{ETH}\) lower bounds.

5.3 Succinct List-Extension Homomorphism Problem↩︎

Suppose a partial homomorphism has already mapped some neighbors of an unmapped source vertex. The vertices of \(H\) still available to that vertex are exactly the common neighborhood in \(H\) of the images of its mapped neighbors. The lemma says that in a degenerate target this common neighborhood is either small or is cut out by few constraints.

Succinct list extension is the bookkeeping problem for exactly the information that survives this compression. Each source vertex carries either the short list of colors still available to it or a short certificate of that list, and the task is to complete the partial homomorphism subject to these lists.

Since \(h\le n\), a target vertex can be named using \(O(\log n)\) bits, so each list record costs \(O(D\log n)\) bits. The source edge set costs \(O(Tn\log n)\) bits, and the target, being \(D\)-degenerate, has at most \(Dh\) edges and so is stored in \(O(Dh\log h)=O(Dn\log n)\) bits. Hence every such instance has bit size \[s=O((T+D)n\log n).\]

5.4 Reduction↩︎

5.5 No-Compression Barrier↩︎

6 Generated Formulas and Hard Witnesses↩︎

This section shows that a strong refutation of [hyp:nocomp] implies circuit lower bounds. The result of Impagliazzo, Paturi, and Zane [38] shows that \(3\)-\(\problemabbr{SAT}\) remains hard even when the number of clauses is linear. Therefore, in some sense, it provides a generator that takes \(O(n \log n)\) bits as input and outputs a \(3\)-\(\problemabbr{SAT}\) formula on \(n\) variables that is hard under \(\cc{ETH}\). Probably, the most natural way to refute [hyp:nocomp] is to construct a more efficient generator of hard \(3\)-\(\problemabbr{SAT}\) formulas.

We show that if a short seed can generate hard formulas, then the generated formulas must sometimes have satisfying assignments of high circuit complexity. Those hard assignments can then be exposed one bit at a time by a language in \(\P^{\NP}\). Any small circuit for this language, after hardwiring the generator seed, would give a small circuit for the hard satisfying assignment, which is impossible.

The proof has three steps. First we formally state what we mean by generators of hard formulas. Second we show that this generator forces satisfying assignments of high circuit complexity: otherwise one could enumerate all small circuits, view each as an assignment, and solve the generated formulas in \(2^{o(N)}\) time. Finally we package the lexicographically first satisfying assignment into a language in \(\P^{\NP}\), which is an easy part.

Fix an \(\alpha\)-compressed hard formula generator \(G=\{G_N\}\). We now turn satisfying assignments into a language by asking for one indexed bit of the lexicographically first witness. Use any fixed effective self-delimiting encoding of triples \(\langle N,y,i\rangle\) such that, for fixed \(N\) and \(y\), all choices of the index \(i \in \{ 0, 1 \}^{\ceil{\log_2 N}}\) have the same total input length.

Let \(\ell(N)\) denote the input bit size of \(\problemabbr{LexWit}_G\), so \(\ell(N) \mathrel{\vcenter{:}}= \Theta(N^{\alpha})\).

Now, the idea is the following: if \(\problemabbr{LexWit}_G\) has small circuits on input length \(\ell\), then fixing \(N\) and a hard seed \(y\) inside such a circuit would leave a small circuit whose only input is the index \(i\). That circuit would output the satisfying assignment bit \(a_i\), contradicting 21.

7 Open Problems↩︎

The results of this paper show that target degeneracy has a genuinely intermediate behavior: it is too rich for the known algorithms, but the available lower-bound machinery still leaves the polynomial-target regime unresolved. [thm:main-lb-formal] shows that the dependence on \(\operatorname{degen}(H)\) must be linear in the exponent whenever this parameter grows, while 4 shows that even degeneracy \(2\) can be hard when the target is quasi-polynomial. At the same time, 7 suggests that substantially stronger lower bounds are unlikely.

The most direct algorithmic question is whether the trivial \(O^*(h^n)=2^{O(n\log h)}\) upper bound can be improved using degeneracy. Is there an algorithm solving \(\problemabbr{HOM}\) in time \(O^*\left(2^{\operatorname{poly}(\operatorname{degen}(H))\cdot n}\right)\)? Such an algorithm would match [thm:main-lb-formal] up to the dependence on \(\operatorname{degen}(H)\) and would separate degeneracy from target parameters that admit \(p(H)^{O(n)}\) algorithms.

The first concrete case is bounded degeneracy. For every fixed \(d\ge2\), can \(\problemabbr{HOM}\) on instances with \(\operatorname{degen}(H)\le d\) and \(h\le\operatorname{poly}(n)\) be solved in time \(O^*\left(2^{O_d(n)}\right)\)? 4 excludes this only when quasi-polynomial targets are allowed, and targets of degeneracy at most \(1\) are forests and hence admit plain-exponential algorithms. Thus the question is open already for \(d=2\) and polynomial-size targets.

A second direction is to understand whether the no-compression hypothesis has its own unconditional evidence. 11 explains why the lookup-table argument behind the barrier of Kulikov and Mihajlin [41] does not directly give such evidence for . In short, their argument turns a claimed \(2^{\Omega(s)}\) lower bound into a uniform \(2^{(1-\Omega(1))N}\) algorithm for the \(N\)-variable problem, by branching on all but a constant fraction of the variables and answering the remaining short queries from a precomputed table. This contradicts , but it does not contradict , which rules out only \(2^{o(N)}\) algorithms. In the spirit of [41], can one nevertheless prove a barrier showing that a disproof of [hyp:nocomp] would imply an unexpected consequence? One concrete form of this question is whether there is a generator of hard \(3\)-\(\problemabbr{SAT}\) formulas with a linear number of bits¹⁰.

Acknowledgments↩︎

The authors used ChatGPT 5.5 to assist in strengthening the constructions in 3 and in checking the lower-bound calculations in 6. The resulting suggestions were reviewed by the authors and incorporated only after independent verification. The authors assume responsibility for all content.

8 Bounded Chromatic Number↩︎

This section notes that the bounded chromatic number lower bound of [11] can be strengthened via ideas in [7].

We state four lemmas and then combine them. We use a grouping of [7] and then use the chromatic-number reduction of [11] to get the constant bound on \(\chi(H)\).

9 Graph Parameters↩︎

This appendix defines all target-side graph parameters from 1 and proves the implications represented by its arrows.

• The chromatic number \(\chi(G)\) is the least number of colors in a proper vertex coloring of \(G\).

• The maximum degree \(\Delta(G)\) is the maximum degree of a vertex of \(G\).

• The degeneracy \(\operatorname{degen}(G)\) is the least integer \(d\) such that every non-empty subgraph of \(G\) has a vertex of degree at most \(d\).

• A tree decomposition of \(G\) is a tree \(T\) with bags \(\beta(x)\subseteq V(G)\), \(x\in V(T)\), such that every vertex and every edge of \(G\) is covered by a bag and the bags containing any fixed vertex form a non-empty connected subtree of \(T\). The treewidth \(\operatorname{tw}(G)\) is the minimum value of \(\max_{x\in V(T)}|\beta(x)|-1\) over all tree decompositions of \(G\) [49].

• For \(k\ge1\), a \(k\)-expression builds \(k\)-labeled graphs by creating one vertex of a chosen label, taking disjoint unions, joining all vertices of one label to all vertices of another label, and relabeling vertices. The clique-width \(\operatorname{cw}(G)\) is the least \(k\) such that some \(k\)-expression represents \(G\) after labels are forgotten [50], [51].

• The extended clique-width \(\operatorname{ecw}(G)\) is the analogous minimum for extended \(k\)-expressions of Bulatov and Dadsetan [12]. Such expressions add to \(k\)-expressions the connect operation \(\eta_{\mathcal{T}}\) between two labeled graphs and the beta operation \(\beta_{\vec{n},\sigma,\mathcal{S}}\), which replaces each vertex of label \(i\) by \(n_i+1\) labeled copies and keeps edges according to \(\mathcal{S}\).

• For a linear order \(v_1,\ldots,v_m\) of \(V(G)\), its bandwidth is \(\max\{|i-j|:v_iv_j\in E(G)\}\). The bandwidth \(\operatorname{bw}(G)\) is the minimum such value over all linear orders, and the complement bandwidth is \(\operatorname{bw}(\overline{G})\) [52].

• A track layout of \(G\) is a proper coloring \(\gamma\) together with a linear order \(\prec\) of \(V(G)\) such that no two edges \(u_1u_2,v_1v_2\) with \(\gamma(u_1)=\gamma(v_1)\) and \(\gamma(u_2)=\gamma(v_2)\) satisfy \(u_1\prec v_1\) and \(v_2\prec u_2\). The track number \(\operatorname{tn}(G)\) is the least number of colors in a track layout [53].

• Given a proper coloring \(\gamma\colon V(G)\to[k]\), let \(\mathbf{\Gamma}_{G,\gamma}\) be the binary constraint language on domain \(V(G)\) with relations \[R_{ij}=\{(u,v)\in V(G)^2\colon\gamma(u)=i,\;\gamma(v)=j,\;uv\in E(G)\},\qquad i,j\in[k].\] A ternary operation \(m\colon D^3\to D\) is a majority operation if \(m(b,a,a)=m(a,b,a)=m(a,a,b)=a\) for all \(a,b\in D\). For tuples \(t_1,t_2,t_3\) of the same arity, write \(f(t_1,t_2,t_3)\) for the tuple obtained by applying \(f\) coordinatewise. A persistent majority triple for a binary crisp constraint language \(\mathbf{\Gamma}\) over domain \(D\) is a triple \((f_1,f_2,f_3)\) of operations \(D^3\to D\) such that \(f_1\) is majority, \[\{\!\{f_1(a_1,a_2,a_3),f_2(a_1,a_2,a_3),f_3(a_1,a_2,a_3)\}\!\}=\{\!\{a_1,a_2,a_3\}\!\}\] for all \(a_1,a_2,a_3\in D\), and \[\{\!\{f_1(t_1,t_2,t_3),f_2(t_1,t_2,t_3),f_3(t_1,t_2,t_3)\}\!\}=\{\!\{t_1,t_2,t_3\}\!\}\] for every relation \(R\in\mathbf{\Gamma}\) and all \(t_1,t_2,t_3\in R\). A persistent majority coloring of \(G\) is a proper coloring \(\gamma\) such that \(\mathbf{\Gamma}_{G,\gamma}\) has a persistent majority triple. The persistent majority number \(\operatorname{pmn}(G)\) is the least number of colors in a persistent majority coloring [13].

9.1 Implications in the Parameter Map↩︎

9.2 Padding Lower Bounds↩︎

We also note that the upper bounds in 1 are tight under \(\cc{ETH}\) for all parameters (except complement bandwidth).

Complement bandwidth \(\operatorname{bw}(\overline{H})\) increases when adding isolated vertices, so the observation above does not follow. Moreover, for any graph \(H\) on \(h\) vertices with \(\operatorname{bw}(\overline{H}) \le p\) it follows that \(\omega(H) \ge \left\lceil \frac{h}{p + 1} \right\rceil\), hence if \(h(n) > (n - 1) (p(n) + 1)\), then for every graph \(G\) on \(n\) vertices, there is a homomorphism \(G \to H\). Thus, the above observation is false for complement bandwidth.

10 The Graph Homomorphism Problem and Its Complexity Dichotomies↩︎

The lower bound \(2^{\Omega(n\log h)}\) for \(\problemabbr{HOM}\) holds for the general case when both graphs \(G\) and \(H\) are part of the input and are not restricted in any way [7]. At the same time, in various applications of the  problem, one or both of these graphs may come from a restricted graph family or even be fixed. There is a rich variety of results studying the complexity of special cases of . Complexity dichotomies ask where the boundary lies between the tractable and intractable sides of the relevant complexity model, such as \(\P\) versus \(\NP\)-hardness, \(\cc{FPT}\) versus \(\cc{W}[1]\)-hardness, or \(\cc{FP}\) versus \(\#\P\)-hardness. Fine-grained classifications ask, once the problem is intractable, which structural features determine the correct exponential running time.

10.0.0.1 Fixed and Restricted Source Graphs.

For the fixed source problem \(\problemabbr{HOM}(G, \cdot)\), the brute-force algorithm with running time \(O(h^{n})\) is polynomial. For restricted source graph classes \(\mathcal{G}\), the question is what properties of \(\mathcal{G}\) make \(\problemabbr{HOM}(\mathcal{G},\cdot)\) tractable. Dalmau, Kolaitis, and Vardi [55] and Grohe [56] showed that \(\problemabbr{HOM}(\mathcal{G}, \cdot)\), parametrized by the size of the source graph, is in \(\cc{FPT}\) precisely when the cores of graphs in \(\mathcal{G}\) have bounded treewidth, and is \(\cc{W}[1]\)-hard otherwise. See 6. Dalmau and Jonsson [57] proved the analogous result for counting homomorphisms.

Fine-grained source-side results further show that the known dynamic-programming exponents are often the right ones. For vertex cover, [11] give an \(O(h^{\operatorname{vc}(G)})\) algorithm and a matching \(\cc{ETH}\) lower bound \(h^{\Omega(\operatorname{vc}(G))}\). Marx [39] showed that the \(h^{O(\operatorname{tw}(G))}\) algorithm cannot be significantly improved under \(\cc{ETH}\). Okrasa and Rzążewski [58] showed that if \(H\) is a projective core, then there is no \((h-\varepsilon)^{\operatorname{tw}(G)} n^{O(1)}\) algorithm, for any \(\varepsilon>0\), under \(\cc{SETH}\). Since almost all graphs are projective cores [59], [60], this covers almost all targets; moreover, the result can be lifted to all targets under long-standing conjectures on the properties of projective cores [61], [62]. This was extended by [63], who proved both lower and upper bounds \(O^*(s(H)^{\operatorname{cw}(G)})\) under the same conjectures, where \(s\) is a signature number of \(H\). Okrasa, Piecyk, and Rzążewski [64], building on the result of Egri, Marx, and Rzążewski [65], showed that for all graphs \(H\) where () is \(\NP\)-hard, it also cannot be solved in time \((h - \varepsilon)^{\operatorname{tw}(G)} n^{O(1)}\), for any \(\varepsilon > 0\), under \(\cc{SETH}\). For counting list homomorphisms, Focke, Marx, and Rzążewski [66] identify the exact exponent base in running time and prove matching \(\#\cc{SETH}\) lower bounds. [67] provide a characterization of the case when \(G\) is parametrized by cutwidth in terms of the asymptotic rank parameter they introduce.

10.0.0.2 Fixed Target Graphs.

The fixed target version \(\problemabbr{HOM}(\cdot,H)\) is also well understood. Hell and Nešetřil [68] proved that \(\problemabbr{HOM}(\cdot,H)\) is polynomial-time solvable when \(H\) is bipartite, and is \(\NP\)-complete otherwise; Meyer and Opršal recently gave a topological proof [69]. Thus, the coarse-grained complexity class of \(\problemabbr{HOM}(\cdot,H)\) is determined by an easy-to-compute parameter of \(H\): whether \(\chi(H)\le2\) or not; see 7. The Feder–Vardi dichotomy conjecture for finite-domain \(\problemabbr{CSP}\)s [70] was proved independently by Bulatov and Zhuk, giving a complete algebraic classification of fixed-target tractability [71], [72].

The same dichotomy philosophy extends to several homomorphism variants. Feder and Hell [73] showed that if each vertex of \(H\) has a loop, then \(\problemabbr{LHOM}(\cdot, H)\) is in \(\P\) if \(H\) is an interval graph and \(\NP\)-complete otherwise. Feder, Hell, and Huang [74] showed that if \(H\) has no loops, then \(\problemabbr{LHOM}(\cdot, H)\) is in ¶ if the complement of \(H\) is a circular-arc graph with clique-cover number two, and is -complete otherwise. Finally, Feder, Hell, and Huang [75] defined a new class of graphs with possible loops, called bi-arc graphs, and showed that if \(H\) is a bi-arc graph, then \(\problemabbr{LHOM}(\cdot, H)\) can be solved in polynomial time, and otherwise the problem is -complete. In the reflexive case, bi-arc graphs coincide with interval graphs; in the irreflexive case, they coincide with bipartite graphs whose complement is a circular-arc graph. Dyer and Greenhill [76] showed that \(\#\problemabbr{HOM}(\cdot, H)\) is #¶-complete unless every connected component of \(H\) is an isolated vertex without a loop, a complete graph with all loops present, or a complete unlooped bipartite graph; otherwise it is in \(\cc{FP}\). This dichotomy was extended in numerous ways: to weighted graphs [77]–[81], directed graphs [82], [83], and the number of homomorphisms modulo a fixed prime [84]–[86]. Chen, Curticapean, and Dell [87] showed that the hard cases from [76] require \(2^{\Omega(n)}\) time under \(\cc{ETH}\). For finite-domain counting \(\problemabbr{CSP}\)s, the exact tractable side is also sharply classified by algebraic conditions [88]–[90]. We refer to Bulatov’s survey [91] and the book of Hell and Nešetřil [2] for a broader background.

10.0.0.3 Restricted Target Graphs.

The fine-grained picture becomes much less complete for the restricted target version \(\problemabbr{HOM}(\cdot,\mathcal{H})\). Several recent results identify properties of the target class \(\mathcal{H}\) that bring \(\problemabbr{HOM}(\cdot,\mathcal{H})\) down to single-exponential time. Fomin, Heggernes, and Kratsch [8] gave an \(O^*((2\operatorname{tw}(H)+1)^n)\) algorithm. Wahlström [9] gave an \(O^*((2\operatorname{cw}(H)+1)^{\max\{n,h\}})\) algorithm for bounded clique-width. Bulatov and Dadsetan [12] extended this to bounded extended clique-width, giving an \(O^*((4\operatorname{ecw}+4)^h+(2\operatorname{ecw}+1)^n)\) algorithm. Fomin, Golovnev, Kulikov, and Mihajlin [11] gave an \(O^*(\Delta(H)^n)\) algorithm for bounded maximum degree, while Rzążewski [10] gave an \(O^*((\operatorname{bw}(\overline{H})+2)^n)\) algorithm for bounded complement bandwidth. Recently, Carbonnel [13] proved a \(2^{O(n)}\) upper bound when \(\mathcal{H}\) excludes a fixed topological minor, and also gave \(O^*(\operatorname{pmn}(H)^{n+h})\) and \(O^*(\operatorname{tn}(H)^{n+h})\) algorithms. On the other hand, bounded chromatic number is not enough: [11] rules out \(2^{O(n)}\) algorithms for this case unless \(\cc{ETH}\) fails.

10.0.0.4 The Fine-Grained Dichotomy for Homomorphism.

A natural target-side dream is to find a structural graph parameter \(p\) that describes the plain-exponential frontier for \(\problemabbr{HOM}(\cdot,\mathcal{H})\). Known algorithms place parameters such as bounded treewidth and excluded topological minors on the algorithmic side, while bounded chromatic number is far from sufficient. The weakest useful form of such a dichotomy would separate target families admitting a \(2^{O(n)}\) algorithm from those that require super-single-exponential time. This raises the following question:

Is there a natural graph parameter \(p\) such that bounded \(p(\mathcal{H})\) implies that \(\problemabbr{HOM}(\cdot, \mathcal{H}) \in 2^{O(n)}\) when \(h \le n\), whereas unbounded \(p(\mathcal{H})\) implies that there is no such algorithm under ?

Such fine-grained dichotomies are known in several settings. For example, Bringmann, Fischer, and Künnemann [92] introduced a hardness parameter \(H\) for every \(\exists^{k}\forall\) graph property \(\varphi\), and showed that the baseline \(O(m^{k})\) algorithm for deciding whether a graph on \(m\) vertices satisfies \(\varphi\) can be improved if and only if \(H(\varphi) \leq 2\), assuming the Hyper-Clique Hypothesis. Berkholz, Keppeler, and Schweikardt [93] established a dichotomy for dynamic conjunctive-query answering, showing that it can be computed with linear preprocessing time and constant update time if and only if the homomorphic core of the query is \(q\)-hierarchical. Otherwise, the size of the query result cannot be maintained with sublinear update time. Moreover, Brand, Dell, and Roth [94] established a dichotomy for the problem \(T_{x,y}\), where \((x,y) \in \mathbb{Q}^{2}\) is a fixed rational point. Given a graph \(G\), the task is to evaluate the Tutte polynomial [95] at the point \((x,y)\), that is, to compute \(T_{x,y}(G)=T(G;x,y)\). This problem belongs to \(\cc{FP}\) if and only if \((x-1)(y-1)=1\). For every other point, it is \(\#\P\)-hard and cannot be solved in time \(2^{o(n)}\) under \(\#\cc{ETH}\) [94], [96]–[99]. The same work [94] also established a dichotomy for the problem of counting satisfying assignments of Boolean instances over a constraint language \(\Gamma\). The problem belongs to \(\cc{FP}\) if and only if every relation in \(\Gamma\) is affine over \(\cc{GF}(2)\). Otherwise, it is \(\#\P\)-complete and cannot be solved in time \(2^{o(n)}\) under \(\#\cc{ETH}\) [94], [100].

10.1 Obstruction for Monotone Parameters↩︎

We finish with a simple obstruction that shows that any monotone parameter cannot establish the dichotomy.

Consequently, parameters such as \(\operatorname{tw}(H)\), \(\operatorname{degen}(H)\), \(\Delta(H)\), \(\chi(H)\), and \(\operatorname{cw}(H)\) cannot give the hard direction of the family-level question.

11 SETH Version of the No-Compression Barrier↩︎

For the sake of completeness, we outline the main idea behind the result of Kulikov and Mihajlin [41].

References↩︎

---

1. Neapolis University Pafos. Email: braulov2004@gmail.com↩︎

2. JetBrains Research. Email: buyolitsez1951@gmail.com↩︎

3. JetBrains Research. Email: alexander.s.kulikov@gmail.com↩︎

4. JetBrains Research. Email: ivmihajlin@gmail.com↩︎

5. Technically, some of the upper bounds mentioned above have an additional multiplicative term \(2^h\) that is needed to compute a certificate for the corresponding parameter of \(H\) (such as coloring or decomposition). When \(h=O(n)\) (as in many interesting applications of ), this term is absorbed by \(p(H)^{O(n)}\). For this reason and to make the summary cleaner, we omit the \(2^h\) term.↩︎

6. Recall that \(O^*(\cdot)\) suppresses factors that grow polynomially in the input length. For , such factors are of the form \((n+h)^{O(1)}\).↩︎

7. By an explicit function, we mean a function computable in \(\P^{\NP}\).↩︎

8. An equitable coloring is a proper coloring such that the sizes of any two color classes differ by at most one.↩︎

9. Here, polynomial time means polynomial in the combined size of the input and the output.↩︎

10. This question was raised by Daniel Lokshtanov, personal communication.↩︎