We denote the Prague dimension of $H$ by $\dim(H)$. Note that for two vertices $u=(u_1,\ldots,u_p), v=(v_1,\ldots,v_p)$ of $K_{n}\times \ldots \times K_{n}$, they are adjacent if and only if $u_i\neq v_i$ for every $i\in [p]$. Therefore equivalently we can say that $\dim(H)\leq p$ if we can encode each vertex of $H$ as a sequence of length $p$ so that the vertices are adjacent if and only if their corresponding sequences differ on every coordinate.

Let $H$ be a bipartite graph.

* There exists a family $\cB$ that $\dim(H)$-covers $H^c$.

* If $H^c$ can be $r$-covered, then $\dim(H)\leq r^2+2$.

Let $n=|V(H)|$, $r=\dim(H)$, and let $\mu: V(H) \to [n]^r$ be a mapping whose image induces a copy of $H$ in $r$-fold direct product of $K_n$ with vertex set $[n]$; it exists by the definition of $\dim(H)$.
For $i\in [r], j\in [n]$, let $B_{i,j}$ be the subgraph of $H^c$ induced by these vertices $v\in V(H)$ for which the projection of $\mu(v)$ to the $i$-th coordinate is equal to $j$.
We define $\cB = \{B_{i,j} ~|~ i \in [r], j \in [n] \}$.

Observe that all vertices of $B_{i,j}$ are pairwise non-adjacent in $H$ since for all tuples $\mu(v)$ their $i$-th coordinate is the same.
Therefore $B_{i,j}$ is an induced biclique of $H^c$.

Now let us verify that $\cB$ $r$-covers $H^c$. First consider a vertex $v\in V(H^c)=V(H)$ and let $\mu(v)=(v_1,\ldots,v_p)$.
The vertex $v$ is contained is subgraph $B_{i,v_i}$ for $i\in [r]$, so $v$ is in $r$ bicliques.
So now consider any edge $uv$ of $H^c$, and let $\mu(u)=(u_1,\ldots,u_r)$ and $\mu(v)=(v_1,\ldots,v_r)$.
By the definition of $H^c$, we have that $uv\notin E(H)$ and therefore there exists $i\in [r]$ such that $u_i=v_i$. Thus both $u,v$ are contained in the biclique $B_{i,u_i}$.
This completes the proof.

Let the bipartition classes of $H$ be $X,Y$.
Let $\cB$ be a family of bicliques that $r$-covers $H^c$ and let $B_1,\ldots,B_s$ be the fixed arbitrary ordering of $\cB$.
Define $I=[r]^2\cup \{(0,1),(1,0)\}$, which will be our set of indices. Note that $|I|=r^2+2$.
Let $q = \max(|V(H)|,s+2)$.
We aim to define a mapping $\mu: V(H) \to [q]^{|I|}$ which will define an induced copy of $H$ in $|I|$-fold product of $K_{q}$ with vertex set $[q]$ (here it will be convenient not to assume that the cliques have $|V(H)|$ vertices).

Fix a pair $(i,j) \in [r]^2$ and consider $u \in X$ (resp. $v \in Y$).
Let $u$ (resp. $v$) be covered by $r' \leq r$ bicliques in $\cB$.
We define

\[
\mu_{i,j}(u) = \begin{cases}
\ell & \text{ if $i \leq r'$ and $B_\ell$ is the}\\
& \text{$i$-th biclique covering $u$}\\
s+1 & \text{ if } i > r',
\end{cases}
\quad
\mu_{i,j}(v) = \begin{cases}
\ell & \text{ if $j \leq r'$ and $B_\ell$ is the}\\
& \text{$j$-th biclique covering $v$}\\
s+2 & \text{ if } i > r'.
\end{cases}
\]

Moreover, we define $\mu_{1,0}: V(H) \to [q]$ so that each vertex receives distinct value (this is possible as $q \geq |V(H)|$),
and $\mu_{0,1}: V(H) \to [q]$ that maps all vertices from $X$ to $1$ and all vertices from $Y$ to $2$.

Now, $\mu : V(H) \to [q]^{I}$ is defined in a way that the projection of $\mu$ on the coordinate $(i,j) \in I$ is precisely $\mu_{i,j}$.
This completes the definition of $\mu$.

Let us verify that the image $\mu(V(H))$ induces a copy of $H$.
By the definition of $\mu_{1,0}$, the mapping is injective and by the definition of $\mu_{0,1}$ for $u,v$ from the same bipartition class we have that $\mu(u)$ and $\mu(v)$ are non-adjacent in $K_{q} \times \ldots \times K_{q}$ (we remark that $\mu_{1,0}$ is not needed if all vertices have pairwise distinct neighborhoods).

Consider $uv\in E(H)$ with $u\in X$, $v\in Y$.
This means that $uv\notin E(H^c)$ and thus there is no biclique that contains both $u,v$.
Therefore $\mu(u)$ and $\mu(v)$ differ on every coordinate and hence are adjacent.

So now consider $uv\notin E(H)$ with $u\in X$, $v\in Y$. Since $uv\in E(H^c)$, there must be at least one biclique $B_\ell\in \cB$ that contains $uv$.
Therefore for some pair $(i,j)$ we defined $\mu_{i,j}(u)=\mu_{i,j}(v)=\ell$, so $\mu(u)$ is non-adjacent to $\mu(v)$. This completes the proof.

We conclude this section with the following bound.

The following bounds hold.

* If $H$ is not bipartite, then the support rank of the adjacency matrix of $H$ is at most $(\dim(H^*)+1)^{\dim(H^*)}$.

* If $H$ is bipartite, then the support rank of the bi-adjacency matrix of $H$ is at most

The first statement is an immediate corollary of <ref> and <ref> (1).
We point out that <ref> holds, if we consider covering $H^c$ instead of $(H^*)^c$ and the bi-adjacency matrix of $H$ instead the adjacency matrix. Therefore, the second statement follows as well.

§ CONCLUSION

We conclude the paper by discussing graphs $H$ that are potentially missed by Theorem <ref> and Theorem <ref>, and pointing out some directions for further research.

Non-projective graphs.
The combination of Corollary <ref> and  Theorem <ref> gives strong evidence that if $H$ is projective, then indeed $\mimsup(H)$ is the “right” parameter to study in the context of <ref>. So let us consider the case that $H$ is  not projective.

There are two questions to be asked: (i) what graphs are non-projective non-bipartite cores, and (ii) whether we can show some interesting lower bound for H in such a case.

Concerning question (i), it turns out that the only way of constructing non-projective graphs that we know is by using direct products.
Indeed, for $H = H_1 \times H_2$, a function that maps each $((x_1,x_2),(y_1,y_2)) \in V(H^2)$ to $(x_1,y_2)$, is a homomorphism from $H^2$ to $H$, but not a projection. Actually, it is conjectured that all non-projective graphs are constructed in such a way [50, 63], i.e., every non-projective non-bipartite core is not prime.
Recall that direct products are handled by Theorem <ref>, and the parameter considered there is actually the maximum value of $\mimsup(H')$, where $H'$ iterates over factors of the prime decomposition of $H$.

Concerning question (ii), Larose [49] defined a subclass of projective graphs called strongly projective graphs (we do not include the definition as it is quite technical and not so relevant to our work). It turns out that we do not know any graphs that are projective but not strongly projective and it is conjectured that these two classes actually coincide [49, 63]. This conjecture, combined with the one mentioned in the previous paragraph and <ref>, yields that every non-bipartite core graph admits a (unique) prime factorization into strongly projective graphs.

Using the methods introduced in [63], it is possible to lift Theorem <ref> to such a setting, and the constant appearing in the lower bound becomes again $\mimsup(H')$ defined as above. As the main focus of the paper is how asymptotic rank parameters can be used to upper-bound the complexity of an algorithm for finding graph homomorphisms, we skip discussing this generalization in detail and refer the reader to [63].

Directions for further research.
An obvious open problem is to fully resolve <ref>.
As discussed, to achieve this goal we only lack a fast algorithm that computes representative sets for partial solutions to H. We have shown in Lemma <ref> that such sets can be found non-trivially fast and hope it can be further improved to settle <ref>.
A far more ambitious (and probably currently out of reach) goal is to provide a (more) fine-grained version of the Courcelle's theorem for deciding any graph property definable in the monadic second-order logic. While being homomorphic to a given graph $H$ is of course only a very special sort of such a property, we find our progress on <ref> encouraging in this respect and hope that eventually similar connections between the complexity of more general computational problems and asymptotic rank parameters can be made as well.
In particular, we believe that $\mimsup$ (or a similar parameter that tracks the asymptotic behavior under appropriate products) is likely to determine the limit of dynamic programming approaches in other settings as well, especially those determined by various graph width parameters.

Another suggested direction of research is purely combinatorial/algebraic: we expect that $\mimsup$ is an interesting parameter for further study in its own right. Similar asymptotic parameters have been defined for tensors (such as asymptotic tensor rank, which can be used to define the matrix multiplication constant $\omega$) but the interesting asymptotic aspects disappear for the special case of matrices. We give some suggestions below.

* What type of values can $\mimsup(H)$ take given a matrix $H$? Can it take non-integer values? Similar questions have recently been investigated for asymptotic tensor parameters, see e.g. [4, 7].

* What is the value of $\mimsup$ for a $n\times n$ random matrix, where each entry of the matrix gets sampled independently to be $1$ with probability $p$ and to be $0$ with probability $1-p$?

* We showed that $\hg$ and the support rank are not functionally equivalent. Is $\mimsup$ functionally equivalent to either $\hg$ or the support rank?

The second question may shed some light on the third.

Our own progress on the relation between $\hg$ and $\mimsup$ lifted basic arguments from (multi-color) Ramsey numbers.
Let $R(t;\ell)$ denote the smallest integer $r$ for which every $\ell$-coloring of $K_r$, the complete graph on $r$ vertices, has a monochromatic $K_t$. Ignoring smaller order terms, for $\ell\geq 3$, the best upper bound $\ell^{\ell t}$ comes from the `neighbourhood chasing argument' similar to the one we applied in <ref>. On the lower bound side it is difficult to get beyond bounds of the form $c^{\ell t}$, for $c$ constant (see [15] for further discussion). It remains open whether $g(t)=\limsup_{\ell \to \infty} R(t;\ell)^{1/\ell}$ is finite for all constant $t$. In particular, the state-of-the-art from this line of work may give some improvement on our separation but is unlikely to (directly) yield an answer to the problem of whether $\hg$ and $\mimsup$ are functionally equivalent or not.

Acknowledgement. The authors are grateful to Koblich for enlightening discussions about communication complexity.

[1]
Noga Alon, Igor Balla, Lior Gishboliner, Adva Mond, and Frank Mousset.
The minrank of random graphs over arbitrary fields.
Israel Journal of Mathematics, 235:63–77, 2020.

[2]
Noga Alon and Eyal Lubetzky.
The shannon capacity of a graph and the independence numbers of its
IEEE Trans. Inf. Theory, 52(5):2172–2176, 2006.

[3]
Srinivasan Arunachalam, Péter Vrana, and Jeroen Zuiddam.
The asymptotic induced matching number of hypergraphs: Balanced
binary strings.
The Electronic Journal of Combinatorics, 27(3), 2020.

[4]
Andreas Blatter, Jan Draisma, and Filip Rupniewski.
Countably many asymptotic tensor ranks.
arXiv:2212.12219, 2022.

[5]
Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof.
Deterministic single exponential time algorithms for connectivity
problems parameterized by treewidth.
Inf. Comput., 243:86–111, 2015.

[6]
Glencora Borradaile and Hung Le.
Optimal dynamic program for $r$-domination problems over tree
In Jiong Guo and Danny Hermelin, editors, 11th International
Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26,
2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 8:1–8:23. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2016.

[7]
Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, and Jeroen Zuiddam.
Discreteness of asymptotic tensor ranks.
arXiv:2306.01718, 2023.

[8]
Csilla Bujtás, Akbar Davoodi, Ervin Győri, and Zsolt Tuza.
Clique coverings and claw-free graphs.
European Journal of Combinatorics, 88:103114, 2020.
Selected papers of EuroComb17.

[9]
Andrei A. Bulatov and Amirhossein Kazeminia.
Complexity classification of counting graph homomorphisms modulo a
prime number.
In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th
Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20
- 24, 2022, pages 1024–1037. ACM, 2022.

[10]
Peter Bürgisser, Michael Clausen, and Amin Shokrollahi.
Algebraic complexity theory.
In Grundlehren der mathematischen Wissenschaften, 1997.

[11]
Jin-Yi Cai and Ashwin Maran.
The complexity of counting planar graph homomorphisms of domain size
In Barna Saha and Rocco A. Servedio, editors, Proceedings of the
55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL,
USA, June 20-23, 2023, pages 1285–1297. ACM, 2023.

[12]
Airlie Chapman and Mehran Mesbahi.
On strong structural controllability of networked systems: A
constrained matching approach.
In 2013 American Control Conference, pages 6126–6131, 2013.

[13]
Prasad Chaugule, Nutan Limaye, and Aditya Varre.
Variants of homomorphism polynomials complete for algebraic
complexity classes.
ACM Trans. Comput. Theory, 13(4):21:1–21:26, 2021.

[14]
Rajesh Chitnis, László Egri, and Dániel Marx.
List h-coloring a graph by removing few vertices.
Algorithmica, 78(1):110–146, 2017.

[15]
David Conlon and Asaf Ferber.
Lower bounds for multicolor ramsey numbers.
Advances in Mathematics, 378:107528, 2021.

[16]
Bruno Courcelle.
The monadic second-order logic of graphs. i. recognizable sets of
finite graphs.
Inf. Comput., 85(1):12–75, 1990.

[17]
Radu Curticapean, Holger Dell, and Dániel Marx.
Homomorphisms are a good basis for counting small subgraphs.
In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of
Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages
210–223. ACM, 2017.

[18]
Radu Curticapean, Nathan Lindzey, and Jesper Nederlof.
A tight lower bound for counting Hamiltonian cycles via matrix
In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA,
USA, January 7-10, 2018, pages 1080–1099. SIAM, 2018.

[19]
Radu Curticapean and Dániel Marx.
Tight conditional lower bounds for counting perfect matchings on
graphs of bounded treewidth, cliquewidth, and genus.
In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh
Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington,
VA, USA, January 10-12, 2016, pages 1650–1669. SIAM, 2016.

[20]
Marek Cygan, Stefan Kratsch, and Jesper Nederlof.
Fast hamiltonicity checking via bases of perfect matchings.
J. ACM, 65(3):12:1–12:46, 2018.

[21]
Ronald de Wolf.
Nondeterministic quantum query and communication complexities.
SIAM Journal on Computing, 32(3):681–699, 2003.

[22]
Jinquan Dong and Yanpei Liu.
On the decomposition of graphs into complete bipartite graphs.
Graphs Comb., 23(3):255–262, 2007.

[23]
László Egri, Andrei A. Krokhin, Benoît Larose, and Pascal
The complexity of the list homomorphism problem for graphs.
In Jean-Yves Marion and Thomas Schwentick, editors, 27th
International Symposium on Theoretical Aspects of Computer Science, STACS
2010, March 4-6, 2010, Nancy, France, volume 5 of LIPIcs, pages
335–346. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010.

[24]
László Egri, Dániel Marx, and Pawel Rzazewski.
Finding list homomorphisms from bounded-treewidth graphs to reflexive
graphs: a complete complexity characterization.
In Rolf Niedermeier and Brigitte Vallée, editors, 35th
Symposium on Theoretical Aspects of Computer Science, STACS 2018, February
28 to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages
27:1–27:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.

[25]
Paul Erdős and George Szekeres.
A combinatorial problem in geometry.
Compositio mathematica, 2:463–470, 1935.

[26]
Baris Can Esmer, Jacob Focke, Dániel Marx, and Paweł Rzążewski.
List homomorphisms by deleting edges and vertices: tight complexity
bounds for bounded-treewidth graphs.
CoRR, abs/2210.10677, 2022.

[27]
Tomás Feder, Pavol Hell, and Jing Huang.
List homomorphisms and circular arc graphs.
Comb., 19(4):487–505, 1999.

[28]
M. Fekete.
Über die Verteilung der Wurzeln bei gewissen algebraischen
Gleichungen mit ganzzahligen Koeffizienten.
Mathematische Zeitschrift, 17(1):228–249, December 1923.

[29]
Peter C. Fishburn and Peter L. Hammer.
Bipartite dimensions and bipartite degrees of graphs.
Discrete Mathematics, 160(1):127–148, 1996.

[30]
Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S.
Sankar, Philipp Schepper, and Philip Wellnitz.
Tight complexity bounds for counting generalized dominating sets in
bounded-treewidth graphs.
In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings
of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023,
Florence, Italy, January 22-25, 2023, pages 3664–3683. SIAM, 2023.

[31]
Jacob Focke, Dániel Marx, and Pawel Rzazewski.
Counting list homomorphisms from graphs of bounded treewidth: tight
complexity bounds.
In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings
of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual
Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 431–458.
SIAM, 2022.

[32]
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh.
Efficient computation of representative families with applications in
parameterized and exact algorithms.
J. ACM, 63(4):29:1–29:60, 2016.

[33]
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh.
Representative families of product families.
ACM Trans. Algorithms, 13(3):36:1–36:29, 2017.

[34]
Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, and Kirill
The fine-grained complexity of graph homomorphism parameterized by
In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff,
editors, 49th International Colloquium on Automata, Languages, and
Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 66:1–66:20. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2022.

[35]
Chris Godsil.
Problems in algebraic combinatorics.
Electr. J. Comb., 2, 01 1995.

[36]
Alexander Golovnev, Oded Regev, and Omri Weinstein.
The minrank of random graphs.
IEEE Transactions on Information Theory, 64(11):6990–6995,

[37]
Carla Groenland, Isja Mannens, Jesper Nederlof, and Krisztina Szilágyi.
Tight bounds for counting colorings and connected edge sets
parameterized by cutwidth.
In Petra Berenbrink and Benjamin Monmege, editors, 39th
International Symposium on Theoretical Aspects of Computer Science, STACS
2022, March 15-18, 2022, Marseille, France (Virtual Conference), volume 219
of LIPIcs, pages 36:1–36:20. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2022.

[38]
Richard H. Hammack, Wilfried Imrich, and Sandi Klavžar.
Handbook of product graphs.
CRC press, 2011.

[39]
Ishay Haviv.
On minrank and forbidden subgraphs.
ACM Transactions on Computation Theory, 11(4), 2019.

[40]
Pavol Hell and Jaroslav Nešetřil.
The core of a graph.
Discrete Mathematics, 109(1-3):117–126, 1992.

[41]
Pavol Hell and Jaroslav Nešetřil.
On the complexity of H-coloring.
J. Comb. Theory, Ser. B, 48(1):92–110, 1990.

[42]
Lars Jaffke and Bart M. P. Jansen.
Fine-grained parameterized complexity analysis of graph coloring
Discret. Appl. Math., 327:33–46, 2023.

[43]
Bart M. P. Jansen and Jesper Nederlof.
Computing the chromatic number using graph decompositions via matrix
Theor. Comput. Sci., 795:520–539, 2019.

[44]
Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos.
Structural parameters, tight bounds, and approximation for $(k,
Discret. Appl. Math., 264:90–117, 2019.

[45]
Kolja Knauer and Torsten Ueckerdt.
Three ways to cover a graph.
Discrete Mathematics, 339(2):745–758, 2016.

[46]
Tomasz Kociumaka and Marcin Pilipczuk.
Deleting vertices to graphs of bounded genus.
Algorithmica, 81(9):3655–3691, 2019.

[47]
Stefan Kratsch and Magnus Wahlström.
Representative sets and irrelevant vertices: New tools for
J. ACM, 67(3):16:1–16:50, 2020.

[48]
Michael Lampis.
Finer tight bounds for coloring on clique-width.
SIAM J. Discret. Math., 34(3):1538–1558, 2020.

[49]
Benoit Larose.
Families of strongly projective graphs.
Discussiones Mathematicae Graph Theory, 22:271–292, 2002.

[50]
Benoit Larose and Claude Tardif.
Strongly rigid graphs and projectivity.
Multiple-Valued Logic, 7:339–361, 2001.

[51]
Daniel Lokshtanov, Dániel Marx, and Saket Saurabh.
Lower bounds based on the Exponential Time Hypothesis.
Bulletin of the EATCS, 105:41–72, 2011.

[52]
Daniel Lokshtanov, Dániel Marx, and Saket Saurabh.
Known algorithms on graphs of bounded treewidth are probably optimal.
ACM Trans. Algorithms, 14(2):13:1–13:30, 2018.

[53]
Tomasz Łuczak and Jaroslav Nešetřil.
Note on projective graphs.
Journal of Graph Theory, 47(2):81–86, 2004.

[54]
Dániel Marx, Govind S. Sankar, and Philipp Schepper.
Degrees and gaps: Tight complexity results of general factor problems
parameterized by treewidth and cutwidth.
In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming,
ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference),
volume 198 of LIPIcs, pages 95:1–95:20. Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2021.

[55]
Dániel Marx, Govind S. Sankar, and Philipp Schepper.
Anti-Factor Is FPT Parameterized by Treewidth and List Size (But
Counting Is Hard).
In Holger Dell and Jesper Nederlof, editors, 17th International
Symposium on Parameterized and Exact Computation (IPEC 2022), volume 249 of
Leibniz International Proceedings in Informatics (LIPIcs), pages
22:1–22:23, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum
für Informatik.

[56]
Ralph McKenzie.
Cardinal multiplication of structures with a reflexive relation.
Fundamenta Mathematicae, 70(1):59–101, 1971.

[57]
Burkhard Monien.
The complexity of determining paths of length k.
In Manfred Nagl and Jürgen Perl, editors, Proceedings of
the WG '83, International Workshop on Graphtheoretic Concepts in Computer
Science, June 16-18, 1983, Haus Ohrbeck, near Osnabrück, Germany,
pages 241–251. Universitätsverlag Rudolf Trauner, Linz, 1983.

[58]
Jesper Nederlof.
Algorithms for np-hard problems via rank-related parameters of
In Fedor V. Fomin, Stefan Kratsch, and Erik Jan van Leeuwen, editors,
Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L.
Bodlaender on the Occasion of His 60th Birthday, volume 12160 of Lecture Notes in Computer Science, pages 145–164. Springer, 2020.

[59]
Jesper Nederlof.
Bipartite TSP in o(1.9999n) time, assuming
quadratic time matrix multiplication.
In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam
Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM
SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA,
June 22-26, 2020, pages 40–53. ACM, 2020.

[60]
J. Nešetřil and A. Pultr.
A dushnik - miller type dimension of graphs and its complexity.
In Marek Karpiński, editor, Fundamentals of Computation
Theory, pages 482–493, Berlin, Heidelberg, 1977. Springer Berlin

[61]
Jaroslav NeĹˇetĹ™il and VojtÄ›ch RĹŤdl.
A simple proof of the galvin-ramsey property of the class of all
finite graphs and a dimension of a graph.
Discrete Mathematics, 23(1):49–55, 1978.

[62]
Karolina Okrasa, Marta Piecyk, and Pawel Rzazewski.
Full complexity classification of the list homomorphism problem for
bounded-treewidth graphs.
In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors,
28th Annual European Symposium on Algorithms, ESA 2020, September 7-9,
2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages
74:1–74:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

[63]
Karolina Okrasa and Pawel Rzążewski.
Fine-grained complexity of the graph homomorphism problem for
bounded-treewidth graphs.
SIAM J. Comput., 50(2):487–508, 2021.

[64]
D.D. Olesky, Michael Tsatsomeros, and P. van den Driessche.
Qualitative controllability and uncontrollability by a single entry.
Linear Algebra and its Applications, 187:183–194, 1993.

[65]
Marta Piecyk and Pawel Rzazewski.
Fine-grained complexity of the list homomorphism problem: Feedback
vertex set and cutwidth.
In Markus Bläser and Benjamin Monmege, editors, 38th
International Symposium on Theoretical Aspects of Computer Science, STACS
2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference),
volume 187 of LIPIcs, pages 56:1–56:17. Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2021.

[66]
Michał Pilipczuk.
Problems parameterized by treewidth tractable in single exponential
time: A logical approach.
In MFCS 2011, volume 6907, pages 520–531. Springer, 2011.

[67]
Marc Roth and Philip Wellnitz.
Counting and finding homomorphisms is universal for parameterized
complexity theory.
In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM
Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA,
January 5-8, 2020, pages 2161–2180. SIAM, 2020.

[68]
Maguy Trefois and Jean-Charles Delvenne.
Zero forcing number, constrained matchings and strong structural
Linear Algebra and its Applications, 484:199–218, 2015.

[69]
Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith.
Dynamic programming on tree decompositions using generalised fast
subset convolution.
In Amos Fiat and Peter Sanders, editors, Algorithms - ESA
2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9,
2009. Proceedings, volume 5757 of Lecture Notes in Computer Science,
pages 566–577. Springer, 2009.

[70]
Virginia Vassilevska Williams.
Multiplying matrices faster than Coppersmith-Winograd.
In Howard J. Karloff and Toniann Pitassi, editors, Proceedings
of the 44th Symposium on Theory of Computing Conference, STOC 2012, New
York, NY, USA, May 19 - 22, 2012, pages 887–898. ACM, 2012.