Assume integers $d > r > 0$ and a connected graph $G$ with $d$ vertices. Every point on the $r$-fold Cartesian product of $G$ with itself, $G^{\square r}$, is equivalent to a dimension-$d$ non-negative integer vector whose entries total to $r$. Assume some linear constraints on these dimension-$d$ vectors; we will say that vertex of $G^{\square r}$ is allowed if its corresponding non-negative integer vector satisfies those linear constraints. Given allowed vertices $x$ and $y$, I would like to know if a path exists between them in $G^{\square r}$ such that every vertex on that path is allowed.
Said another way, each cardinality-$r$ multiset of vertices on $G$ is equivalent to a dimension-$d$ non-negative integer vector whose entries total to $r$. Given two such cardinality-$d$ multisets whose corresponding indicator vectors satisfy some linear constraints, find a sequence of such cardinality-$d$ multisets such that
- neighboring multisets in the sequence differ by a move of one element of the multiset along an edge of $G$
- the corresponding non-negative integer vectors satisfy the linear constraints.
If it helps, the linear constraints are of the following form. Assume $c > 0$, a $c \times d$ binary matrix $C$, and a dimension-$c$ positive integer vector $m$. Our linear constraints on a non-negative vector $s$ with total $r$ are that $Cs < m$ and that $s$ is binary.
Somehow it seems that we would be slicing off subsets of the Cartesian product with our linear constraints, but I can't see how we would get the graph structure to talk to the linear constraints. In the long run, we would like to have an algorithm to find the minimal path between points, but deciding existence would be a huge help.
Thank you for your help.
