E-Graphs as Circuits, and Optimal Extraction via Treewidth
<|reference_start|>E-Graphs as Circuits, and Optimal Extraction via Treewidth: We solve the optimal extraction problem for e-graphs by first showing a connection between e-graphs and cyclic monotone Boolean circuits, then solving the weighted satisfiability problem for such circuits. The solution is a parameterized algorithm based on treewidth. Additionally, we show how the circuit view of e-graphs allows us to apply simplification techniques that are not possible when operating directly on e-graphs. While the core parameterized algorithm may be adapted to work directly on e-graphs, the simplification results show why the circuit view is helpful.<|reference_end|>
@article{sun2024e-graphs,
    title={E-Graphs as Circuits, and Optimal Extraction via Treewidth},
    author={Glenn Sun, Yihong Zhang, and Haobin Ni},
    journal={arXiv preprint arXiv:2408.17042},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.17042},
    primaryClass={cs.DS}
}