Consider the following parameterized counting variation of the classic subset sum problem, which arises notably in the context of higher homotopy groups of topological spaces. Let v ∈ Q d be a rational vector, ( T 1 , T 2 … , T m ) a list of d × d rational matrices, S ∈ Q h × d a rational matrix not necessarily square and k a parameter. The goal is to compute the number of ways one can choose k matrices T i 1 , T i 2 , … , T i k from the list such that S T i k ⋯ T i 1 v = 0 ∈ Q h . In this paper, we show that this problem is # W [ 2 ] -hard for parameter k . As a consequence, computing the k -th homotopy group of a d -dimensional 1-connected topological space for d > 3 is # W [ 2 ] -hard for parameter k . We also discuss a decision version of the problem and its several modifications for which we show W [ 1 ] / W [ 2 ] -hardness. This is in contrast to the parameterized k -sum problem, which is only W [ 1 ] -hard (Abboud-Lewi-Williams, ESA'14). In addition, we show that the decision version of the problem without parameter is an undecidable problem, and we give a fixed-parameter tractable algorithm for matrices of bounded size over finite fields, parameterized by the matrix dimensions and the order of the field.

We extend the algebraic techniques of Brand and Pratt (ICALP'21) for deterministic detection of k-multilinear monomials in a given polynomial with non-negative coefficients to the more general situation of detecting colored k-multilinear monomials that satisfy additional constraints on the multiplicities of the colors appearing in them. Our techniques can be viewed as a characteristic-zero generalization of the algebraic tools developed by Guillemot and Sikora (MFCS'10) and Björklund, Kaski and Kowalik (STACS'13) As applications, we recover the state-of-the-art deterministic algorithms for the Graph Motif problem due to Pinter, Schachnai and Zehavi (MFCS'14), and give new deterministic algorithms for generalizations of certain questions on colored directed spanning trees or bipartite planar matchings running in deterministic time O^∗(4^k), studied originally by Gutin, Reidl, Wahlström and Zehavi (J. Comp. Sys. Sci. 95, '18). Finally, we give improved randomized algorithms for intersecting three and four matroids of rank k in characteristic zero, improving the record bounds of Brand and Pratt (ICALP'21) from O^∗(64^k) and O^∗(256^k), respectively, to O^∗(4^k).

Abstract. The PL geometric category of a polyhedron [Formula: see text], denoted [Formula: see text], is a combinatorial notion which provides a natural upper bound for the Lusternik–Schnirelmann category, and it is defined as the minimum number of PL collapsible subpolyhedra of [Formula: see text] that cover [Formula: see text]. In dimension 2 the PL geometric category is at most 3. It is easy to characterize/recognize 2-polyhedra [Formula: see text] with [Formula: see text]. Borghini provided a partial characterization of 2-polyhedra with [Formula: see text]. We complement his result by showing that it is NP-hard to decide whether [Formula: see text]. Therefore, we should not expect much more than a partial characterization, at least in an algorithmic sense. Our reduction is based on the observation that 2-dimensional polyhedra [Formula: see text] admitting a shellable subdivision satisfy [Formula: see text] and a (nontrivial) modification of the reduction of Goaoc, Paták, Patáková, Tancer and Wagner showing that shellability of 2-complexes is NP-hard.

We say that a pure simplicial complex ${\mathbf K}$ of dimension $d$ satisfies the removal-collapsibility condition if ${\mathbf K}$ is either empty or ${\mathbf K}$ becomes collapsible after removing $\tilde \beta_d ({\mathbf K}; {\mathbb Z}_2)$ facets, where $\tilde \beta_d ({\mathbf K}; {\mathbb Z}_2)$ denotes the $d$th reduced Betti number. In this paper, we show that if the link of each face of a pure simplicial complex ${\mathbf K}$ (including the link of the empty face which is the whole ${\mathbf K}$) satisfies the removal-collapsibility condition, then the second barycentric subdivision of ${\mathbf K}$ is vertex decomposable and in particular shellable. This is a higher-dimensional generalization of a result of Hachimori, who proved that if the link of each vertex of a pure 2-dimensional simplicial complex ${\mathbf K}$ is connected and ${\mathbf K}$ becomes simplicially collapsible after removing $\tilde{\chi}({\mathbf K})$ facets, where $\tilde \chi ({\mathbf K})$ denotes the reduced Euler characteristic, then the second barycentric subdivision of ${\mathbf K}$ is shellable. For the proof, we introduce a new variant of decomposability of a simplicial complex, stronger than vertex decomposability, which we call star decomposability. This notion may be of independent interest.