Subgraph counting is a fundamental and well-studied problem whose computational complexity is well understood. Quite surprisingly, the hypergraph version of subgraph counting has been almost ignored. In this work, we address this gap by investigating the most basic sub-hypergraph counting problem: given two hypergraphs \(H\) and \(G\), compute the number of sub-hypergraphs of \(G\) isomorphic to \(H\). Formally, for a family \(\mathcal{H}\) of hypergraphs, let #Sub\((\mathcal{H})\) be the restriction of the problem to \(H \in \mathcal{H}\); the induced variant #IndSub\((\mathcal{H})\) is defined analogously. Our main contribution is a complete classification of the fixed-parameter tractability of these problems. Assuming the Exponential Time Hypothesis, we prove that #Sub\((\mathcal{H})\) is fixed-parameter tractable if and only if \(\mathcal{H}\) has bounded fractional co-independent edge-cover number, a novel graph parameter introduced in this work, and that #IndSub\((\mathcal{H})\) is fixed-parameter tractable if and only if \(\mathcal{H}\) has bounded fractional edge-cover number. Both results subsume pre-existing results for graphs as special cases. We also show that the fixed-parameter tractable cases of #Sub\(\mathcal{H})\) and #IndSub\((\mathcal{H})\) are unlikely to be in polynomial time, unless respectively \(\#P = P\) and Graph Isomorphism \(\in\, P\). This shows a separation with the special case of graphs, where the fixed-parameter tractable cases are known to actually be in polynomial time. From a technical standpoint, we turn to the hypergraph homomorphism basis and lift the complexity monotonicity principle due to Curticapean, Dell, and Marx [STOC 2017] from graphs to hypergraphs of unbounded rank. Moreover, we crucially rely on the integrality gap for fractional independent sets based on adaptive width due to Bressan, Lanzinger, and Roth [STOC 2023]. The heart of our proofs consists of a careful investigation of the adaptive width of the patterns that survive in the hypergraph homomorphism basis. We also consider a natural variant of sub-hypergraphs where edges are trimmed to be vertex subsets; we show that, surprisingly, in this case complexity monotonicity fails.

Every semicomplete multipartite digraph contains a quasi-Hamiltonian path, but the problem of finding a quasi-Hamiltonian path with prescribed start and end vertex is NP-complete even when restricted to semicomplete multipartite digraphs with independence number exactly 3. Bang-Jensen, Wang and Yeo (arXiv 2024) showed that deciding the presence of a quasi-Hamiltonian cycle which does not contain at least one vertex from each color class is NP-complete. Similarly, deciding the presence of a quasi-Hamiltonian cycle which intersects every part exactly once is also NP-complete as shown in the same work. In this paper, we continue the study of paths with constraints on the number of covered vertices from each color class. We consider the problem of finding a path with prescribed start and end vertex that contains at least $a$ and at most $b$ vertices from each color class where all color classes have size exactly $α$. This unifies the Hamiltonian path problem, the quasi-Hamiltonian path problem and the path-version of the cycle problems mentioned above, among other problems. Using Schaefer's dichotomy theorem, we classify the complexity of almost all problems in our framework. Notable open problems are the Hamiltonian path problem on semicomplete multipartite digraphs as well as the quasi-Hamiltonian path problem restricted to semicomplete multipartite digraphs with independence number 2. We then investigate the quasi-Hamiltonian path problem restricted to semicomplete multipartite digraphs with independence number 2. We generalize sufficient criteria for Hamiltonian $(s,t)$-paths in semicomplete digraphs to sufficient criteria for quasi-Hamiltonian $(s,t)$-paths in this class. Although this does not settle the problem, the initial results suggest that this special case may be solvable in polynomial time.