Finding minimum cost in a binary matrix

Question

Consider a n * n binary matrix. Each cell of this matrix has at most 4 neighbors (if it exists). We call two cells of this matrix incompatible if they are neighbors and their values are not equal. We pay $b for each incompatible pair. Also we can change the value of the cell with paying $a.

The question is to find the minimum cost for this matrix.

I already used backtracking and found an algorithm of O(2 ^ (n * n)). Can someone help me find a more efficient algorithm?

Answer 1

This idea is due to Greig, Porteous, and Seheult. Treat the matrix as a capacitated directed graph with vertices corresponding to matrix entries and arcs from each vertex to its four neighbors, each with capacity b. Introduce two more vertices, a source and a sink, and arcs of capacity a: from the source to each vertex with a corresponding 0 entry, and to the sink from each vertex with a corresponding 1 entry. Find a minimum cut; the entries with value 0 after changes are the vertices on the source side of the cut, and the entries with value 1 after changes are the vertices on the sink side of the cut.

The cost of this cut is exactly your objective. Of the capacity-a from-source arcs, the ones crossing the cut correspond to changes from 0 to 1. Of the capacity-a to-sink arcs, the ones crossing the cut correspond to changes from 1 to 0. Of the capacity-b arcs, the ones crossing the cut correspond to those instances where there is an arc from a 0 to a 1.