1

I'm trying to find an algorithm to find the max sum of non adjacent (adjacent being horizontal/vertical elements) elements in an n sized square grid. I've tried converting the grid into a flow graph and calculating the max flow, but not having much luck. Is there an algorithm to solve this? If not, how would we go about making one?

Yuya
  • 13
  • 2
  • What went wrong with the flow graph approach? You're trying to find a maximum weighted independent set on a grid graph, so [maximum flow techniques](https://stackoverflow.com/questions/24204747/maximum-weighted-independent-set-in-bipartite-graph) are the standard algorithm. – kcsquared Mar 10 '22 at 05:15
  • Not sure how to apply the restriction that adjacent cells cannot be chosen – Yuya Mar 10 '22 at 09:59
  • If the grid is guaranteed not to contain negative numbers, then the problem is pretty trivial. Otherwise, your problem is an instance of maximum-weight independent set, so you can pick an algorithm for that. The restriction "adjacent cells cannot be chosen" is exactly the definition of an independent set. – Stef Mar 10 '22 at 13:47
  • How would we solve this if all the numbers were positive? – Yuya Mar 10 '22 at 14:34
  • I don't see any difference in difficulty, either practically or theoretically, between the only-positive and general case. The maximum set will never contain a negative number, except possibly in the case where all numbers are negative, depending on whether the empty set is allowed. – kcsquared Mar 10 '22 at 21:40

1 Answers1

0

There is an algorithm for solving this efficiently, using the max-flow min-cut theorem. This involves a series of transformations of your problem-- you may want to verify for yourself why each transformation works.

First, let's get the positive/negative number technicalities out of the way. If your max sum is allowed to be empty, then the smallest it can ever be is 0. If there is at least one positive number in the grid, we never have to take negative numbers into our sum, so we can completely ignore those cells.

However, if your maximum sum can't be empty, and all numbers are negative, then take the single maximum number in the grid as the best sum.

You have a 'grid graph' in two dimensions: each cell corresponds to a vertex, and vertices are adjacent if and only if their cells are horizontally or vertically adjacent.

This is a bipartite graph (just like a chessboard): if you number the rows and columns, then cell (x, y) is adjacent to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Looking at the parity of x+y, a cell is only adjacent to cells whose coordinates sum to the opposite parity.

Now, you're looking for the maximum weighted independent set in this bipartite graph. The algorithm for finding that has been completely laid out in this SO post, and also in this CS StackExchange post with references, so I won't repeat all of the same details again here for a third time.

Instead, here's an outline of the problem transformations, in order:

  • Max sum of nonadjacent cells in square grid S

  • Maximum weighted independent set of vertices in bipartite graph G

  • Minimum weighted vertex cover in G

  • Minimum weight cut in flow graph F, where F has same vertices as G plus a source and sink vertex

  • Maximum flow in F from source to sink

After removing all negative cells and finding this maximum flow, the answer to your maximum sum question is: (Sum of all cells) - (Max flow in F).

kcsquared
  • 5,244
  • 1
  • 11
  • 36