{"ID":2879341,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.16173","arxiv_id":"2508.16173","title":"Symmetry-breaking symmetry in directed spectral partitioning","abstract":"We break the symmetry in classical spectral bi-partitioning in order to incentivise the alignment of directed cut edges. We use this to generate acyclic bi-partitions and furthermore topological orders of directed acyclic graphs with superb locality. The new approach outperforms the state-of-the-art Gorder algorithm by up to $17\\times$ on total reuse distance and minimum linear arrangement.","short_abstract":"We break the symmetry in classical spectral bi-partitioning in order to incentivise the alignment of directed cut edges. We use this to generate acyclic bi-partitions and furthermore topological orders of directed acyclic graphs with superb locality. The new approach outperforms the state-of-the-art Gorder algorithm by...","url_abs":"https://arxiv.org/abs/2508.16173","url_pdf":"https://arxiv.org/pdf/2508.16173v1","authors":"[\"Dimosthenis Pasadakis\",\"Raphael S. Steiner\",\"Pál András Papp\",\"Toni Böhnlein\",\"Albert-Jan N. Yzelman\"]","published":"2025-08-22T07:51:07Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}