In this work we study a graph problem called edge packing in a distributed setting. An edge packing p is a function that associates a packing weight p(e) with each edge e of a graph such that the sum of the weights of the edges incident to each node is at most one. The task is to maximise the total weight of p over all edges. We are interested in approximating a maximum edge packing and in finding maximal edge packings, that is, edge packings such that the weight of no edge can be increased.
We use the model of distributed computing known as the LOCAL model. A communication network is modelled as a graph, where nodes correspond to computers and edges correspond to direct communication links. All nodes start at the same time and they run the same algorithm. Computation proceeds in synchronous communication rounds, during each of which each node can send a message through each of its communication links, receive a message from each of its communication links, and then do unbounded local computation. When a node terminates the algorithm, it must produce a local output – in this case a packing weight for each incident edge. The local outputs of the nodes must together form a feasible global solution.
The running time of an algorithm is the number of steps it takes until all nodes have terminated and announced their outputs. In a typical distributed algorithm, the running time of an algorithm is a function of n, the size of the communication graph, and ∆, the maximum degree of the communication graph. In this work we are interested in deterministic algorithms that have a running time that is a function of ∆, but not of n.
In this work we will review an O(log ∆)-time constant-approximation algorithm for maximum edge packing, and an O(∆)-time algorithm for maximal edge packing. Maximal edge packing is an example of a problem where the best known algorithm has a running time that is linear-in-∆. Other such problems include maximal matching and (∆ + 1)-colouring. However, few matching lower bounds exist for these problems: by prior work it is known that finding a maximal edge packing requires time Ω(log ∆), leaving an exponential gap between the best known lower and upper bounds. Recently Hirvonen and Suomela (PODC 2012) showed a linear-in-∆ lower bound for maximal matching. This lower bound, however, applies only in weaker, anonymous models of computation. In this work we show a linear-in-∆ lower bound for maximal edge packing. It applies also in the stronger port numbering model with orientation.
Recently Göös et al. (PODC 2012) showed that for a large class of optimisation problems, the port numbering with orientation model is as powerful as a stronger, so called unique identifier model. An open question is if this result can applied to extend our lower bound to the unique identifier model.
