6 papers
Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Rank Parameters
Carla Groenland, Isja Mannens, Jesper Nederlof +2
A homomorphism from a graph to a graph is an edge-preserving mapping from to . In the graph homomorphism problem, denoted by , the graph is fixed a…
The Parameterised Complexity of Integer Multicommodity Flow
Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen +2
The Integer Multicommodity Flow problem has been studied extensively in the literature. However, from a parameterised perspective, mostly special cases, such as the Disjoint Paths…
A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth
Isja Mannens, Jesper Nederlof
We give a fine-grained classification of evaluating the Tutte polynomial on all integer points on graphs with small treewidth and cutwidth. Specifically, we show for any…
Reconstructing Graphs from Connected Triples
Paul Bastide, Linda Cook, Jeff Erickson +4
We introduce a new model of indeterminacy in graphs: instead of specifying all the edges of the graph, the input contains all triples of vertices that form a connected subgraph. In…
Tight bounds for counting colorings and connected edge sets parameterized by cutwidth
Carla Groenland, Jesper Nederlof, Isja Mannens +1
We study the fine-grained complexity of counting the number of colorings and connected spanning edge sets parameterized by the cutwidth and treewidth of the graph. While decomposit…
On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem
Isja Mannens, Jesper Nederlof, Céline Swennenhuis +1
We study a variant of Min Cost Flow in which the flow needs to be connected. Specifically, in the Connected Flow problem one is given a directed graph , along with a set of dema…