1. Quantum Algorithms for One-Sided Crossing Minimization
- Author
-
Caroppo, Susanna, Da Lozzo, Giordano, and Di Battista, Giuseppe
- Subjects
Quantum Physics ,Computer Science - Data Structures and Algorithms - Abstract
We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. Given an $n$-vertex bipartite graph $G=(U,V,E\subseteq U \times V)$, a $2$-level drawing $(\pi_U,\pi_V)$ of $G$ is described by a linear ordering $\pi_U: U \leftrightarrow \{1,\dots,|U|\}$ of $U$ and linear ordering $\pi_V: V \leftrightarrow \{1,\dots,|V|\}$ of $V$. For a fixed linear ordering $\pi_U$ of $U$, the OSCM problem seeks to find a linear ordering $\pi_V$ of $V$ that yields a $2$-level drawing $(\pi_U,\pi_V)$ of $G$ with the minimum number of edge crossings. We show that OSCM can be viewed as a set problem over $V$ amenable for exact algorithms with a quantum speedup with respect to their classical counterparts. First, we exploit the quantum dynamic programming framework of Ambainis et al. [Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. SODA 2019] to devise a QRAM-based algorithm that solves OSCM in $O^*(1.728^n)$ time and space. Second, we use quantum divide and conquer to obtain an algorithm that solves OSCM without using QRAM in $O^*(2^n)$ time and polynomial space., Comment: This is the long version of a paper to appear at the 32nd International Symposium on Graph Drawing and Network Visualization (GD '24)
- Published
- 2024