{"ID":2869257,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.14807","arxiv_id":"2509.14807","title":"The Complexity of Finding and Counting Subtournaments","abstract":"We study the complexity of counting and finding small tournament patterns inside large tournaments. Given a fixed tournament $T$ of order $k$, we write ${\\#}\\text{IndSub}_{\\text{To}}(\\{T\\})$ for the problem whose input is a tournament $G$ and the task is to compute the number of subtournaments of $G$ that are isomorphic to $T$. Previously, Yuster [Yus25] obtained that ${\\#}\\text{IndSub}_{\\text{To}}(\\{T\\})$ is hard to compute for random tournaments $T$. We consider a new approach that uses linear combinations of subgraph-counts [CDM17] to obtain a finer analysis of the complexity of ${\\#}\\text{IndSub}_{\\text{To}}(\\{T\\})$. We show that for all tournaments $T$ of order $k$ the problem ${\\#}\\text{IndSub}_{\\text{To}}(\\{T\\})$ is always at least as hard as counting $\\lfloor 3k/4 \\rfloor$-cliques. This immediately yields tight bounds under ETH. Further, we consider the parameterized version of ${\\#}\\text{IndSub}_{\\text{To}}(\\mathcal{T})$ where we only consider patterns $T \\in \\mathcal{T}$ and that is parameterized by the pattern size $|V(T)|$. We show that ${\\#}\\text{IndSub}_{\\text{To}}(\\mathcal{T})$ is ${\\#}W[1]$-hard as long as $\\mathcal{T}$ contains infinitely many tournaments.","short_abstract":"We study the complexity of counting and finding small tournament patterns inside large tournaments. Given a fixed tournament $T$ of order $k$, we write ${\\#}\\text{IndSub}_{\\text{To}}(\\{T\\})$ for the problem whose input is a tournament $G$ and the task is to compute the number of subtournaments of $G$ that are isomorphi...","url_abs":"https://arxiv.org/abs/2509.14807","url_pdf":"https://arxiv.org/pdf/2509.14807v1","authors":"[\"Simon Döring\",\"Sarah Houdaigoui\",\"Lucas Picasarri-Arrieta\",\"Philip Wellnitz\"]","published":"2025-09-18T10:07:46Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}