Partitioning an undirected, unweighted, square planar graph paths that join certain pairs of nodes

Question

I am trying to find a way to efficiently solve a puzzle that I play a lot by turning it into a graph partitioning problem (which is basically is in its actual form). I know that generally, graph partitioning problems are considered NP-hard or even NP-complete, but considering the unique constraints of the input graph, I am hoping that there is an efficient solution.

Note: This problem is different than the disjoint-vertex paths problem since each node must be included in one of the paths, whereas the disjoint-vertex problem does not consider this. However, if you think that it could be modified as a better approach than the one I describe, please let me know!

Input Graph Description

• Given a size $n$ (which will actually range from 5-14), the graph will contain $n^{2}$ nodes arranged in a square matrix format
• Of the $n^{2}$ nodes, there will be $k$ pairs of marked nodes such that there must always exist a path between each pair. $k$ is generally about the same size as $n$, usually within a range of $n \pm 2$ (for smaller $n$, $k$ is usually smaller than $n$ since too many pairs will make the problem unsolvable)
• A given node has at most 4 edges that go up, down, left, or right
• Each node that is directly "adjacent" to another node in one of the 4 previously mentioned directions will have an edge connecting to that node (with the exception of the specially marked nodes, they do not connect to other specially marked nodes from other pairs)

Here is a pictoral example of a simple input:

In this example, $n = 5$ and $k = 4$. Notice that on the top row of nodes, the "adjacent" A and B nodes are not really adjacent (they have no connecting edge). This is what I was trying to explain in my 4th point. Also notice the "marked" nodes I was referring to are circles and are labeled with letters, marking them.

Problem/Output Graph Description

• Partition the graph into $k$ subgraphs
• Each subgraph is a path connecting one of the $k$ pairs, making them "endpoints"
• The unlabeled nodes form the intermediary part of the subgraphs/paths
• Since each subgraph is actually a path, the marked nodes will ultimately have degrees of 1, and the unmarked nodes will have degrees of 2.
• Every unmarked node must be used in one of the subgraphs (I originally tried to formulate the problem as a vertex-disjoint paths problem, but I felt that this didn't address the problem of including all the original vertices)

Here is a pictoral representation of the solution to the example input:

My Approach

Ultimately, I am using backtrack to find the solution. However, instead of plain backtrack search, I reduce the input graph based on some rules I came up with:

Rules

• If a marked node has only 1 edge, then the node it is adjacent to is "owned" by that marked pair.
• If an unmarked node is owned by one of the $k$ pairs and has more than 2 edges, then 1 or 2 of those edges are pointing to marked nodes of a different pair. These edges are thus removed.
• If an unmarked node is owned by one of the $k$ pairs and has exactly 2 edges, the edge that connects an unowned/unmarked node is now owned by the current pair.
• If there are any unmarked nodes owned by some pair $i$ that are adjacent to unmarked nodes owned by some pair $j$ (where $i \neq j$), then the edges connecting these nodes are removed.
• If an unmarked node owned by some pair $i$ is adjacent to one of the marked nodes in pair $i$ and the degree of that marked node is greater than 1, the edges of the marked node are removed except for the one connecting to the owned unmarked node.

For inputs where $n < 10$ and where $k$ is small enough (wrt to $n$) such that the marked nodes are not too sparse, the rules reduce the input into the solution, obviating the need for backtrack search. However, with larger/more sparse inputs, the rules barely seem to reduce the initial state, and then backtrack becomes necessary. Unfortunately, the search space seems to be too large to efficiently solve the problem.

Main Question

Given the constraints of the input graph, is it possible to add to/revise these rules to be able to solve the problem without resorting to a state space search? Or, is it at least possible to add to/revise the rules in order to improve the problem reduction for larger problem inputs?

If it is indeed the case that there is not much else to do in terms of problem reduction via rules, am I better off implementing a heuristic search (like best-first search) to solve this problem? And if so, does anyone have suggestions for formulating such a heuristic? Thanks!

UPDATE

So I attempted to use best-first search with a few different evaluation functions. I tried to use an A* type approach ($f(n) = g(n) + h(n)$) but this did not work very well, mainly because I could not find a good function to satisfy $h(n) \leq cost(n, goal)$. Instead I used the number of newly "owned" nodes that the state had after applying the aforementioned rules and subtracting the level of the state in the tree (ultimately, this was a function I wanted to maximize instead of minimize). This worked extremely well for many inputs that were not solved completely by the rules, but still larger inputs are not efficiently found.

I am trying to now find some kind of evaluation function that can measure the potential of a certain state to become more "reduced" by these rules, which will guide search towards the states whose descendants will more likely be the goal state.

In addition, I figured out another invariant property about the goal states: using the definition I gave, the goal state must have exactly $n^{2} - k$ edges (and as mentioned before, "labeled" nodes have degree of 1 and unlabeled degree of 2). Also, if the start state is redefined to include edges between all directly adjacent nodes (so including an edge between A and B nodes for example), then a start state always begins with exactly $2n(n-1)$ edges. With both of these in mind, the solution to each problem must result by removing exactly $n^{2} - 2n + k$ edges from the graph.

Given these extra properties, is there a way to determine a specific set of moves to solve the problem, or at least some kind of evaluation function that will help guide a search towards "better" states?

Answer 1

As it turns out, this puzzle was solved in a competition at Oxford University in 2012. The winning implementation used backtrack search with several heuristics and pruning, and it can solve instances of the puzzle much larger than the maximum 14x14 in milliseconds. Apparently, the problem I was trying to solve is equivalent to another game called Numberlink. For anyone else interested, here is the GitHub page for the implementation, which further explains the heuristics used to solve the problem.

In case the link breaks, I will post a quote from the readme:

Numberlink solves puzzles using a heavily pruned backtracking search. In particular the following pruning heuristics are used:

Partial links

A dual representation based on link corners

Optimistic validation

There are multiple ways to do backtracking on numberlink puzzles. The most obvious is to start at a source, choose a link to its other end and recurse. Alternatively one can start at all sources at the same time, or you can ignore the sources and systematically fill out the squares on the paper in some order.

Numberlink uses the later approach: It fills out the paper starting in the upper left corner and continuing along the SW-diagonals. For a 4x4 paper the order in which squares are visited is (in base 16):

0136

247a

58bd

9cef

Backtracking in this systematic give us a lot of advantages compared to starting at the sources:

We never get unconnected squares. We simply always connect a square as we go over it. We never block a source from its other end. To see this notice that blocking a source requires us to have passed it. In passing it we must have connected it to a partial link. The other end of this partial link can not be connected to any other sources or to the side, so it must be in the 'active diagonal'. We always know exactly what squares around us have already been connected. That's the one above us and the one to the left. The directions we need to care about is down and right.