A Row-wise Algorithm for Graph Realization
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912450849275904 |
|---|---|
| author | van der Hulst, Rolf Walter, Matthias |
| author_facet | van der Hulst, Rolf Walter, Matthias |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_12869 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Row-wise Algorithm for Graph Realization van der Hulst, Rolf Walter, Matthias Discrete Mathematics Combinatorics 90C57 (primary), 52B40 (secondary), 05C50 (secondary) G.2.1; G.2.2 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. |
| title | A Row-wise Algorithm for Graph Realization |
| topic | Discrete Mathematics Combinatorics 90C57 (primary), 52B40 (secondary), 05C50 (secondary) G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2408.12869 |