4 papers
Edge Geography is XNLP-hard for Pathwidth and in XP for Tree-Partition Width
Thobias Kvalvik Høivik, Erlend Raa Vågset
Directed Edge Geography and Undirected Edge Geography are classical PSPACE-complete two-player graph games in which players alternately make moves along edges, deleting each one af…
ETH-tight algorithms for finding surfaces in simplicial complexes of bounded treewidth
Mitchell Black, Nello Blaser, Amir Nayyeri +1
Given a simplicial complex with simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected sur…
The Parameterized Complexity of Finding Minimum Bounded Chains
Nello Blaser, Morten Brun, Lars M. Salbu +1
Finding the smallest -chain with a specific -boundary in a simplicial complex is known as the \textsc{Minimum Bounded Chain} (MBC) problem. The MBC problem is NP-…
Linear MIM-Width of Trees
Svein Høgemo, Jan Arne Telle, Erlend Raa Vågset
We provide an algorithm computing the linear maximum induced matching width of a tree and an optimal layout.