3 papers
cs.DS2026
An FPT Algorithm for Diverse Minimum s-t Cuts
Krishnan Dehaleesan, Pål Grønås Drange, Fedor V. Fomin +2
We study the problem of finding a family of diverse minimum edge s-t cuts in a directed weighted graph G. Given integers k and d, the task is to decide whether G contains k minimum…
cs.DS2025
Structural Optimal Jacobian Accumulation and Minimum Edge Count are NP-Complete Under Vertex Elimination
Matthias Bentert, Alex Crane, Pål Grønås Drange +2
We study graph-theoretic formulations of two fundamental problems in algorithmic differentiation. The first (Structural Optimal Jacobian Accumulation) is that of computing a Jacobi…
cs.DS2015
On the Threshold of Intractability
Pål Grønås Drange, Markus Sortland Dregi, Daniel Lokshtanov +1
We study the computational complexity of the graph modification problems Threshold Editing and Chain Editing, adding and deleting as few edges as possible to transform the input in…