We study the complexity of a class of promise graph homomorphism problems. For a fixed graph H, the H-colouring problem is to decide whether a given graph has a homomorphism to H. By a result of Hell and Nešetřil, this problem is NP-hard for any non-bipartite loop-less graph H. Brakensiek and Guruswami [SODA 2018] conjectured the hardness extends to promise graph homomorphism problems as follows: fix a pair of non-bipartite loop-less graphs G, H such that there is a homomorphism from G to H, it is NP-hard to distinguish between graphs that are G-colourable and those that are not H-colourable. We confirm this conjecture in the cases when both G and H are 4-colourable. This is a common generalisation of previous results of Khanna, Linial, and Safra [Comb. 20(3): 393-415 (2000)] and of Krokhin and Opršal [FOCS 2019]. The result is obtained by combining the algebraic approach to promise constraint satisfaction with methods of topological combinatorics and equivariant obstruction theory.

A linearly ordered (LO) $k$-colouring of a hypergraph is a colouring of its vertices with colours $1, \dots, k$ such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO $k$-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the `linearly ordered chromatic number' of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO $3$-colourable, and the case that it is not even LO $4$-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).

Abstract We present an algorithm that, given finite diagrams of simplicial sets X, A, Y, i.e., functors $${\mathcal {I}}^\textrm{op}\rightarrow {\textsf {s}} {\textsf {Set}}$$ I op → s Set , such that (X, A) is a cellular pair, $$\dim X\le 2\cdot {\text {conn}}Y$$ dim X ≤ 2 · conn Y , $${\text {conn}}Y\ge 1$$ conn Y ≥ 1 , computes the set $$[X,Y]^A$$ [ X , Y ] A of homotopy classes of maps of diagrams $$\ell :X\rightarrow Y$$ ℓ : X → Y extending a given $$f:A\rightarrow Y$$ f : A → Y . For fixed $$n=\dim X$$ n = dim X , the running time of the algorithm is polynomial. When the stability condition is dropped, the problem is known to be undecidable. Using Elmendorf’s theorem, we deduce an algorithm that, given finite simplicial sets X, A, Y with an action of a finite group G, computes the set $$[X,Y]^A_G$$ [ X , Y ] G A of homotopy classes of equivariant maps $$\ell :X\rightarrow Y$$ ℓ : X → Y extending a given equivariant map $$f:A\rightarrow Y$$ f : A → Y under the stability assumption $$\dim X^H\le 2\cdot {\text {conn}}Y^H$$ dim X H ≤ 2 · conn Y H and $${\text {conn}}Y^H\ge 1$$ conn Y H ≥ 1 , for all subgroups $$H\le G$$ H ≤ G . Again, for fixed $$n=\dim X$$ n = dim X , the algorithm runs in polynomial time. We further apply our results to Tverberg-type problem in computational topology: Given a k-dimensional simplicial complex K, is there a map $$K\rightarrow {\mathbb {R}}^d$$ K → R d without r-tuple intersection points? In the metastable range of dimensions, $$rd\ge (r+1) k+3$$ r d ≥ ( r + 1 ) k + 3 , the problem is shown algorithmically decidable in polynomial ti

We consider the following decision problem EMBEDk→d in computational topology (where k ≤ d are fixed positive integers): Given a finite simplicial complex K of dimension k, does there exist a (piecewise-linear) embedding of K into ℝd? The special case EMBED1→2 is graph planarity, which is decidable in linear time, as shown by Hopcroft and Tarjan. In higher dimensions, EMBED2→3 and EMBED3→3 are known to be decidable (as well as NP-hard), and recent results of Čadek et al. in computational homotopy theory, in combination with the classical Haefliger–Weber theorem in geometric topology, imply that EMBEDk→d can be solved in polynomial time for any fixed pair (k, d) of dimensions in the so-called metastable range . Here, by contrast, we prove that EMBEDk→d is algorithmically undecidable for almost all pairs of dimensions outside the metastable range, namely for . This almost completely resolves the decidability vs. undecidability of EMBEDk→d in higher dimensions and establishes a sharp dichotomy between polynomial-time solvability and undecidability. Our result complements (and in a wide range of dimensions strengthens) earlier results of Matoušek, Tancer, and the second author, who showed that EMBEDk→d is undecidable for 4 ≤ k ϵ {d – 1, d}, and NP-hard for all remaining pairs (k, d) outside the metastable range and satisfying d ≥ 4.

A central problem of algebraic topology is to understand the homotopy groups πd(X) of a topological space X. For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group π1(Χ) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(Χ) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2. However, these algorithms come with a caveat: They compute the isomorphism type of πd(Χ), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(Χ). Converting elements of this abstract group into explicit geometric maps from the d-dimensional sphere Sd to Χ has been an important open question in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected simplicial complex Χ, computes πd(Χ) and represents its elements as simplicial maps from a suitable triangulation of the d-sphere Sd to Χ. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of Χ. Moreover, we prove that this is optimal: For every fixed d ≥ 2, we construct a family of simply connected simplicial complexes Χ such that for any simplicial map representing a generator of πd(Χ), the size of the triangulation of Sd on which the map is defined is exponential in size(X).