# Complexity of a matrix partition problem in graphs

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.

• I stumbled upon a paper very much relevant to this question. They consider a matrix partition problem where entries of the matrix are from {0,1,*}, (and the entries rep. same thing as in the question). The conditions in the question (bullets) are not there in the problem they consider; so $M^*$-partition problem is a special case of the problem they consider. Jan 2 at 4:11