2024/08/23 by Rolf van der Hulst, van der Hulst, Rolf, Matthias Walter +1 · 2 citations
Computer Science · #05C50 (secondary) #52B40 (secondary) #90C57 (primary) #Advanced Graph Neural Networks #Combinatorics (math.CO) #Data Mining Algorithms and Applications #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2408.12869
openalex publication_date 2024/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. Existing efficient algorithms for graph realization grow a submatrix in a column-wise fashion whilst maintaining a graphic realization. In the context of mixed-integer linear programming, this limits the set of submatrices of the constraint matrix that can efficiently be determined to be network matrices to network submatrices that span all rows and a subset of the columns. This paper complements the existing work by providing an algorithm that works in a row-wise fashion and uses similar data structures, and enables the detection of arbitrary graphic submatrices. 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.