Finding minimum cut-sets between bounded subgraphs

Question

If a game map is partitioned into subgraphs, how to minimize edges between subgraphs?

I have a problem, I'm trying to make A* searches through a grid-based game like Pacman or Sokoban, but I need to find "enclosures". What do I mean by enclosures? subgraphs with as few cut edges as possible given a maximum size and minimum size for the number of vertices for each subgraph that acts as a soft constraint.

Alternatively, you could say I am looking to find bridges between subgraphs, but its generally the same problem.

---

Example

Grid-based game map example

Given a game that looks like this, what I want to do is find enclosures so that I can properly find entrances to them and thus get a good heuristic for reaching vertices inside these enclosures.

alt text

So what I want is to find these colored regions on any given map.

---

My Motivation

The reason for me bothering to do this and not just staying content with the performance of a simple Manhattan distance heuristic is that an enclosure heuristic can give more optimal results and I would not have to actually do the A* to get some proper distance calculations and also for later adding competitive blocking of opponents within these enclosures when playing Sokoban type games. Also, the enclosure heuristic can be used for a minimax approach to finding goal vertices more properly.

Possible solution

A possible solution to the problem is the Kernighan Lin algorithm :

function Kernighan-Lin(G(V,E)): determine a balanced initial partition of the nodes into sets A and B do A1 := A; B1 := B compute D values for all a in A1 and b in B1 for (i := 1 to |V|/2) find a[i] from A1 and b[i] from B1, such that g[i] = D[a[i]] + D[b[i]] - 2*c[a][b] is maximal move a[i] to B1 and b[i] to A1 remove a[i] and b[i] from further consideration in this pass update D values for the elements of A1 = A1 / a[i] and B1 = B1 / b[i] end for find k which maximizes g_max, the sum of g[1],...,g[k] if (g_max > 0) then Exchange a[1],a[2],...,a[k] with b[1],b[2],...,b[k] until (g_max <= 0) return G(V,E)

My problem with this algorithm is its runtime at O(n^2 * lg(n)), I am thinking of limiting the nodes in A1 and B1 to the border of each subgraph to reduce the amount of work done.

I also don't understand the c[a][b] cost in the algorithm, if a and b do not have an edge between them is the cost assumed to be 0 or infinity, or should I create an edge based on some heuristic.

Do you know what c[a][b] is supposed to be when there is no edge between a and b? Do you think my problem is suitable to use a multilevel method? Why or why not? Do you have a good idea for how to reduce the work done with the Kernighan-lin algorithm for my problem?

Answer 1

There is an algorithm known as Karger’s algorithm for Minimum Cut which helps to find out from a given an undirected and unweighted graph, the smallest cut (smallest number of edges that disconnects the graph into two components).

The input graph may have parallel edges.

You can refer the following links for better understanding:

https://www.geeksforgeeks.org/kargers-algorithm-for-minimum-cut-set-1-introduction-and-implementation/

https://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/