## 3 The Static Form of the Problem
### Solution to WCCP
#### 3.2.1 Pruning  
Before describing the pruning mechanism, we first formally define a concept--participating cliques. **Definition 2** (Participating clique). : _In a graph \(G=(V,E)\), a participating clique of a given vertex \(v\in V\) is any clique \(G^{\prime}\subset G\), such that \(v\in G^{\prime}\)._  
Before branching on one vertex, we need to get all of its participating cliques; the number of branches then is dependent on the number of ways to allocate weights to these participating cliques. The pruning rule below demonstrates that we only need to consider a subset of these participating cliques in certain cases, and hence, we can significantly reduce the amount of computation. \(N(v)\) denotes the set of neighbor vertices of vertex \(v\). **Theorem 3** (Pruning rule). : _For a vertex \(v\in V\), where \(w(v)\leq w(v_{i})\forall v_{i}\in N(v)\), a participating clique \(C_{j}\) of vcan be safely ignored when making the branching decision if it is subsumed by another participating clique \(C_{k}\),i.e., \(V_{C_{j}}\subset V_{C_{k}}\). Stated another way, allocating zero weight to the clique \(C_{j}\) will not eliminate the possibility of finding the optimal solution in the pruned search tree._  
Proof. : Suppose in one optimal allocation, vertex \(v\) allocates \(w^{*}(0<w^{*}\leq w(v))\) to clique \(C_{j}\). We use \(V_{C_{k}}-V_{C_{j}}\) to denote the difference vertices set between clique \(V_{C_{k}}\) and \(V_{C_{j}}\). For each \(v_{l}\in V_{C_{k}}-V_{C_{j}}\), we assert that \(v_{l}\) must allocate at least \(w^{\prime}=w^{*}+w(v_{l})-w(v)\geq w^{*}\) to some of its participating cliques that do not have vertex \(v\) involved. The reason is stated as below: for every unit of weight of \(v_{l}\), its allocation may either fall in a clique that involves \(v\) or fall in a clique that does not involve \(v\). With \(w(v_{l})\geq w(v)\), \(v_{l}\) can allocate at most \(w(v)\) to cliques that involve \(v\). Furthermore, with our assumption that \(v\) has allocated \(w^{*}\) to \(C_{j}\), where \(v_{l}\) is not part, \(v_{l}\) can then allocate at most \(w(v)-w^{*}\) to cliques that involve \(v\). Therefore, \(v_{l}\) must allocate at least \(w(v_{l})-(w(v)-w^{*})\) to cliques that do not involve \(v\), just as we have asserted. Consider the following reallocation: For each \(v_{l}\), we withdraw \(w^{*}\) weights from cliques that do not involve \(v\). This withdrawal either shrinks the vertex set for some cliques or it totally eliminates some cliques with only one vertex \(v_{l}\) inside. In fact, the latter case will never happen if the prior allocation is optimal. Then, these withdrawn weights are merged into the weighted clique \(C_{j}\) with \(w^{*}\) weights, yielding a weighted clique \(C_{k}\) with \(w^{*}\) weights. This reallocation will never increase the sum of weights of weighted cliques, so the new allocation is also optimal. From a local view, the decision to allocate zero weight to clique \(C_{j}\) can therefore never go wrong, and the possibility of reaching optimality is preserved after the decision. In the following, we give several corollaries to further demonstrate the usage of this pruning rule. **Corollary 4** (One-degree vertex). : _In WCCP, if there exists a degree-one vertex \(v_{j}\) connecting to another vertex \(v_{k}\), allocating \(\min(w(v_{j}),w(v_{k}))\) to the two-vertex clique \((v_{j},v_{k})\) will not eliminate the possibility of finding optimal solution in this branch._  
Proof. : The vertex \(v_{j}\) has only one neighbor \(v_{k}\), so its participating cliques are \((v_{j})\) and \((v_{j},v_{k})\). Since the former clique is subsumed by the latter one, we can allocate zero weight to the one-node clique \((v_{j})\) if \(w(v_{j})\leq w(v_{k})\). For the cases when \(w(v_{j})>w(v_{k})\), we can allocate at most \(\min(w(v_{j}),w(v_{k}))\) to the clique \((v_{j},v_{k})\). Following the same reallocation-based logic in the proof of Theorem 3, we can assert that this decision will not eliminate the possibility of finding the optimal solution either.