A Row-wise Algorithm for Graph Realization
<|reference_start|>A Row-wise Algorithm for Graph Realization: Given a $\{0,1\}$-matrix $M$, the graph realization problem for $M$ asks if there exists a spanning forest such that the columns of $M$ are incidence vectors of paths in the forest. The problem is closely related to the recognition of network matrices, which are a large subclass of totally unimodular matrices and have many applications in mixed-integer programming. Previously, Bixby and Wagner have designed an efficient algorithm for graph realization that grows a submatrix in a column-wise fashion whilst maintaining a graphic realization. This paper complements their work by providing an algorithm that works in a row-wise fashion and uses similar data structures. The main challenge in designing efficient algorithms for the graph realization problem is ambiguity as there may exist many graphs realizing $M$. The key insight for designing an efficient row-wise algorithm is that a graphic matrix is uniquely represented by an SPQR tree, a graph decomposition that stores all graphs with the same set of cycles. The developed row-wise algorithm uses data structures that are compatible with the column-wise algorithm and can be combined with the latter to detect maximal graphic submatrices.<|reference_end|>
@article{van der hulst2024a,
    title={A Row-wise Algorithm for Graph Realization},
    author={Rolf van der Hulst, Matthias Walter},
    journal={arXiv preprint arXiv:2408.12869},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.12869},
    primaryClass={cs.DM math.CO}
}