A hard graph theory problem?

Suppose I have a symmetric NxN binary matrixM=[a_ij] (which is
the adjacency matrix of the graph) and a set L of integers(L= {0}
union {l_r}). l_r is indeed key label. We may assume the
number of 1's in each row of M is the same and equal to K
to reflect it is a regular graph.
I want an algorithm to map entries of M to an l_r in L such that
- f(a_ij) = 0 if a_ij=0
- f(a_ij) = f(a_ji).

In essence, we map the binary matrix M to another
matrix P with entries drawn from L. Besides, I want the
resulting matrix P fulfill the following constraints:
- for some d|K (with K/d = t), each row of P has t different
l_r's and each l_r appears d times. There is no restriction
that the same subset of l_r appear in every row. That is,
row 1 could have, say, {l_1, l_2, l_3, l_4, l_5) while row 2
could have {l_2, l_5, l_6, l_7, l_8}.

Does there exists a reasonably efficient algorithm to achieve
the labeling?

It seems to be some kind of edge colouring problem but it just
looks different from the usual colouring problem. It may also
be viewed as a graph decomposition problem. What should
we call it?

If d=K/2, the problem could be easy by finding an Eulerian tour.
The difficulty seems to come up with d neq K/2.

In case it is difficult, I am wondering whether the problem is
much easier if we don't need the requirement that each l_r in
a row appears exactly d times.

For instance, we re-cast the restriction as: each row has no more
than t l_r's and each l_r appears no more than d times in a row
(with t*d > K). Would this one be much easier? Can it be formulated
as a linear programming problem?

Thanks.

.