All graphs in this question are finite, simple, and undirected. Let $H$ be a regular graph on at least five vertices, let $v_1,v_2,\dots,v_n$ be the vertices in $H$, and let $M$ be the adjacency matrix of $H$. Let $M_{ij}$ denote the $(i,j)$-th entry of $M$. The following problem is NP-complete (because it is same as checking whether $G$ has a locally bijective homomorphism to $H$; see the survey [1] for details).
$M$-PARTITION
Input: A graph $G$.
Question: Does there exist a partition $U_1,U_2,\dots,U_n$ of the vertex set of $G$ such that for all $i$ and $j$ in $\{1,2,\dots,n\}$, each vertex in $U_i$ has exactly $M_{ij}$ neighbours in $U_j$ ?
(To be explicit, if $M_{ij}=0$, then each vertex in $U_i$ has no neighbour in $U_j$; and if $M_{ij}=1$, then each vertex in $U_i$ has exactly one neighbour in $U_j$. )
I am interested in a related problem. Let $M^*$ be a fixed matrix obtained from $M$ by changing some of the 1-entries in $M$ to $*$-entry so that the following hold for $M^*$ (to clarify, each entry of $M^*$ is $0,1,$ or $*$) :
- for every row in $M^*$, the number of 1-entries equals the number of $*$-entries, and
- for all $i$ and $j$, $M_{ij}=*$ if and only if $M_{ji}=1$.
$M^*$-PARTITION
Input: A regular graph $G$.
Question: Does there exist a partition $U_1,U_2,\dots,U_n$ of the vertex set of $G$ such that for all $i$ and $j$ in $\{1,2,\dots,n\}$ with $M_{ij}\neq *$, each vertex in $U_i$ has exactly $M_{ij}$ neighbours in $U_j$ ?
(To be explicit, if $M_{ij}=0$, then each vertex in $U_i$ has no neighbour in $U_j$; if $M_{ij}=1$, then each vertex in $U_i$ has exactly one neighbour in $U_j$; if $M_{ij}=*$, each vertex in $U_i$ can have zero or any number of neighours in $U_j$).
What is the complexity of the problem $M^*$-PARTITION?
Of course, the complexity might vary depending on $M^*$. Note that $M^*$-PARTITION problem is a special case of the $D_q$-paritition problem in the LC-VSP framework of Telle and Proskurowski [2] (where $q=n$ and $D_q$ is the matrix obtained from $M^*$ by replacing $0$-entries by $\{0\}$, $1$-entries by $\{1\}$, and $*$-entries by $\{0,1,\dots\}$).
NB: We assume that $G$ is regular to keep things as simple as possible.
[1] Fiala, Jiří; Kratochvíl, Jan, Locally constrained graph homomorphisms – structure, complexity, and applications, Comput. Sci. Rev. 2, No. 2, 97-111 (2008). ZBL1302.05122.
[2] Telle, Jan Arne; Proskurowski, Andrzej, Algorithms for vertex partitioning problems on partial (k)-trees, SIAM J. Discrete Math. 10, No. 4, 529-550 (1997). ZBL0885.68118.
