@inproceedings{pasadakis26a,
author = {Pasadakis, Dimosthenis and Steiner, Raphael S. and Papp, P\'{a}l Andr\'{a}s and B\"{o}hnlein, Toni and Yzelman, A. N.},
title = {Brief Announcement: Direction-Incentivized Spectral Partitioning for Acyclic Graphs},
year = {2026},
isbn = {9798400727610},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3816782.3819184},
doi = {10.1145/3816782.3819184},
abstract = {Partitioning directed acyclic graphs is central to scheduling, pipelining, and memory-hierarchy optimization. We break the symmetry in classical spectral bi-partitioning in order to incentivize the alignment of directed graph cuts and find partitions whose cut edges mostly point in one direction. Our method employs a modified spectral quadratic objective function that promotes cut edges with consistent directionality. We further introduce an algorithm that rectifies misaligned edges to produce acyclic bi-partitions with low balanced cut metrics, and extend it to the retrieval of topological orders. We demonstrate the effectiveness of the proposed algorithms in comparative experiments on real-world cases that focus on acyclic density-based bi-partitioning.},
booktitle = {Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures},
pages = {482--485},
numpages = {4},
keywords = {spectral partitioning, (nearly) acyclic partitioning, directed acyclic graph (DAG) partitioning, conductance},
location = {Royal Holloway, University of London, London, United Kingdom},
series = {SPAA '26}
}