This paper considers four problems with possible applications in network design: Given a graph G with | G | = n and an integer k ≥ 0 , does G have a DFS tree with (i) ≤ k leaves, (ii) ≥ k leaves, (iii) ≤ n − k leaves, and (iv) ≥ n − k leaves? We show that all four problems are NP-hard. When parameterized by k , we prove that while (i) is para-NP-hard and (ii) is W[1]-hard, both (iii) and (iv) admit polynomial kernels with O ( k 3 ) vertices, implying FPT algorithms running in k O ( k ) ⋅ n O ( 1 ) time. Our polynomial kernels are based on a O ( k ) -sized vertex cover structure associated with the solution of these problems. As a byproduct, we obtain polynomial kernels for these problems parameterized by the vertex cover number of the input graph.

Finding the smallest d-chain with a specific (d−1)-boundary in a simplicial complex is known as the Minimum Bounded Chain problem (MBCd). MBCd is NP-hard for all d≥2. In this paper, we prove that it is also W[1]-hard for all d≥2, if we parameterize the problem by solution size. We also give an algorithm solving MBC1 in polynomial time and introduce and implement two fixed parameter tractable (FPT) algorithms solving MBCd for all d. The first algorithm uses a shortest path approach and is parameterized by solution size and coface degree. The second algorithm is a dynamic programming approach based on treewidth, which has the same runtime as a lower bound we prove under the exponential time hypothesis.

Given a simplicial complex with $n$ simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected surface with a fixed boundary. We also study the related Sum-of-Genus Subsurface Recognition (SoG) problem, where we instead search for a surface whose boundary, number of connected components, and total genus are given. For both of these problems, we give parameterized algorithms with respect to the treewidth $k$ of the Hasse diagram that run in $2^{O(k \log k)}n^{O(1)}$ time. For the SoG problem, we also prove that our algorithm is optimal assuming the exponential-time hypothesis. In fact, we prove the stronger result that our algorithm is ETH-tight even without restriction on the total genus.

Abstract The alpha complex efficiently computes persistent homology of a point cloud $$X$$ X in Euclidean space when the dimension $$d$$ d is low. Given a subset $$A$$ A of $$X$$ X , relative Čech persistent homology can be computed as the persistent homology of the relative Čech complex $${\check{\mathrm{C}}}(X, A)$$ C ˇ ( X , A ) . However, this is not computationally feasible for larger point clouds $$X$$ X . The aim of this note is to present a method for efficient computation of relative Čech persistent homology in low dimensional Euclidean space. We introduce the relative Delaunay–Čech complex $${\text {Del}\check{\mathrm{C}}}(X, A)$$ Del C ˇ ( X , A ) whose homology is the relative Čech persistent homology. It is constructed from the Delaunay complex of an embedding of $$X$$ X in $$(d+1)$$ ( d + 1 ) -dimensional Euclidean space.

The alpha complex efficiently computes persistent homology of a point cloud $X$ in Euclidean space when the dimension $d$ is low. Given a subset $A$ of $X$, relative persistent homology can be computed as the persistent homology of the relative Čech complex. But this is not computationally feasible for larger point clouds. The aim of this note is to present a method for efficient computation of relative persistent homology in low dimensional Euclidean space. We introduce the relative Delaunay Čech complex whose homology is the relative persistent homology. It can be constructed from the Delaunay complex of an embedding of the point clouds in $(d+1)$-dimensional Euclidean space.