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 k k and t t , and an alphabet ? ? , a feasible labeling  is defined as an assignment of a set Lv?? L v ? ? to each vertex v?V v ? V , such that (i) |Lv|?k | L v | ? k for all v?V v ? V and (ii) each label ??? ? ? ? is used no more than t t times. An edge e={i,j} e = { i , j } is said to be covered  by a feasible labeling if Li?Lj?0? L i ? L j ? 0? . G G is said to be covered if there exists a feasible labeling that covers each edge e?E e ? E . In general, we show that the problem of deciding whether or not a tree can be covered is strongly NP-complete. For k=2 k = 2 , t=3 t = 3 , we characterize the trees that can be covered and provide a linear time algorithm for solving the decision problem. For fixed t t , 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 k k and the size of the tree. For general graphs, we give a strongly polynomial algorithm to resolve the covering problem for k=2 k = 2 , t=3 t = 3 .
software programming graph algorithms complexity