I have a problem involving the traversal of a binary matrix (which can also be conceptualized as a graph traversal problem) under specific constraints, aiming to minimize the maximum number of simultaneously "open" rows throughout the process. The matrix is defined such that no column or row sums to zero, and traversal must cover each '1' exactly once, adhering to these rules:
- On traversing a '1' in any column, all other '1's in the same column must be traversed before moving to a different column. The order of column and row traversal is flexible within this constraint.
- A row is considered "open" from the moment the first '1' is traversed until the last '1' in it is traversed. It "closes" immediately after this last '1' is covered, independent of the column traversal completion.
The challenge is to identify a traversal strategy that minimizes the peak number of open rows at any time.
Context and Attempts:
- Initial strategies involved starting with columns of minimum sum and proceeding to the next column with the maximum overlap (shared '1's) with the current column, which turned out to not generalize for larger matrices.
- For small matrices (3x3), I had a strategy: the minimum between the two largest column sums and the count of row sums greater than or equal to 2. This, however, does not scale beyond 3x3 matrices.
Questions:
- Is there a known strategy or algorithm that can consistently identify an optimal traversal path under these constraints?
- Can the minimum number of concurrently open rows for any matrix be determined without fully resolving the traversal path?
I believe matrices that are isomorphic might share the same optimal solution, suggesting a structural approach to this problem. Any insights or problem solving strategies/tools would be highly appreciated.