## 3 The Static Form of the Problem
### Weighted Clique Cover Problem  
Consider an isolated scenario with only one node. This node has multiple queues of packets. Packets from some of the queues can be coded together, while others cannot. This relationship is depicted in a coding graph, where each vertex represents one queue and each edge represents a coding-possible relationship between two queues. A set of \(k\) packets can be coded and sent in one transmission if and only if they come from \(k\) distinct queues (\(k\) vertices) and each pair of queues is coding-possible (\(\binom{k}{2}\) edges). The objective is to find a scheduling algorithm that minimizes the number of transmissions, either coded or non-coded, to empty all queues. This problem is called static in the sense that no new packets would arrive.  
This problem is mathematically formulated as a weighted clique cover problem as below:  
**Definition 1** (Weighted clique cover problem).: _Given a graph \(G=\{V,E\}\), where V is the set of vertices, \(E\) is the set of edges and a weight function \(w:V\rightarrow\mathbb{Z}^{+}\) that maps each vertex to a positive integer, we define a weighted clique w.r.t. the graph as \(C=\{V_{c},w_{c}\}\), where \(V_{c}\) is a set of vertices that are fully connected in \(G\) (i.e., \(V_{c}\) is the vertex set of a clique in \(G\)) and \(w_{c}\) is a positive integer that satisfies:_  
\[\forall v\in V_{c},w_{c}\leq w(v)\]  
_We then further define a weighted clique cover w.r.t. the weighted graph as a set of weighted cliques \(\mathbf{C}=\{C_{i}=\{V_{c_{i}},w_{c_{i}}\},i=1,2\ldots,n\}\), such that:_  
\[\bigcup_{i=1,2,\ldots,n}V_{c_{i}}=V\] \[\forall v\in V,w(v)=\sum_{c_{i}:v\in V_{c_{i}}}w_{c_{i}}\]  
_The problem is to find a weighted clique cover w.r.t. the weighted graph that minimizes \(\sum_{i=1,\ldots,n}w_{c_{i}}\)._  
As one of the 21 Karp's NP-complete problems [14], the clique cover problem (CCP) is NP-complete. WCCP, as a generalized form of CCP, is known to be NP-complete, as well, and researchers have been working on a practical solution to it. It is shown by [PERSON] [15, 16] that for a special class of graphs, known as claw-free perfect graphs, the WCCP problem can be solved in polynomial time. A claw is the shape shown in Figure 1a. It is often referred to as \(K_{1,3}\), because it is essentially 1,3-bipartite. A claw-free graph is a graph where none of its sub-graphs is a claw. A perfect graph was an idea raised in the 1970s by [PERSON] [17]. Mathematically, a graph is said to be perfect if, for each of its induced sub-graphs, the chromatic number equals the size of its largest clique of the subgraph. Take Figure 1b as an example. Nodes \(A\), \(B\), \(D\), \(E\) can form a sub-graph. The corresponding induced sub-graph contains the four nodes, as well as the four edges that connect them. In this induced sub-graph, the chromatic number is three, because we can color Nodes \(A\) and \(E\) as red, Node \(D\) as green and Node \(B\) as green, such that no adjacent nodes have the same color. The size of the maximum clique in this sub-graph is also three, as Nodes \(A\), \(B\) and \(D\) form a three-node clique. The simplest imperfect graph is a ring of five nodes shown in Figure 1c. The size of the maximum clique is two, but the chromatic number is three. A more recent paper [18] summarizes the problem and some recent advances on the topic.  
**Figure 1.** There exists polynomial solutions to the weighted clique cover problem (WCCP) for claw-free perfect graphs. (**a**) Illustration of a claw; (**b**) an example of a perfect graph; (**c**) an example of an imperfect graph.