## 3 The Static Form of the Problem
### Solution to WCCP  
As the size of the problem (_i.e._, the number of vertices, the number of edges and the amount of weights) scales up, WCCP becomes very hard to tackle. Existing polynomial solutions focus only on claw-free perfect graphs. However, claw-free graphs are rare in practice. For practical problems that we may encounter in networks, we need a definitive method to solve them, irrespective of whether they are claw-free or not.  
Here, we propose a search-based algorithm to solve WCCP for all perfect graphs (which is more general than the existing algorithms). This algorithm can run in linear time for most of the cases (when pruning is applicable). Note that pruning can be applied even when the graph has claw sub-graphs and is imperfect. After each iteration of pruning, the graph can be modified, and this usually yields a simpler graph. In some extreme cases, its running time grows exponentially with the size of the graph (when pruning is not applicable); we therefore introduce an approximation method to guarantee that the run time is invariant to the amount of weights. Fortunately, these extreme cases are hardly seen in the settings of wireless communication [19], and they are very difficult to construct, even in the pure mathematical setting.  
In essence, our algorithm is a search algorithm that structures all possible solutions into a tree structure. Consider the WCCP in such a way: for each vertex in the graph, its weight equals the sum of the weights of all cliques of which this vertex is a part. Then, if we can list all cliques that one vertex is a part of, the search of cliques that cover the graph can be transformed into the search for a method to allocate weights to a node's participating cliques, as will soon be defined in Definition 2. The transformation of \"covering\" to \"allocation\" enables an iteration-based approach. We iteratively allocate a weight for each vertex. When all vertices have their weights allocated, the solution to WCCP is determined. The search tree is equivalent to a decision tree.  
The root node of the search tree denotes the initial state of the problem. As we go down one level, a decision is made at each vertex. After \(|V|\) levels, with the respective decision made at every vertex, one solution, or a weighted clique cover, is determined at each leaf node. For example, consider the coding graph shown in Figure 2. The first search decision can be made at the central vertex \(A\). Its weight (three) should be allocated to three adjacent cliques, \((A,B)\), \((A,C)\) and \((A)\). However, due to the fact that \(w(A)<w(B)+w(C)\), we can omit the last clique and allocate its weight only to the first two cliques. This will be justified with the introduction of pruning rules in Section 3.2.1. The allocation can be done in three possible ways: \((3,0),(2,1)\) and \((1,2)\) between cliques \((A,B)\) and \((A,C)\). Therefore, in the first layer, we have three branching nodes, each of which denotes one choice of possible allocations.  
Figure 2: One example of a coding graph.  
If we continue the search in this manner, it is a brute-force algorithm that has a time complexity of \(O({W+D-1\choose D-1}^{|V|})\), where \(W=\max_{v\in V}w(v)\) and \(D\) is the average number of participating cliques that one vertex can be in. In simple graphs, \(D\) is close to the average degree of vertices, which is easier to calculate. In real cases, since \(W\gg D\), \({W+D-1\choose D-1}\approx W^{D-1}\), the complexity can be simplified as \(O(W^{D|V|})\). This is obviously unacceptable, as the scale factors are both on the base and the exponent. Therefore, we seek a better algorithm through pruning and approximation.