Weighted Edge-Decompositions of Graphs

We prove tight estimates on the minimum weight of an edge decomposition of the complete graph into subgraphs of 3 or 4 edges, where the weight of a subgraph is the number of its vertices. We conjecture that the weighted edge decomposition problem on general graphs is NP-complete for every \( k > 2 \). This conjecture is shown to be true for every \( k \leq 11 \) except \( k = 8 \). The problem is motivated by the traffic grooming problem for optical networks.