2024-07-17
Quantum algorithms for vertex sparsification
Publication
Publication
The goal of graph sparsification is to compress large graphs into smaller ones. In vertex sparsification we are given a graph and a set of terminals. We aim to find a graph with the terminals as vertices, that preserves some property of interest. For vertex- flow sparsification we aim to preserve flows. Moitra proved that vertex-flow sparsifiers exist with quality O( log k/ log log k) , where k is the number of terminals. There is a classical algorithm with runtime ˜O(m2) to find such vertex-flow sparsifier, where m is the number of edges of the original graph. In this work we present a new quantum algorithm with runtime ˜O(m11/6n1/6) that finds the same quality vertex-flow sparsifier, where n is the number of vertices of the original graph. This is a small polynomial speedup for dense graphs. The quantum speedup is based on the classical algorithm, but uses various quantum subroutines from the literature.
Additional Metadata | |
---|---|
R.M. de Wolf (Ronald) | |
Organisation | Algorithms and Complexity |
Grevink, L. (2024, July 17). Quantum algorithms for vertex sparsification. |