Thobias Høivik

Research

Research

I am interested in parameterized complexity, graph games, structural graph theory, algebraic methods in computation, and more!

I am broadly interested in theoretical computer science, especially problems where combinatorial structure interacts with computation. At the moment, I am most interested in parameterized complexity, graph games, and structural graph parameters such as treewidth and pathwidth. I am also curious about algebraic and geometric directions in complexity, particularly where graph-theoretic objects appear naturally.

Unmixedness of binomial edge idealsComputational algebra · graph theory · parameterized complexity
Work in progress

Let GG be a finite simple graph with vertex set [n][n], and let K[x1,…,xn,y1,…,yn]\mathbb K[x_1,\ldots,x_n,y_1,\ldots,y_n] be a polynomial ring over a field K\mathbb K. The binomial edge ideal of GG is the ideal

JG=⟨xiyj−xjyi:{i,j}∈E(G), i<j⟩.J_G = \langle x_i y_j - x_j y_i : \{i,j\} \in E(G),\ i < j\rangle.

I am currently looking into the computational complexity of properties related to these binomial edge ideals.

Edge Geography parameterized by pathwidth and tree-partition widthGraph games · parameterized complexity
Accepted · ESA 2026Preprint coming later

Edge Geography is a two-player graph game in which players traverse edges that are then deleted. Since the history of deleted edges matters, the game is a natural test case for understanding when structural graph parameters give useful dynamic programming algorithms.

Bodlaender showed that Edge Geography is solvable in linear time on graphs of bounded treewidth and bounded degree. A natural question is whether the bounded-degree assumption can be removed, or whether treewidth alone is enough to make the problem fixed-parameter tractable.

We show that Edge Geography is XNLP-hard parameterized by pathwidth. Since bounded pathwidth implies bounded treewidth, this gives evidence that treewidth alone is not sufficient for fixed-parameter tractability, unless FPT=XNLP\mathrm{FPT} = \mathrm{XNLP}.

We also give a nontrivial upper bound: an XP algorithm for Edge Geography on graphs of bounded tree-partition width.

For an introduction to what Edge Geography is check out this lab page!