## 2 Materials and Methods
### Random Tree Pruning Based Search  
With a large number of lines, we will obtain the combinatorial explosion of paths in the tree of mutually acceptable interfering line sets. To mitigate that, we can randomly prune the tree, by not choosing more than the given amount of nodes in the current layer. We need to set the maximal number of nodes to not be less than the number of lines, so that the first layer has all lines, and we are guaranteed to have the sets covering all lines. The second reason to make the maximum number of nodes equal to the number of lines owes to the fact that the number of sets in the minimum set cover over the full tree is always equal to or less than the number of lines. This means that the pruned tree needs to accommodate the number of leaf nodes to be more than or equal to the number of lines to guarantee the possibility of finding the min set cover over the pruned tree equal to the one over the full tree. The higher the maximum number of nodes per layer, the higher the probability of randomly creating the pruned tree which gives the same minimal set cover as the full tree. Let us define the pruning scale factor which can be any natural number starting from one. If the pruning scale factor equals one, then the maximum number of nodes per layer is equal to the number of lines. The pruning scale factor cannot be less than one. So, instead of using the full tree for finding min set cover, we need to find the pruned tree which gives the same min set cover. We can use the pruning information to represent the pruned tree. With the optimization of pruning information, we can find the best tree. We represent the pruning information for each layer with two elements: the number of layer nodes before pruning, and the set of indices chosen to be left after pruning. To prune, we first find all nodes of the next layer. Then we randomly sample the nodes with one of the following distributions of choice: uniform, linear, or Pareto. Before sampling, we collect nodes of the next layer into the next layer node list and sort nodes by the identifier of their line in increasing order. To sample only unique nodes and to decrease the number of sampling operations if most of the nodes were chosen, we do the following: if the node was already chosen, we traverse to the end of the next layer node list until we find a not chosen node. If we reach the end of the list without finding an eligible node, we traverse backwards from the first chosen node to the start of the list. If the number of nodes in the layer is less than the maximum allowed number of nodes, then we take them all without sampling. With the uniform distribution, we sample nodes with equal probability. With linear and Pareto distributions, we choose nodes having lower line identifiers with higher probability than nodes having higher line identifiers. This is realized because nodes with lower identifiers can have more children with higher probability, hence larger concurrently transmitting line sets. We use the scale parameter for the linear and Pareto distribution, which shows how many times the probability of choosing the first node in the list having the lowest line identifier is higher than choosing the last node having the highest line identifier. For the Pareto distribution, we set the parameter \(\beta=1\). And the parameter \(\alpha\) is variable. Thus, we can generate randomly pruned trees. However, pruned trees do not always contain all the line sets of the smallest minimum set cover, unlike the complete tree. Thus, we need to perform the heuristic optimization to find the pruned tree which gives us the smallest minimum set cover. We will use two ways to perform optimization: random search and genetic algorithm (GA) search. Both approaches have the following common parameters: batch size (for the GA it is the population size), minimal number of iterations and the number of iterations after the best found solution has not improved. It is floating and represented in the ratios of the number of iterations that have happened.