2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Jan 2, 2022 at 4:11

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.