On a labeling problem in graphs

Motivated by applications in software programming, we consider the problem of covering a graph by a feasible labeling. Given an undirected graph G=(V,E)G=(V,E), two positive integers kk and tt, and an alphabet ΣΣ, a feasible labeling   is defined as an assignment of a set Lv⊆ΣLv⊆Σ to each vertex v∈Vv∈V, such that (i) |Lv|≤k|Lv|≤k for all v∈Vv∈V and (ii) each label α∈Σα∈Σ is used no more than tt times. An edge e={i,j}e={i,j} is said to be covered   by a feasible labeling if Li∩Lj≠0̸Li∩Lj≠0̸. GG is said to be covered if there exists a feasible labeling that covers each edge e∈Ee∈E.In general, we show that the problem of deciding whether or not a tree can be covered is strongly NP-complete. For k=2k=2, t=3t=3, we characterize the trees that can be covered and provide a linear time algorithm for solving the decision problem. For fixed tt, we present a strongly polynomial algorithm that solves the decision problem; if a tree can be covered, then a corresponding feasible labeling can be obtained in time polynomial in kk and the size of the tree. For general graphs, we give a strongly polynomial algorithm to resolve the covering problem for k=2k=2, t=3t=3.