4 papers
Unifying and Extending Strong Simulation of Quantum Circuits
Floris Geerts, Rihan Hai, Matthias Lanzinger +3
We establish functional aggregate queries (FAQs) as a unifying language for exact classical simulation of quantum circuits. A circuit becomes a sum-product query: factors encode ga…
From FPT Decision to FPT Enumeration
Nadia Creignou, Timo Camillo Merkl, Reinhard Pichler +1
Fixed-parameter tractable (FPT) algorithms have been successfully applied to many intractable problems -- with a focus on decision and optimization problems. Their aim is to confin…
FPT Parameterisations of Fractional and Generalised Hypertree Width
Matthias Lanzinger, Igor Razgon, Daniel Unterberger
We present the first fixed-parameter tractable (FPT) algorithms for exact computation of generalized hypertree width (ghw) and fractional hypertree width (fhw). Our algorithms are…
The Parameterized Complexity Landscape of the Unsplittable Flow Problem
Robert Ganian, Mathis Rocton, Daniel Unterberger
We study the well-established problem of finding an optimal routing of unsplittable flows in a graph. While by now there is an extensive body of work targeting the problem on graph…