4 papers
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…
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…
The Complexity of Color-constrained Paths in Semicomplete Multipartite Digraphs
Julian Brinkmann
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 e…
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…