The concept of well group in a special but important case captures homological properties of the zero set of a continuous map $$f:K\rightarrow {\mathbb {R}}^n$$ f : K → R n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within $$L_\infty $$ L ∞ distance r from f for a given $$r>0$$ r > 0 . The main drawback of the approach is that the computability of well groups was shown only when $$\dim K=n$$ dim K = n or $$n=1$$ n = 1 . Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of $${\mathbb {R}}^n$$ R n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and $$\dim K<2n-2$$ dim K < 2 n - 2 , our approximation of the $$(\dim \ K-n)$$ ( dim K - n ) th well group is exact. For the second part, we find examples of maps $$f,f':K\rightarrow {\mathbb {R}}^n$$ f , f ′ : K → R n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status.

The concept of well group in a special but important case captures homological properties of the zero set of a continuous map f from K to R^n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within L_infty distance r from f for a given r > 0. The main drawback of the approach is that the computability of well groups was shown only when dim K = n or n = 1. Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K < 2n-2, our approximation of the (dim K-n)th well group is exact. For the second part, we find examples of maps f, f' from K to R^n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status.

We study the problem of robust satisfiability of systems of nonlinear equations, namely, whether for a given continuous function f : K → Rn on a finite simplicial complex K and α>0, it holds that each function g : K → Rn such that ║ g−f ║∞ ≤ α , has a root in K . Via a reduction to the extension problem of maps into a sphere, we particularly show that this problem is decidable in polynomial time for every fixed n , assuming dim K ≤ 2 n −3. This is a substantial extension of previous computational applications of topological degree and related concepts in numerical and interval analysis. Via a reverse reduction, we prove that the problem is undecidable when dim K ≥ 2 n −2, where the threshold comes from the stable range in homotopy theory. For the lucidity of our exposition, we focus on the setting when f is simplexwise linear. Such functions can approximate general continuous functions, and thus we get approximation schemes and undecidability of the robust satisfiability in other possible settings.

We study the problem of robust satisfiability of systems of nonlinear equations, namely, whether for a given continuous function f : K → R n on a finite simplicial complex K and α > 0, it holds that each function g : K → R n such that gf ∞ ≤ α, has a root in K. Via a reduction to the extension problem of maps into a sphere, we show that this problem is decidable if dim K ≤ 2n -3.This is a substantial extension of previous computational applications of topological degree and related concepts in numerical and interval analysis.Via a reverse reduction we prove that the problem is undecidable when dim K ≥ 2n -2, where the threshold comes from the stable range in homotopy theory.For the lucidity of our exposition, we focus on the setting when f is piecewise linear.Such functions can approximate general continuous functions, and thus we get approximation schemes and undecidability of the robust satisfiability in other possible settings.

Given topological spaces X , Y , a fundamental problem of algebraic topology is understanding the structure of all continuous maps X → Y . We consider a computational version, where X , Y are given as finite simplicial complexes, and the goal is to compute [ X , Y ], that is, all homotopy classes of such maps. We solve this problem in the stable range , where for some d ≥ 2, we have dim X ≤ 2 d −2 and Y is ( d -1)- connected ; in particular, Y can be the d -dimensional sphere S d . The algorithm combines classical tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and simplicial sets) with algorithmic tools from effective algebraic topology (locally effective simplicial sets and objects with effective homology). In contrast, [ X , Y ] is known to be uncomputable for general X , Y , since for X = S 1 it includes a well known undecidable problem: testing triviality of the fundamental group of Y . In follow-up papers, the algorithm is shown to run in polynomial time for d fixed, and extended to other problems, such as the extension problem , where we are given a subspace A ⊂ X and a map A → Y and ask whether it extends to a map X → Y , or computing the ℤ 2 - index —everything in the stable range. Outside the stable range, the extension problem is undecidable.

For several computational problems in homotopy theory, we obtain algorithms with running time polynomial in the input size. In particular, for every fixed $k\ge 2$, there is a polynomial-time algorithm that, for a $1$-connected topological space $X$ given as a finite simplicial complex, or more generally, as a simplicial set with polynomial-time homology, computes the $k$th homotopy group $\pi_k(X)$, as well as the first $k$ stages of a Postnikov system of $X$. Combined with results of an earlier paper, this yields a polynomial-time computation of $[X,Y]$, i.e., all homotopy classes of continuous mappings $X\to Y$, under the assumption that $Y$ is $(k-1)$-connected and $\dim X\le 2k-2$. We also obtain a polynomial-time solution of the extension problem, where the input consists of finite simplicial complexes $X$, $Y$, where $Y$ is $(k-1)$-connected and $\dim X\le 2k-1$, plus a subspace $A\subseteq X$ and a (simplicial) map $f:A\to Y$, and the question is the extendability of $f$ to all of $X$. The algorithms are based on the notion of a simplicial set with polynomial-time homology, which is an enhancement of the notion of a simplicial set with effective homology developed earlier by Sergeraert and his coworkers. Our polynomial-time algorithms are obtained by showing that simplicial sets with polynomial-time homology are closed under various operations, most notably Cartesian products, twisted Cartesian products, and classifying space. One of the key components is also polynomial-time homology for the Eilenberg--MacLane space $K(\mathbb{Z},1)$, provided in another recent paper by Krčál, Matoušek, and Sergeraert. (A corrected file is attached.)

A seminal result of Reed et al. [15] in 1996 states that the Erdős-Pósa property holds for directed cycles, i.e. for every integer n there is an integer t such that every directed graph G has n pairwise vertex disjoint directed cycles or contains a set T ⊆ V (G) of at most t vertices such that G -T contains no directed cycle.In this paper, we consider the Erdős-Pósa property for directed cycles through a vertex in a given vertex set S, i.e. the question if for every integer n there is an integer t such that if G is a directed graph G and S is a set of vertices then G has n pairwise vertex disjoint directed cycles each containing a vertex of S or contains a set T of at most t vertices such that G-T contains no such directed cycle.For undirected graphs, this property holds for cycles through a vertex in a vertex set S (see Kakimura, Kawarabayashi and Marx [9], and Pontecorvi and Wollan [12]).In this paper, we show the following: The Erdős-Pósa does hold for half-integral packings of directed cycles each containing a vertex from S, i.e.where every vertex of the graph is contained in at most 2 cycles.On the other hand, an example shows that the Erdős-Pósa property does not hold without this relaxation.

We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of computational complexity.

We present an algorithm for computing [X, Y], i.e., all homotopy classes of continuous maps X → Y, where X, Y are topological spaces given as finite simplicial complexes, Y is (d − 1)-connected for some d ≥ 2 (for example, Y can be the d-dimensional sphere Sd), and dim X ≤ 2d − 2. These conditions on X, Y guarantee that [X, Y] has a natural structure of a finitely generated Abelian group, and the algorithm finds generators and relations for it. We combine several tools and ideas from homotopy theory (such as Postnikov systems, simplicial sets, and obstruction theory) with algorithmic tools from effective algebraic topology (objects with effective homology). We hope that a further extension of the methods developed here will yield an algorithm for computing, in some cases of interest, the ℤ2-index, which is a quantity playing a prominent role in Borsuk–Ulam style applications of topology in combinatorics and geometry, e.g., in topological lower bounds for the chromatic number of a graph. In a certain range of dimensions, deciding the embeddability of a simplicial complex into ℝd also amounts to a ℤ2-index computation. This is the main motivation of our work. We believe that investigating the computational complexity of questions in homotopy theory and similar areas presents a fascinating research area, and we hope that our work may help bridge the cultural gap between algebraic topology and theoretical computer science.