Partitioning an undirected, unweighted, square planar graph paths that join certain pairs of nodes
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). 180
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? 835