find the maximal number of path graphs of size n fit in a grid graph

Question

I am trying to find a way to calculate or approximate the number of path graphs that can fit in a grid graph. The path graph consists of different states of the nodes.

An example of this path graph is: $1 \rightarrow 2 \rightarrow 3$ So state 1 wants to be connected to state 2 and so forth.

The goal is to find the optimal configuration of states on the nodes such that the path graph is satisfied the maximal times possible in a 10x10 grid graph with periodic boundaries.

In this example the path is satisfied 3 times. \begin{matrix} 1 & 2 & 3\\ 1 & 2 & 3\\ 1 & 2 & 3 \end{matrix}

This is an example of a setting where this path graph is satisfied 8 times in a grid graph. \begin{matrix} 1 & 2 & 1\\ 2 & 3 & 2\\ 1 & 2 & 1 \end{matrix}

Is there a way to approximate the maximal number of satisfactions of a specific path graphs in a grid graph? I think it has something to do with partitions/number theory, but I can not find a specific solution to this problem. I hope someone can give me a direction to find a solution.

Answer 1

You can solve the problem via integer linear programming as follows. Let $P_n$ be the set of possible paths with $n$ nodes. In particular, $|P_2|=400$, $|P_3|=1200$, $|P_4|=3600$, and $|P_5|=10000$. For path $p\in P_n$ and $k \in \{1,\dots,n\}$, let $(i_{p,k},j_{p,k})$ be the nodes in the path, in order. For $(i,j)\in \{1,\dots,10\}^2$ and $k \in \{1,\dots,n\}$, let binary decision variable $x_{i,j,k}$ indicate whether node $(i,j)$ takes value $k$. For $p\in P_n$, let binary decision variable $y_p$ indicate whether path $p$ is selected. The problem is to maximize $\sum_p y_p$ subject to \begin{align} \sum_k x_{i,j,k} &= 1 &&\text{for all $i,j$} \tag1\\ y_p &\le x_{i_{p,k},j_{p,k},k} &&\text{for all $p,k,i_{p,k},j_{p,k}$} \tag2 \end{align} Constraint $(1)$ assigns exactly one value to each node. Constraint $(2)$ forces the node values to be consistent with every selected path.

Here are the best solutions I have found for small $n$. Not sure whether the last three are optimal.

$200$ paths (optimal) with $2$ nodes:

1 2 1 2 1 2 1 2 1 2 
2 1 2 1 2 1 2 1 2 1 
1 2 1 2 1 2 1 2 1 2 
2 1 2 1 2 1 2 1 2 1 
1 2 1 2 1 2 1 2 1 2 
2 1 2 1 2 1 2 1 2 1 
1 2 1 2 1 2 1 2 1 2 
2 1 2 1 2 1 2 1 2 1 
1 2 1 2 1 2 1 2 1 2 
2 1 2 1 2 1 2 1 2 1 

$200$ paths with $3$ nodes:

1 2 1 2 1 2 1 2 1 2 
2 3 2 3 2 3 2 3 2 3 
1 2 1 2 1 2 1 2 1 2 
2 3 2 3 2 3 2 3 2 3 
1 2 1 2 1 2 1 2 1 2 
2 3 2 3 2 3 2 3 2 3 
1 2 1 2 1 2 1 2 1 2 
2 3 2 3 2 3 2 3 2 3 
1 2 1 2 1 2 1 2 1 2 
2 3 2 3 2 3 2 3 2 3 

$244$ paths with $4$ nodes:

1 2 3 4 3 4 3 2 1 4 
2 1 4 3 2 1 2 1 2 3 
3 4 3 2 1 2 3 4 3 4 
4 3 2 1 2 3 4 3 2 1 
3 2 1 2 3 4 3 2 1 2 
4 1 2 3 4 3 2 1 2 3 
3 2 3 4 3 2 1 2 3 4 
2 1 4 3 2 1 2 3 4 3 
1 2 3 2 1 2 3 4 1 2 
4 3 4 1 2 3 4 3 2 3 

$316$ paths with $5$ nodes:

1 2 3 4 5 2 1 4 3 2 
2 1 2 5 4 3 2 5 4 3 
3 2 5 4 3 2 1 2 5 4 
4 5 4 3 2 1 2 3 4 5 
5 4 3 2 1 2 3 4 5 4 
2 3 2 1 2 3 4 5 4 3 
1 2 1 2 3 4 5 4 3 2 
4 5 2 3 4 5 4 3 2 1 
3 4 5 4 5 4 3 2 1 2 
2 3 4 5 4 3 2 1 2 1