Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
Faster Algorithms for Deciding the Unbiased Maker-Breaker Triangle Game on General Graphs
Julian Christoph Brinkmann, Anand Srivastav
In this paper, we present new polynomial-time algorithms for determining the winner of the unbiased triangle game played on the edge set of general graphs. To that end, we propose…
cs.CC2026
On the Complexity of the Minimum-()-Shortcut Problem
Tatiana Rocha Avila, Julian Christoph Brinkmann, Alexander Leonhardt +1
We consider the Minimum-- problem (), where the goal is to find the smallest set of shortcut edges such that every ver…
cs.CC2025
The Parametrised Complexity of Counting Small Sub-Hypergraphs
Marco Bressan, Julian Brinkmann, Holger Dell +2
Subgraph counting is a fundamental and well-studied problem whose computational complexity is well understood. Quite surprisingly, the hypergraph version of subgraph counting has b…