# Lossless Image Compression Using Multi-level Dictionaries: Binary Images

Samar Agnihotri, Renu Rameshan, and Ritwik Ghosal
Correspondence Email<EMAIL_ADDRESS>
###### Abstract

Lossless image compression is required in various applications to reduce
storage or transmission costs of images, while requiring the reconstructed
images to have zero information loss compared to the original. Existing
lossless image compression methods either have simple design but poor
compression performance, or complex design, better performance, but with no
performance guarantees. In our endeavor to develop a lossless image
compression method with low complexity and guaranteed performance, we argue
that compressibility of a color image is essentially derived from the patterns
in its spatial structure, intensity variations, and color variations. Thus, we
divide the overall design of a lossless image compression scheme into three
parts that exploit corresponding redundancies. We further argue that the
binarized version of an image captures its fundamental spatial structure and
in this work, we propose a scheme for lossless compression of binary images.

The proposed scheme first learns dictionaries of $16\times 16$, $8\times 8$,
$4\times 4$, and $2\times 2$ square pixel patterns from various datasets of
binary images. It then uses these dictionaries to encode binary images. These
dictionaries have various interesting properties that are further exploited to
construct an efficient scheme. Our preliminary results show that the proposed
scheme consistently outperforms existing conventional and learning based
lossless compression approaches, and provides, on average, as much as
$1.5\times$ better performance than a common general purpose lossless
compression scheme (WebP), more than $3\times$ better performance than a state
of the art learning based scheme, and better performance than a specialized
scheme for binary image compression (JBIG2).

##  I Introduction

Lossless compression of images strives to exploit various redundancies in
images to reduce their sizes with the constraint of the reconstructed image
having the same quality and information content as the original image.
Applications in various domains such as medical, forensics, document analysis,
data archival may require relevant images to be losslessly compressed to
reduce storage and transmission costs without any loss of information. In the
past few decades numerous schemes and commercial standards have been developed
towards this end, such as GIF [1], PNG [2], TIFF [3], JPEG-LS [4], WebP [5],
and JPEG-XL [6] and are used billions of times everyday to store and transmit
images.

All existing schemes for lossless image compression are broadly of three
types: universal source coding based, prediction based, and those based on
learning a distribution. Schemes based on universal source coding, such as [7,
8, 9, 10, 11], based on variants of Lempel-Ziv coding, linearize an image in
rows or strips of pixels or create a “front” of pixels which are already
explored and then use some universal source coding scheme to compress those
losslessly. Prediction based schemes such as [4, 5, 6], on the other hand
divide an image in various segments based on some complexity heuristic, and
then use prediction and entropy coding over the prediction error. Finally, the
distribution learning based methods, such as [12], attempt to estimate the
probability distribution of pixel values or their residues using self-
supervised learning.

Impressive as many of these schemes are for their usage and performance, all
these schemes are based on heuristics, drawing upon some general theoretical
principles and empirical results. However, many that perform well are too
complex to be amenable for rigorous performance analysis and those that are
simple enough for analysis do not perform too well. Further, given their
heuristic nature, none of these schemes consistently perform better than all
other schemes over all types of images and no guarantees of their respective
performance can be given.

In our pursuit of developing a lossless image compression scheme that performs
better than all other schemes over all types of images, is amenable for
rigorous performance analysis, and can provided guaranteed compression for a
given type of images, we step back and ask the most basic question related to
image compression: where does the information lie in an image? In other words,
in an image where do the patterns, redundancies, or correlations lie that can
be exploited to reduce the size of the compressed image?

The reader may recall that in the RGB color space, the color of each image
pixel is encoded by $24$ bits, with $8$ bits used to represent the intensities
of each of the R, G, and B components. While a pixel in a color image is
represented using $24$ bits, a grayscale image uses $8$ bits, and a binary or
bilevel image uses only two bits. In this work, we hypothesize that a RGB
image has information in its spatial structure, and intensity and colors
variations with core information captured by its spatial structure and then
intensity and colors variations adding further layers of information in that
order. We argue that the primary spatial structure of an image is captured by
its binary version111It should be noted that further spatial structure may
appear in a binary image when intensity and colors are added to it. However,
such secondary structures can be addressed by considering patterns in
intensities and colors of the neighboring pixels. and the primary intensity
variations in an image are captured by its grayscale version222Patterns in
intensity variations in a grayscale image may appear when color is added to
them and those can be exploited using the correlation among their color
values.. Therefore, overall compressibility of a RGB image can be considered
as a function of its compressibilities with respect to its spatial structure,
and its intensity and color variations. In other words, the overall
compressibility of a color image can be understood and explained in terms of
the compressibilities of its binary and grayscale versions and color
variations.

In this work, as the first part of our effort to develop a lossless color
image compression scheme, we discuss the design of a lossless binary image
compression scheme. We strive to provide an introduction to this new approach
for lossless binary image compression and report its performance compared to
existing conventional and learning based approaches. However, we assert that
the current implementation of the proposed scheme only provides a proof of the
concept. There exist various opportunities to optimize it to improve its
compression performance as well as computational requirements. We plan to
exploit such opportunities in our immediate work. Still, it is encouraging to
note that even in its not fully optimized form, the proposed scheme
outperforms all existing commercial and/or state-of-the-art schemes for
lossless image compression and provides competitive performance with respect
to a specialized scheme for binary image compression. This points to
significant potential of such schemes for the lossless image compression.

The proposed scheme to encode a binary image includes two major steps: multi-
level dictionary learning and image encoding. We propose to cover an image
with square pixel blocks of sizes $16\times 16$, $8\times 8$, $4\times 4$, and
$2\times 2$. Therefore, we first create dictionaries of patterns for each of
these block-sizes from given datasets of binary images and then use these
dictionaries to encode a binary image. We provide the details in Section II.

We plan to introduce schemes for lossless compression of grayscale and color
images in our upcoming work. Though those schemes follow the same general
approach as the scheme introduced in this work for binary images, yet those
introduce major innovations to manage the computational costs while providing
better compression performance than the existing schemes.

###  I-A Contributions

  * •

We introduce a new paradigm for the lossless compression of color images where
the overall compression scheme is developed in a layered manner by
successively exploiting the patterns in spatial structure, and intensity and
color variations.

  * •

We argue that the fundamental spatial structure of an image is captured by its
binarized version.

  * •

We provide a multi-level dictionary learning based approach to compress and
decompress binary images.

  * •

Our results establish that the proposed scheme consistently outperform major
conventional and learning based lossless compression schemes and provides, on
average, as much as $1.5\times$ better performance than a common general
purpose lossless compression scheme (WebP), more than $3\times$ better
performance than a state of the art learning based scheme [12], and better
performance than a specialized scheme for binary image compression (JBIG2).

###  I-B Related Work

Though we approach lossless compression of binary images as a first step in
developing an effective scheme for lossless compression of grayscale and color
images, in literature lossless compression of binary images has been widely
addressed for its own importance in processing and storing text, maps,
seismograms, fingerprints, logos, silhouettes, line drawings, facsimile etc.
Accordingly a lot of work exists for lossless compression of binary images. A
facsimile standard, called JBIG2 [13], segments an image into different
regions and uses different coding schemes to encode them. However, this
requires a good segmentation algorithm. A scheme for lossless compression of
binary and grayscale images, called Block Arithmetic Coder for Image
Compression (BACIC) [14], uses variable-to-fixed block arithmetic coder to
encode symbols whose probability distribution is estimated using a single
context model throughout the whole image. However, this may result in poor
compression for images which may have regions with widely different context,
such as text and halftone. The authors in [15] propose a scheme that
adaptively weighs different context models based on their relative accuracy in
real-time, where the weighting factors are updated in a pixel-by-pixel manner
using the relative accuracy of the corresponding context models. However, this
scheme in spite of its higher complexity achieves only a marginal performance
gain with respect to simpler BACIC. In [16], a lossless compression algorithm
is proposed that creates a context for each pixel by rearranging a 2-D image
into a corresponding 1-D string and encodes it using hierarchical enumerative
coding. However, its compression performance depends on scanning order of the
2-D images to create the corresponding 1-D strings and this may lead to
substantially poor compression performance as it may create spurious long-
range correlations by putting nearby pixels far away.

###  I-C Organization

The paper is organized as follows. We provide the details of the proposed
method, such as dictionary learning and encoder design in Section II. In
Section III, we provide a description of datasets used for dictionary
learning, some interesting statistical properties of these dictionaries, and
results comparing the compression ratios of the proposed scheme with those of
various other major schemes. Finally, Section IV concludes the paper and
provides some directions for further work.

##  II The Proposed Method

In this work, we take an approach that is very different from context-modeling
approach adopted by most of the existing work on lossless compression of
binary images. One of the major results of [17] is that the 2-D entropy
density of an infinite 2-D lattice monotonically decreases to a limit as the
side-lengths of rectangular blocks covering the lattice tend to infinity,
while keeping the ratio of the side-lengths finite. Motivated by this, we
propose to cover an image with non-overlapping pixel squares of side-length
$2^{m},m\geq 1$. Then each of these squares is replaced by its corresponding
entropy code obtained from the dictionary of all $2^{m}\times 2^{m}$ patterns
with their respective frequencies, learned a priori over a given collection of
binary images. Next, we provide the details of multi-level dictionary learning
and encoder design.

###  II-A Multi-level dictionary learning

We use multi-level dictionaries to compress a given image. Dictionaries
contain string representation of image patches and their frequencies. As our
focus is on binary images, the patches are represented using hex strings.
Multi-level refers to the four patch sizes that are being used. To capture the
statistics at a very small scale, we use $2\times 2$ patches and we capture
the statistics at increasingly higher levels by considering square patches of
sizes $4,\,8,$ and $16$.

The statistics of $n\times n$ patches, where $n=2,\,4,\,8,\,16$ are learned
from a wide variety of images, derived from various publicly available
datasets. While for patch sizes $2$ and $4$, the number of patches are small
enough to be handled without any special considerations in coding, the case
for sizes $8$ and $16$ are not so. Despite the combinatorial explosion, we
processed several giga bytes of data and have come up with interesting
observations and exploited those to design an efficient encoder. Specific
details of the datasets used, processing steps, and corresponding observations
are recorded in Section III.

As a first step in creating the dictionary, the RGB input images are binarized
using Otsu’s thresholding [18]. Dictionaries are created separately for each
patch size. For each value of $n$, all possible patches of size $n\times n$
are read from an image, binarized, converted to a hex string, and are stored
in an array. The order in which bits are read from a patch to form the hex
string is shown in Figure 1. For $2\times 2$ patches the bits are read out in
a zig-zag manner. A $4\times 4$ patch is formed by arranging four $2\times 2$
patches, again in a zig-zag manner. This process is repeated for larger size
patches as illustrated in Figure 1.

$b_{1}$$b_{2}$$b_{3}$$b_{4}$$B_{2}=\text{Hex}(b_{1}b_{2}b_{3}b_{4})$$B_{2}^{1}$$B_{2}^{2}$$B_{2}^{3}$$B_{2}^{4}$$B_{4}=B_{2}^{1}B_{2}^{2}B_{2}^{3}B_{2}^{4}$$B_{4}^{1}$$B_{4}^{2}$$B_{4}^{3}$$B_{4}^{4}$$B_{8}=B_{4}^{1}B_{4}^{2}B_{4}^{3}B_{4}^{4}$
Figure 1: The bits ($b_{i}$) or blocks $B_{n}^{i}$ are read in a raster scan
order; here $n$ indicates the patch size and $i$, the bit or the block.

Patches are extracted from images and stored in an array. To ensure that
patches are picked in an independent manner for counting their respective
frequencies, the array of image patches is shuffled across an image, across
images in a dataset, and across datasets.

###  II-B Multi-level image encoding

Having constructed dictionaries of all unique $16\times 16$, $8\times 8$,
$4\times 4$, and $2\times 2$ patches that occur in the training data along
with their respective frequencies, we next use these dictionaries to compress
a given image as follows. To keep the exposition simple, here we discuss the
encoding only for the images with side-lengths that are a multiple of $16$,
though the description can be easily extended to images with arbitrary side-
lengths.

To compress a given image, we start with the largest available patch size,
which is $16\times 16$ in this work. We divide the entire image in terms of
$16\times 16$ non-overlapping patches. Among all these patches, we find the
ones which occur in the corresponding $16\times 16$ dictionary. Using
frequencies of those patches, we construct the corresponding canonical Huffman
codes (CHCs) and replace these patches in the image by the corresponding CHCs.
Each of those $16\times 16$ patches in the image which are not found in the
$16\times 16$ dictionary are divided into four $8\times 8$ patches. Among all
such $8\times 8$ patches, we find the ones which occur in the corresponding
$8\times 8$ dictionary, construct CHCs for those, and replace those patches in
the image by the corresponding CHCs. Further, each of those $8\times 8$
patches in the image which are not found in the $8\times 8$ dictionary are
divided into four $4\times 4$ patches and the same process as for $8\times 8$
patches is repeated, but now for $4\times 4$ patches. Lastly, the same goes
for $2\times 2$ patches.

In Figure 2, we provide an example of compressing a $32\times 32$ image
successively with smaller block sizes, starting with the block size of
$16\times 16$.

Figure 2: Illustration of hybrid encoding for a $32\times 32$ patch.

A small header is prefixed to the compressed image to help the decoder know
the original image size, identities of patterns from various dictionaries for
which the CHCs are created and which are subsequently used to encode the
corresponding patches, and the identities of the patches in the original image
so encoded. However, we skip the details of this header to keep the discussion
simple.

For decompression, we follow the reverse process of compression and recreate
the original image by referring to the dictionaries, which are shared a priori
with the decoder, to find the patterns corresponding to codes in the
compressed image and use those to replace the codes in the compressed image to
reconstruct the original image.

##  III Results

We compare the proposed method with widely used lossless compression
algorithms both from engineered solution category like PNG [2], WebP [5],
JPEG-XL [6], JBIG2 [13], and also a deep learning based model [12]. Binary
images are given as input to all the algorithms.

###  III-A Deep learning based model

As we are proposing a learning based method, we compare the performance of the
proposed scheme with that of a recent deep learning based lossless compression
scheme [12]. This method uses a convolutional neural network along with the
lossy compression scheme BPG [19] for achieving lossless compression. BPG
itself is based on the HEVC video coding standard [20].

In [12], the CNN model learns the conditional distribution of natural images,
given as side information the residual image obtained as the difference of the
actual image and the image reconstructed from the BPG format. Two sub-networks
are learned: a Q-Classifier network which provides the quantization parameter
to BPG and a residual compressor, which predicts the conditional probabilities
($p$). Once $p$ is learned, an arithmetic encoder uses this to generate the
bit stream.

We retrain the network using binary images. As in [12], for training we use
the Open Images [21] dataset. This requires around $190$ Gb of data.

###  III-B Datasets

For dictionary learning, we use various datasets from ImageNet [22] to the
recent SAM [26] dataset. While some of them are class specific, SAM brings in
variety by having images across several domains.

The class specific datasets that we use are ImageNet [22], 256 Object
Categories [23], iNaturalist7 [24], and DTD [25]. The first two contain images
for object categorization, the third one contains fine-grained images of
plants and animals; DTD is different in the sense that it has different
classes of textures images. As mentioned before, to avoid any bias in the way
patches are sampled from images, we create new sets of images by randomly
sampling images from across classes, and across datasets. We restructure the
above datasets and create $732$ directories each with $1132$ images. This
amounts to $88$ GB of data. Let us call this combined dataset as D1 to
distinguish it from the SAM dataset described next.

From the SAM training data we use $50$ directories. We do not mix the images
in this case as SAM being a segmentation dataset, the images are diverse
within and across directories. Each directory has around $11$ GB of data.
Sample images from these datasets are shown in Figure 7.

For $8\times 8$ and $16\times 16$ patches, as the total number of possible
patches are huge, $2^{64}$ and $2^{256}$, respectively, the number of observed
patches are also quite high despite the fact that many patches repeat with a
high frequency. We processed roughly 638 Gb of data which amounts to a huge
number of patches. A large fraction of these patches are quite rare. In the
next subsection, we provide more insights into the observed statistics of
these learned dictionaries. We process the unit frequency patches and patches
with frequency greater than one, separately. This separation is maintained for
all type of processing for patches of size $8$ and $16$.

###  III-C Statistical properties of dictionaries

Natural images and other types of images exhibit local similarity or
smoothness. They are usually modeled as a Markov Random Field (MRF) due to
similarity among neighboring pixels [27]. This means that for a pixel we
expect the neighborhood pixels also to have similar values. When we quantize
images to the level where each pixel is represented by a bit, wherever pixels
in the RGB image have similar values, the neighboring pixels in the binary
image would take the same value - either $0$ or $1$. Wherever there is an edge
or other significant fluctuation of intensity in the RGB image, the binary
values would exhibit a variation. This can be observed in the statistics that
we have extracted.

Another consequence of the MRF nature of natural images is that, when we come
to patches of size $n=8,\,16$, though the number of possible patches is huge
($2^{64}$ and $2^{256}$), we see only a tiny fraction of patches in the
binarized version of naturally occurring images. Below we give our
observations on the statistics of the patches of different sizes.

####  III-C1 Dictionary for $2\times 2$ patterns

There are only $16$ patterns of size $2\times 2$ and as expected the frequency
of the all zero and all ones patterns are both very high compared with the
frequencies of other patches. Figure 3 shows the frequency plot obtained from
the combined dataset (D1 and SAM).

Figure 3: Pattern frequencies for $2\times 2$ in a log-linear scale. Vertical
bars represent the count of symbols lying in the particular frequency range.
The frequency corresponding to the center of the interval is indicated along
the X-axis.

The X-axis shows frequency intervals in log scale and the Y-axis gives the
number of symbols lying in each interval. It is observed that two symbols lie
at the extreme right interval indicating that they both are of high frequency.
These are the all zero and all one patches. Similarly, we observe two symbols
lying in the lowest frequency range and these correspond to symbols $6$ or
$(0110)_{2}$ and $9$ or $(1001)_{2}$. In these two patches, the binary value
of the pixel changes with the highest spatial frequency.

####  III-C2 Dictionary for $4\times 4$ patterns

For $4\times 4$ patches, there are $65,536$ possible patterns and during
dictionary learning, we encounter all those in the training data. The number
of patches (log scale) in each frequency interval (selected in a logarithmic
manner) is shown in Figure 4(a) and the cumulative sum of frequencies is shown
in Figure 4(b).

(a) Number of patterns in normalised frequency intervals in log-log scale.

(b) Cumulative sum plot.

Figure 4: Statistics for $4\times 4$ patterns.

From Fig. 4(a), it is seen that similar to the case of $2\times 2$, two
patterns occur with high frequencies. These are again the all zero and all one
patches. Many of the patterns cluster at lower frequency intervals showing
that majority of the patterns are relatively rare. This trend is seen in
Figure 4(b) too. It shows the symbol count along the X-axis and the cumulative
frequency as a percentage along the Y-axis. The inset zoom on the initial
region shows that only $97$ symbols contribute towards $90\%$ of the total
frequency, and that $95\%$ of the total frequency is accounted for by only
$864$ symbols. The rest of the $64,672$ patches contribute only towards $5\%$
of the total frequency.

####  III-C3 Dictionary for $8\times 8$ patterns

Unlike in $2\times 2$ and $4\times 4$, the number of patterns in this case is
huge. However, the log-log frequency histogram plot in Figure 5(a) shows that
most of the symbols are rare. The number of symbols in the lower frequency
intervals are much higher than those at the high frequency ranges. The number
of symbols occurring with unit frequency is $2,591,241,520$ and those with
frequency two is $105,638,640$. It may be noted that we have discarded the
unit frequency symbols while plotting both these graphs. It is seen from
Figure 5(b) that from among roughly $2\times 10^{8}$ number of symbols, only
around $20,000$ symbols contribute towards $90\%$ of the total frequency. This
validates our argument that relatively only a few high frequency patterns come
together to form an image. Further, as the probability of unit frequency
patterns is close to zero, we do not consider them in creating the dictionary.

(a) Number of patterns in normalised frequency intervals in log-log scale.

(b) Cumulative sum plot.

Figure 5: Statistics for $8\times 8$ patterns.

####  III-C4 Dictionary for $16\times 16$ patterns

It is observed from Figures 6(a) and 6(b), that the statistics of $16\times
16$ patterns also follow the trend of the statistics of $8\times 8$ patterns.
They differ only in the number of patterns seen, which is smaller compared to
that of $8\times 8$. The number of strings with unit frequency is
$2,248,110,545$ and the number of strings with frequency $2$ is $26,607,341$.
It may be noted that again we have discarded the unit frequency symbols while
plotting both these graphs. It is seen from Figure 6(b) that from among
roughly $5.5\times 10^{7}$ number of symbols, only around $10,000$ symbols
contribute towards $90\%$ of the total frequency. Again, as the probability of
unit frequency patterns is close to zero, we do not consider them in creating
the dictionary.

(a) Number of patterns in normalised frequency intervals in log-log scale.

(b) Cumulative sum plot

Figure 6: Statistics for $16\times 16$ patterns.

###  III-D Compression ratio comparison

We compare the performance of the proposed method to engineered solutions like
PNG [2], WebP [5], JPEG-XL [6], and JBIG2 [13], and a learning based solution
MGT [12] with respect to different datasets. Results on sample images
extracted from four different datatsets: ImageNet [22], SAM [26], iNaturalist
[24], and Kodak [28], are provided below. The Kodak image dataset contains
high-resolution true-color images for compression testing. Binarized
representative test images from each of these datasets are illustrated in
Figure 7.

(a) n06359193

(b) sa_6369140

(c) 4b474218

(d) kodim01

Figure 7: Sample images from each dataset. Left to right, ImageNet [22], SAM
[26], iNaturalist [24], and Kodak [28].

The compression ratios of the proposed scheme and the comparison pool is shown
in Table I. In the appendix, we provide comparison results over more images
from each of these four datasets. It can be observed from these results that
the proposed scheme consistently outperforms the general-purpose compressors,
such as PNG and JPEG-XL, by a large margin. Also, it outperforms WebP
by$1.5\times$, on average, though there are instances where the proposed
scheme is only slightly better than WebP and for a handful of cases, WebP
outperforms the proposed scheme by a small margin.

It can be observed that the proposed scheme comprehensive outperforms a state
of the art learning based scheme [12] and provides, on average, more than
$3\times$ better performance than it.

Further to address a potential concern that it may be unfair to compare the
performance of the proposed scheme with schemes which are not optimized for
lossless compression of binary images, we also compare the performance of the
proposed scheme with that of JBIG2 [13] \- a specialized scheme for binary
image compression. It can be seen from results in various tables that though
JBIG2 performs better than the proposed schemes for some binary images, the
proposed scheme, even in its yet-to-be-fully-optimized form, still performs
better than it, on average, across all datasets.

Lastly, to address another potential concern that it may not be fair to
compare the performance of the proposed scheme with that of JBIG2 over the
binarized versions of general images when JBIG2 is meant to compress images
corresponding to scanned documents and facsimile, we compare the performance
of the proposed scheme with that of JBIG2 over images from FigureQA [29] \- a
dataset of plots, graphs, and charts; and scanned document binary images from
various sources on the Internet, such as [30]. Our results show that the two
schemes still have comparable performance, even when JBIG2 is highly optimized
for such images and the proposed scheme is yet to be fully optimized.

Image | Proposed | MGT | PNG | WebP | JPEG-XL | JBIG2
---|---|---|---|---|---|---
| ImageNet |
n02910353 |  138.92 |  30.6 |  31.61 |  52 |  6.39 |  84.34
n03196217 |  339.28 |  93.3 |  61.9 |  195.64 |  18.79 |  292.64
n06359193 |  30.7 |  10.21 |  15.3 |  30.93 |  3.74 |  34.24
| SAM |
sa_6367649 |  40.76 |  13.88 |  16.75 |  32.36 |  4.7 |  45.8
sa_6367685 |  152.82 |  47.26 |  36.9 |  101.2 |  10.19 |  168.87
sa_6369140 |  45.00 |  13.25 |  18.45 |  32.01 |  4.42 |  51.42
| iNaturalist7 |
019397d5 |  25.31 |  7.36 |  9.16 |  16.7 |  2.22 |  24.8
3a099450 |  44.1 |  12.34 |  14.28 |  25.86 |  3.24 |  41.06
4b4742a8 |  22.26 |  6.66 |  8.24 |  15.51 |  2.10 |  21.96
| Kodak |
kodim01 |  22.75 |  7.48 |  11.03 |  20.38 |  2.39 |  24.09
kodim02 |  268.61 |  87.54 |  82.28 |  157.16 |  20.19 |  242.13
kodim03 |  77.82 |  22.48 |  25.71 |  47.38 |  6 |  75.91
TABLE I: Compression ratio comparison for four datasets. Only for one image
does WebP perform better than the proposed algorithm.

##  IV Conclusions and Future Work

We explore compression from a new perspective of the information contained at
different quantization levels (color, intensity, and binary) and provide a
scheme for lossless compression of binary images. The proposed multi-level
dictionary based encoder outperforms the existing conventional as well as
learning based image compression schemes by a large margin and has competitive
performance with respect to a specialized scheme for compression of binary
images.

Much work remains to be done. The current implementation of the proposed
scheme only provides a proof of the concept. There exists various
opportunities to optimize it to improve compression performance as well as
computational requirements. In near future, we plan to work in these
directions.

Also, we plan to formalize our work to extend the proposed multi-level
dictionary learning approach to develop schemes that exploit the patterns in
intensity and color variations in images to construct lossless compression
schemes for grayscale and color images.

## References

  * [1] Graphics Interchange Format, Version 89a,  https://www.w3.org/Graphics/GIF/spec-gif89a.txt, 1990.
  * [2] Information Technology - Computer graphics and image processing Portable Network Graphics (PNG): Functional specification, ISO/IEC 15948:2004,  https://www.iso.org/standard/29581.html.
  * [3] Tag Image File Format for Image Technology (TIFF/IT), ISO 12639:2004,  https://www.iso.org/standard/34342.html.
  * [4] Information Technology – Lossless and near-lossless compression of continuous-tone still images – Baseline, ISO-14495-1/ITU-T.87,  https://www.itu.int/rec/T-REC-T.87/en.
  * [5] “Compression Techniques — WebP — Google Developers”  https://developers.google.com/speed/webp/docs/compression.
  * [6] J. Alakuijala, R. Asseldonk, S. Boukortt, M. Bruse, I. Comsa, M. Firsching, T Fischbacher, E. Kliuchnikov, S. Gomez, R. Obryk, K. Potempa, A. Rhatushnyak, J. Sneyers, Z. Szabadka, L. Vandevenne, L. Versari, and J. Wassenberg, “JPEG XL next-generation image compression architecture and coding tools,” in Proc. SPIE Optical Engineering + Applications, San Diego, CA, 2019.
  * [7] J. A. Storer, “Loss image compression using generalized LZ1-type methods,” in Proc. IEEE DCC, Snowbird, UT, Apr. 1996.
  * [8] J. A. Storer and H. Helfgott, “Lossless image compressing by block matching,” The Computer J., vol. 40, no. 2-3, pp. 137-145, 1997.
  * [9] F. Rizzo, J. A. Storer, and B. Carpentieri, “LZ-based image compression,” Information Sciences, vol. 135, no. 1-2, pp. 107-122, 2001.
  * [10] Y. Wu, S. Lonardi, and W. Szpankowski, “Error-resilient LZW data compression,” in Proc. IEEE DCC, Snowbird, UT, Mar. 2006.
  * [11] S. H. Bae and B.-H. Juang, “Multidimensional incremental parsing for universal source coding,” IEEE Trans. Image Process., vol. 17, no. 10, pp. 1837-1848, 2008.
  * [12] F. Mentzer, L. V. Gool, and M. Tschannen, “Learning better lossless compression using lossy compression,” in Proc. IEEE/CVF CVPR, Seattle, WA, Jun 2020.
  * [13] F. Ono, W. Rucklidge, R. Arps, C. Constantinescu, “JBIG2-the ultimate bi-level image coding standard,” in Proc. IEEE ICIP, Vancouver, Canada, Sept. 2000.
  * [14] M. D. Reavy and C. G. Boncelet, “An algorithm for compression of bilevel images,” IEEE Trans. Image Process., vol. 10, no. 5, pp. 669-676, 2001.
  * [15] S. Xiao and C. G. Boncelet, “On the use of context-weighting in lossless bilevel image compression,” IEEE Trans. Image Process., vol. 15, no. 11, pp. 3253-3260, 2006.
  * [16] J. Im and J. Jeong, “Lossless compression of bi-level images based on context selection and hierarchical enumerative coding,” in Proc. IEEE ICIP, Thessaloniki, Greece, Oct. 2001.
  * [17] D. P. Feldman and J. P. Crutchfield, “Structural information in two-dimensional patterns: Entropy convergence and excess entropy,” Phys. Rev. E, vol. 67, no. 5, 051104, 2003.
  * [18] N. Otsu, “A threshold selection method from gray-level histograms,” IEEE Trans. on Systems, Man and Cybernetics, vol. 9, no. 1, pp. 62-66, 1979.
  * [19] F. Bellard. (2018). “BPG Image format,” http://bellard.org/bpg.
  * [20] G. J. Sullivan, J.-R. Ohm, W.-J. Han, and T. Wiegand, “Overview of the high efficiency video coding (HEVC) standard,” IEEE Trans. on Circuits and Systems for Video Tech. 22.12 (2012).
  * [21] A. Kuznetsova, H. Rom, N. Alldrin, J. Uijlings, I. Krasin, J. Pont-Tuset, S. Kamali, S. Popov, M. Malloci, A. Kolesnikov, T. Duerig, and V. Ferrari. “The Open Images Dataset V4: Unified image classification, object detection, and visual relationship detection at scale,” Int J. Comput. Vis,, vol. 128, pp. 1956-1981, 2020.
  * [22] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in Proc. IEEE/CVF CVPR, USA, Mar. 2017.
  * [23] G. Griffin, A. Holub, and P. Perona, “Caltech-256 object category dataset,” 2007.
  * [24] G. V. Horn, O. M. Aodha, Y. Song, Y. Cui, C. Sun, A. Shepard, H. Adam, P. Perona, and S. J. Belongie, “The iNaturalist Species Classification and Detection Dataset,” in Proc. IEEE/CVF CVPR, Salt Lake City, UT, Dec. 2018.
  * [25] M. Cimpoi, S. Maji, I. Kokkinos, S. Mohamed, and A. Vedaldi, “Describing Textures in the Wild,” in Proc. IEEE/CVF CVPR, Columbus, OH, Sept. 2014.
  * [26] A. Kirillov, E. Mintun, N. Ravi, H. Mao, C. Rolland, L. Gustafson, T. Xiao, S. Whitehead, A. C. Berg, W-Y. Lo, P. Dollar, R. Girshick, “Segment Anything,” in Proc. IEEE/CVF ICCV, Paris, France, Oct. 2023.
  * [27] A. Rangarajan and R. Chellappa. Markov Random Field Models in Image Processing, pp. 564–567. MIT Press, Cambridge, MA, USA, 1998.
  * [28] Kodak Lossless True Color Image Suite, https://www.kaggle.com/datasets/sherylmehta/kodak-dataset.
  * [29] S. E. Kahou, V. Michalski, A. Atkinson, Á. Kádár, A. Trischler, and Y. Bengio, “FigureQA: An annotated figure dataset for visual reasoning,” in Proc. ICLR workshop, Vancouver, Canada, Apr.-May 2018.
  * [30] ITU Reference Documents - Bi-level Images, https://www.itu.int/net/itu-t/sigdb/genimage/test24.htm.

We give results on more images from four datasets. In each row, number in
boldface corresponds to the scheme that provides the best compression ratio
among all six schemes.

Image | Proposed | MGT | PNG | WebP | JPEG-XL | JBIG2
---|---|---|---|---|---|---
n01518878 |  67.90 |  19.83 |  24.01 |  42.57 |  5.55 |  60.8
n02107142 |  64.98 |  21.79 |  26.97 |  48.09 |  6.89 |  61.03
n02454379 |  56.82 |  17.73 |  23.17 |  37.1 |  5.65 |  52.33
n02814860 |  18.47 |  6.59 |  9.85 |  16.49 |  2.49 |  18.39
n02910353 |  138.92 |  30.59 |  31.61 |  51 |  6.39 |  84.34
n02910353 |  22.54 |  8.15 |  12.17 |  20.52 |  3.10 |  22.92
n02910353 |  180.65 |  52.91 |  49.25 |  97.40 |  12.92 |  141.6
n03196217 |  339.28 |  93.30 |  61.89 |  195.64 |  18.79 |  292.64
n03796401 |  122.99 |  43.04 |  33.6 |  86.34 |  10.13 |  125.39
n06359193 |  30.70 |  10.21 |  15.34 |  30.93 |  3.74 |  43.24
1.TABLE: Compression ratio comparison for images from ImageNet dataset. Image | Proposed | MGT | PNG | WebP | JPEG-XL | JBIG2
---|---|---|---|---|---|---
sa_6366087 |  28.38 |  9.41 |  13.30 |  22.84 |  3.47 |  31.67
sa_6367580 |  31.39 |  9.86 |  16.34 |  27.58 |  4.87 |  39.34
sa_6367649 |  40.76 |  13.88 |  16.75 |  32.36 |  4.70 |  45.8
sa_6367685 |  152.82 |  47.26 |  36.90 |  101.2 |  10.1 |  168.87
sa_6369140 |  45.00 |  13.25 |  18.45 |  32.01 |  4.42 |  51.42
sa_6369201 |  44.68 |  13.68 |  18.38 |  32.39 |  4.51 |  48.4
sa_6372170 |  49.56 |  15.91 |  22.15 |  39.02 |  5.84 |  53.43
sa_6372464 |  141.75 |  42.42 |  49.56 |  85.55 |  11.3 |  151.26
sa_6375426 |  87.53 |  29.83 |  34.30 |  68.26 |  10.0 |  97.77
sa_6375657 |  170.47 |  62.99 |  66.77 |  143.8 |  18.0 |  199.45
2.TABLE: Compression ratio comparison for images from SAM dataset. Image | Proposed | MGT | PNG | WebP | JPEG-XL | JBIG2
---|---|---|---|---|---|---
019397d5 |  25.31 |  7.36 |  9.16 |  16.70 |  2.22 |  24.8
07515e5e |  36.29 |  10.4 |  12.08 |  22.15 |  2.91 |  34.15
3a099450 |  44.10 |  12.3 |  14.28 |  25.86 |  3.24 |  41.06
4b4742a8 |  22.26 |  6.66 |  8.24 |  15.5 |  2.10 |  21.96
4fc46e54 |  109.9 |  26.2 |  39.07 |  70.16 |  6.06 |  98.75
63af9699 |  15.80 |  5.28 |  7.39 |  13.0 |  2.01 |  16.27
662fb22c |  9.86 |  3.54 |  5.92 |  10.2 |  1.52 |  10.33
6dcb6418 |  12.18 |  4.17 |  6.43 |  10.9 |  1.60 |  12.73
70dbd589 |  244.35 |  64.04 |  48.91 |  113.8 |  14.4 |  196.05
79b7c4cb |  83.54 |  22.72 |  24.59 |  47.04 |  6.25 |  74.5
3.TABLE: Compression ratio comparison for images from iNaturalist dataset. Image | Proposed | MGT | PNG | WebP | JPEG-XL | JBIG2
---|---|---|---|---|---|---
kodim01 |  22.75 |  7.48 |  11.03 |  20.38 |  2.39 |  24.09
kodim02 |  268.61 |  87.54 |  82.28 |  157.1 |  20.1 |  242.13
kodim03 |  77.82 |  22.48 |  25.71 |  47.38 |  6.00 |  75.91
kodim04 |  55.40 |  17.60 |  21.46 |  38.52 |  5.33 |  53.32
kodim05 |  30.18 |  9.31 |  12.19 |  20.74 |  3.07 |  31.69
kodim06 |  39.10 |  13.02 |  22.00 |  37.93 |  4.62 |  39.97
kodim07 |  60.61 |  18.11 |  20.62 |  38.66 |  4.57 |  61.32
kodim08 |  36.88 |  11.99 |  12.69 |  26.98 |  3.71 |  37.45
kodim09 |  54.91 |  17.56 |  22.06 |  44.00 |  5.37 |  55.57
kodim10 |  70.08 |  21.20 |  23.35 |  42.62 |  5.93 |  68.21
kodim11 |  48.96 |  15.62 |  20.09 |  37.07 |  4.69 |  47.87
kodim12 |  185.10 |  56.14 |  49.37 |  109.78 |  13.27 |  166.12
kodim13 |  26.55 |  8.60 |  14.50 |  24.04 |  3.05 |  26.87
kodim14 |  31.64 |  9.87 |  14.74 |  24.51 |  3.14 |  31.93
kodim15 |  182.00 |  60.35 |  49.02 |  104.86 |  15.72 |  176.33
kodim16 |  40.80 |  13.35 |  22.81 |  38.18 |  4.65 |  40.86
kodim17 |  56.03 |  17.49 |  19.97 |  36.94 |  4.95 |  54.91
kodim18 |  30.10 |  9.70 |  13.95 |  23.52 |  3.29 |  29.78
kodim19 |  72.47 |  23.21 |  23.50 |  51.50 |  7.62 |  73.78
kodim20 |  198.11 |  59.15 |  58.53 |  123.50 |  15.47 |  189.59
kodim21 |  42.56 |  13.74 |  21.20 |  35.96 |  4.46 |  42.83
kodim22 |  48.47 |  15.49 |  19.85 |  35.06 |  4.72 |  46.32
kodim23 |  133.06 |  41.50 |  39.61 |  76.15 |  11.06 |  126.84
kodim24 |  60.88 |  19.62 |  27.77 |  45.98 |  8.11 |  59.49
4.TABLE: Compression ratio comparison for images from Kodak dataset.


11institutetext:

# Multi-Priority Graph Sparsification††thanks: Supported in part by NSF grants
CCF-1740858, CCF-1712119, and DMS-1839274.

Reyan Ahmed  Keaton Hamm  Stephen Kobourov  Mohammad Javad Latifi Jebelli
Faryad Darabi Sahneh  Richard Spence

###### Abstract

A _sparsification_ of a given graph $G$ is a sparser graph (typically a
subgraph) which aims to approximate or preserve some property of $G$. Examples
of sparsifications include but are not limited to spanning trees, Steiner
trees, spanners, emulators, and distance preservers. Each vertex has the same
priority in all of these problems. However, real-world graphs typically assign
different “priorities” or “levels” to different vertices, in which higher-
priority vertices require higher-quality connectivity between them. Multi-
priority variants of the Steiner tree problem have been studied in prior
literature but this generalization is much less studied for other
sparsification problems. In this paper, we define a generalized multi-priority
problem and present a rounding-up approach that can be used for a variety of
graph sparsifications. Our analysis provides a systematic way to compute
approximate solutions to multi-priority variants of a wide range of graph
sparsification problems given access to a single-priority subroutine.

###### Keywords:

graph spanners sparsification approximation algorithms

##  1 Introduction

A _sparsification_ of a graph $G$ is a graph $H$ which preserves some property
of $G$. Examples of sparsifications include spanning trees, Steiner trees,
spanners, emulators, distance preservers, $t$–connected subgraphs, and
spectral sparsifiers. Many sparsification problems are defined with respect to
a given subset of vertices $T\subseteq V$ which we call _terminals_ : e.g., a
_Steiner tree_ over $(G,T)$ requires a tree in $G$ which spans $T$. Most of
the corresponding optimization problems of these sparsifications are NP-hard
to compute optimally, so we often seek approximation algorithms or other
algorithms which yield good solutions in practice.

Different sparsifications can play a significant role in tackling real-world
network design problems containing a large number of nodes and edges. For
example, networks arising in real-world applications can be of vast scale, and
often contain millions of vertices and even more edges (social networks,
epidemiological networks, road networks, etc.). Visualizing such large
networks at once with all important information is impossible, hence it is
desirable to have a multi-priority structure for the network, in which low
priority vertices and edges capture finer detail, while higher priority
vertices and edges form a significantly sparser network, which nonetheless
still represents the underlying structure.

In this paper, we are interested in generalizations of sparsification problems
where each vertex possesses one of $k+1$ different _priorities_ (between 0 and
$k$, where $k$ is the highest), in which the goal is to construct a graph $H$
such that (i) every edge in $H$ has a _rate_ between 1 and $k$ inclusive, and
(ii) For all $i\in\\{1,\ldots,k\\}$, the edges in $H$ of rate $\geq i$
constitute a given type of sparsifier over the vertices whose priority is at
least $i$. Throughout, we assume a vertex with priority 0 need not be
included. This multi-priority problem has been studied in the context of
Steiner or multicast trees [10, 14, 17], where the objective is to connect a
source to a set of heterogeneous receivers, each with a certain priority
request. However, this generalization is far less studied for other types of
sparsifications. We investigate multi-priority generalizations of other graph
problems and provide approximation algorithms for these problems.

###  1.1 Problem definition

Here, we will consider a general range of sparsification problems. A
sparsification $H$ is valid if it satisfies a set of constraints that depends
on the type of sparsification. Given $G$ and a set of terminals $T$, let
$\mathcal{F}$ be the set of all valid sparsifications $H$ of $G$ over $T$.
Throughout, we will assume that $\mathcal{F}$ satisfies the following general
constraints that must hold for all types of sparsification we consider in this
article: for all $H\in\mathcal{F}$:

  * •

$H$ contains all terminals $T$ in the same connected component, and

  * •

$H$ is a subgraph of $G$.

Besides these general constraints, there are additional constraints that
depend on the specific type of sparsification as described below. Note that
$|\mathcal{F}|$ is usually too large to enumerate, but in many cases
$\mathcal{F}$ can be implicitly stated via constraints, and we will assume
that checking if $H\in\mathcal{F}$ can be done in polynomial-time. Several
such sparsification problems we focus on include:

Steiner trees: A Steiner tree over $(G,T)$ is a subtree that spans $T$. In
this case, we may let $\mathcal{F}$ be the set of all Steiner trees over
$(G,T)$. The specific constraint for this problem is the sparsification $H$
which is a Steiner tree over $(G,T)$; we denote this constraint by tree
constraint.

Subset spanners and distance preservers: A spanner is a subgraph which
approximately preserves pairwise distances in the original graph $G$. A
_subset spanner_ needs only approximately preserve distances between a subset
$T\subseteq V$ of vertices. Two common types of spanners include
_multiplicative_ $\alpha$-spanners, which preserve distances in $G$ up to a
multiplicative $\alpha$ factor, and _additive_ $+\beta$ spanners, which
preserve distances up to additive $+\beta$ error. A _distance preserver_ is a
special case of the spanner where distances are preserved exactly. The
specific constraints are basically the distance constraints applied from the
problem definition. For example, for multiplicative $\alpha$-spanners the
constraints are that the distance in $H$ between any pair of vertices is no
more than $\alpha$ times the distance in $G$. We denote these types of
constraints by distance constraints.

The above problems are widely studied in literature; see surveys [5, 21]. An
example sparsification which we will not consider in the above framework is
the _emulator_ , which approximates distances but is not necessarily a
subgraph.

In a standard weighted graph $G=(V,E)$, given a set of edges
$E^{\prime}\subseteq E$, the weight of the induced subgraph just depends on
the weight of edges in $E^{\prime}$. In this paper we study a problem where
the weight not only depends on the edge weights but also on the rate of the
edges. We denote the weight of the edge $e$ having rate $r$ by $w(e,r)$.
Different strategies can be used to increase the weight of the edge as the
rate increases. One natural setting is the linear increment: $w(e,r)=r\
w(e,1)$. We can set $w(e,1)=w(e)$, the input weight of $e$. It is also
possible to consider $w(e,1)=1$ if the graph is unweighted. We assess the
quality of a sparsification $H$ by $\text{weight}(H):=\sum_{e\in E(H)}$
$w(e,R(e))$. We define a $k$-priority sparsification as follows, where
$[k]:=\\{1,2,\ldots,k\\}$.

######  Definition 1 ($k$-priority sparsification).

Let $G(V,E)$ be a graph, where each vertex $v\in V$ has priority
$\ell(v)\in[k]\cup\\{0\\}$. Let $T_{i}:=\\{v\in V\mid\ell(v)\geq i\\}$. Let
$w(e)$ be the edge weight of edge $e$. The weight of an edge having rate $i$
is denoted by $w(e,i)=i\ w(e,1)=i\ w(e)$. For $i\in[k]$, let $\mathcal{F}_{i}$
denote the set of all valid sparsifications over $T_{i}$. A subgraph $H$ with
edge rates $R:E(H)\to[k]$ is a $k$-priority sparsification if for all
$i\in[k]$, the subgraph of $H$ induced by all edges of rate $\geq i$ belongs
to $\mathcal{F}_{i}$. We assess the quality of a sparsification $H$ by
$\text{weight}(H):=\sum_{e\in E(H)}$ $w(e,R(e))$.

Note that $H$ induces a nested sequence of $k$ subgraphs, and can also be
interpreted as a _multi-level_ graph sparsification [3]. A road map serves as
a good analogy of a multi-level sparsification, as zooming out only displays
highways and other major roads (Figure 1). Figure 2 shows an example of
2-priority sparsification with distance constraints where $\mathcal{F}_{i}$ is
the set of all subset $+2$ spanners over $T_{i}$; that is, the vertex pairs of
$T_{i}$ is connected by a path in $H_{i}$ at most 2 edges longer than the
corresponding shortest path in $G$. Similarly, Figure 3 shows an example of
2-priority sparsification with a tree constraint.

Figure 1: Three different zoom levels of a map of New York (_Map data:
Google_). Figure 2: _Right:_ A graph $G$ with $k=2$ priorities, with four and
three vertices of priority 1 and 2, respectively (indicated using small and
large circles). _mid:_ The subgraph $H_{1}$ with edges of rates 2 and 1
(indicated using the thickness) of a 2-priority sparsification with distance
constraints. _left:_ The subgraph $H_{2}$ with edges of rate 2 of the same
2-priority sparsification. Figure 3: _Right:_ A graph $G$ with $k=2$
priorities, with four and three vertices of priority 1 and 2, respectively
(indicated using small and large circles). _mid:_ The subgraph $H_{1}$ with
edges of rates 2 and 1 (indicated using the thickness) of a 2-priority
sparsification with a tree constraint. _left:_ The subgraph $H_{2}$ with edges
of rate 2 of the same 2-priority sparsification.

The linearly increasing $k$-priority instance is motivated by a natural large
network visualization problem. Semantic zooming features similar to the Google
map (Figure 1) are desirable while visualizing large networks. In semantic
zooming, when an object appears at a particular level, it should not suddenly
disappear after zooming in. In the context of network visualization, we can
say that if an edge appears at a particular rate or level, then it should also
appear in the lower levels. In other words, an edge can appear in multiple
levels and the total weight is the highest level of appearance times the edge
weight in level 1.

Definition 1 is intentially open-ended to encompass a wide variety of
sparsification problems. The $k$-priority problem is a generalization of many
NP-hard problems, for example, Steiner trees, spanners, distance preservers,
etc. These classical problems can be considered different variants of the
1-priority problem. Hence, the $k$-priority problem can not be simpler than
the $1$-priority problem. In this paper, we are mainly interested in the
following problem: how much harder is it to compute a $k$-priority
sparsification, compared to the corresponding 1-priority sparsification
problem?

We use the terms cost and weight interchangeably, as from an optimization
point of view the term “cost” is more intuitive. Let OPT be an optimal
solution to the $k$-priority problem and the cost of OPT be
$\text{weight}(\textnormal{OPT})$.

######  Problem.

Given $\langle G,P,w\rangle$ consisting of a graph $G$ with vertex priorities
$\ell:V\to[k]\cup\\{0\\}$, can we compute a $k$-priority sparsification whose
weight is small compared to $\text{weight}(\textnormal{OPT})$?

###  1.2 Related work

The case where $\mathcal{F}_{i}$ consists of all Steiner trees over $T_{i}$ is
known under different names including Priority Steiner Tree [17], Multi-level
Network Design [10], Quality-of-Service Multicast Tree [14, 22], and Multi-
level Steiner Tree [3].

Charikar et al. [14] give two $O(1)$-approximations for the Priority Steiner
Tree problem using a rounding approach which rounds the priorities of each
terminal up to the nearest power of some fixed base (2 or $e$), then using a
subroutine which computes an exact or approximate Steiner tree. If edge
weights are arbitrary with respect to rate (not necessarily increasing
linearly w.r.t. the input edge weights), the best known approximation
algorithm achieves ratio $O(\min\\{\log|T|,k\rho\\}$ [14, 30] where
$\rho\approx 1.39$ [13] is an approximation ratio for the edge-weighted
Steiner tree problem. On the other hand, the Priority Steiner tree problem
cannot be approximated with ratio $c\log\log n$ unless
$\text{NP}\subseteq\text{DTIME}(n^{O(\log\log\log n)})$ [17].

Ahmed et al. [7] describe an experimental study for the $k$-priority problem
in the case where $\mathcal{F}_{i}$ consists of all subset multiplicative
spanners over $T_{i}$. They show that simple heuristics for computing multi-
priority spanners already perform nearly optimally on a variety of random
graphs. Multi-priority variants of additive spanners have also been studied
[6], although with objective functions that are more restricted than our
setting.

###  1.3 Our contribution

We have extended the rounded-up approach provided by Charikar et al. [14]. The
original approach has several limitations:

  * •

The algorithm only ensures that for each priority the terminals are connected.
By removing the redundant paths, one can generate a tree-like structure, but
it is not obvious how to generate sparsifications for distance preservers or
spanners.

  * •

The algorithm computes a solution for different priorities independently.
However, we may need to satisfy constraints between different priorities. For
example, in graph spanners, we have to maintain the distance constraints
between pairs of vertices with different priorities. The independent solutions
approach does not easily handle distance constraints between different
priorities.

We generalize the algorithm to deal with these limitations and the result can
be applied not only Steiner trees but to other sparsifiers. Specifically:

  * •

We define a merging operation that can handle graph spanners, distance
preservers, and similar structures in addition to Steiner trees.

  * •

We propose different partitioning of the terminals that helps to satisfy the
distance constraints between different priorities and study the trade-offs
between different partitioning techniques.

  * •

We prove an approximation guarantee for all considered sparsifications using
proof by induction that is independent of the partitioning method.

##  2 A general approximation for $k$-priority sparsification

In this section, we generalize the rounding approach of [14]. The approach has
two main steps: the first step rounds up the priority of all terminals to the
nearest power of 2; the second step computes a solution independently for each
rounded-up priority and merges all solutions from the highest priority to the
lowest priority. Each of these steps can make the solution at most two times
worse than the optimal solution. Hence, overall the algorithm is a
$4$-approximation, we provide the pseudocode of the algorithm below.

Algorithm $k$-priority Approximation($G=(V,E)$)

// Round up the priorities

for each terminal $v\in V$ do

Round up the priority of $v$ to the nearest power of 2

// Independently compute the solutions

Compute a partition $S_{1},S_{2},\cdots,S_{k}$ from the rounded-up terminals

for each partition $S_{i}$ do

Compute a $1$-priority solution on partition $S_{i}$

// Merge the independent solutions

for $i\in\\{k,k-1,\cdots,1\\}$ do

Merge the solution of $S_{i}$ to the solutions of lower priorities

Independently computed solutions introduce some complicated situations for the
$k$-priority problem. For example, consider the most natural partitioning of
the terminals to different priorities: if $t_{i}$ and $t_{j}$ are two
terminals having priority $i$ and $j$ respectively (where $i<j$), then assign
$t_{i}$ to $S_{i}$ and $t_{j}$ to $S_{j}\setminus S_{i}$. Here, $S_{i}$ and
$S_{j}$ are the partitions having priority $i$ and $j$, respectively. In other
words, this is an exclusive partitioning: each terminal vertex is assigned to
exactly one set of terminals. In the second step, we can compute a solution
for each terminal set independently. Although exclusive partitioning is a
natural approach, it may generate invalid solutions. If we select a vertex
with the highest priority as a root and add it to each partition, then the
solution based on exclusive partitioning will satisfy the general constraints
mentioned in Section 1.1. It will also satisfy the additional constraints for
the Steiner tree after merging the solutions. However, it may not satisfy the
additional constraints of other types of problems: for example, in graph
spanners, we may need to satisfy the distance constraints between two terminal
vertices that belong to two different partitions.

We now propose two partitioning techniques that will guarantee valid
solutions. The first one is the inclusive partitioning: each terminal $t_{j}$
is assigned to each partition in $\\{S_{i}:i\leq\ell(t_{j})\\}$. In other
words, $S_{i}=T_{i}$ for all $i$.

######  Definition 2.

An inclusive partitioning of the terminal vertices of a $k$-priority instance
assigns each terminal $t_{j}$ to each partition in
$\\{S_{i}:i\leq\ell(t_{j})\\}$.

We propose another partitioning that is based on pairs of terminals. Consider
a pair of terminals $t_{i}$ and $t_{j}$ and w.l.o.g. let
$\ell(t_{i})\leq\ell(t_{j})$. Then we assign the priority to this pair equal
to $\min(\ell(t_{i}),\ell(t_{j}))$. We partition the pairs of terminals for
each priority and refer to it as the pairwise partitioning.

######  Definition 3.

A pairwise partitioning of the terminal vertices of a $k$-priority instance
assigns the priority of each pair of terminals $t_{i}$ and $t_{j}$ equal to
$\min(\ell(t_{i}),$ $\ell(t_{j}))$. Based on this assignment, we can create a
partitioning; $\forall kS_{k}=\\{(t_{i},t_{j}):min($
$\ell(t_{i}),\ell(t_{j}))=k\\}$.

We compute partitions $S_{1},S_{2},\cdots,S_{k}$ from the terminal sets
$T_{1},T_{2},$ $\cdots,T_{k}$ and use them to compute the independent
solutions. Here, we require one more assumption: given $1\leq i<j\leq k$ and
two partitioned sets $S_{i},S_{j}$, any two sparsifications of rate $i$ and
$j$ can be “merged” to produce a third sparsification of rate $i$.
Specifically, if $H_{i}\in\mathcal{F}_{i}$, and $H_{j}\in\mathcal{F}_{j}$,
then there is a graph $H_{i,j}\in\mathcal{F}_{i}$ such that $H_{j}\subseteq
H_{i,j}\subseteq H_{i}\cup H_{j}$. For the above sparsification problems
(e.g., Steiner tree, spanners), we can often let $H_{i,j}$ be the union of
$H_{i}$ and $H_{j}$, though edges may need to be pruned to ensure that
$H_{i,j}$ is a Steiner tree (by removing cycles).

######  Definition 4.

Let $S_{i}$ and $S_{j}$ be two partitions where $i<j$. Let $H_{i}$ and $H_{j}$
be the independently computed solution for the terminal set $T_{i}$ and
$T_{j}$ respectively. We say that the solution $H_{j}$ is merged with solution
$H_{i}$ if we complete the following two steps:

  1. 1.

If an edge $e$ is not present in $H_{i}$ but present in $H_{j}$, then we add
$e$ to $H_{i}$.

  2. 2.

If there is a tree constraint, then prune some lower-rated edges to ensure
there is no cycle.

For a tree constraint, we need to prune lower-rated edges since pruning
higher-rated edges may disconnect the tree. More specifically, for each pair
of terminals $u$ and $v$ in $S_{j}$, we check if there exists more than one
path in $H_{j}$. We prune edges until there is only one path $P$ between $u$
and $v$. Now consider the solution $H_{i}$. If a path between $u$ and $v$
other than $P$ exists in $H_{i}$, we remove more edges until $P$ is the only
path between $u$ and $v$. At the end, there is exactly one path for each pair
of terminals in both $H_{i}$ and $H_{j}$. We need the second step of merging
particularly for sparsifications with tree constraints. Although the merging
operation treats these sparsifications differently, we will later show that
the pruning step does not play a significant role in the approximation
guarantee.

Algorithm $k$-priority Approximation computes a partition from the rounded-up
terminals. The following claims show that if the algorithm computes either an
inclusive or pairwise partitioning, then the algorithm provides a valid
solution.

######  Lemma 1.

If Algorithm $k$-priority Approximation computes an inclusive partitioning,
then the algorithm provides a valid solution.

###### Proof.

To compute the solution of the $k$-priority instance we merge all the
independent solutions, that is, if an edge is present for a particular rate
$i$, then it is also present for all rates smaller than $i$. If we are
computing the Steiner tree, then the merging operation ensures that we have
exactly one path for each pair of terminals. Hence, we have a valid priority
Steiner tree. Now suppose that we are computing a spanner (or preserver).
Consider a pair of terminals $t_{i}\in S_{i}$ and $t_{j}\in S_{j}$, w.l.o.g.
we assume $\ell(t_{i})\leq\ell(t_{j})$. Then $t_{j}\in S_{i}$ since the
partitioning is inclusive. Hence there is a path between $t_{i}$ and $t_{j}$
satisfying the distance constraint since we have computed an independent
spanner on $S_{i}$. Hence the merged solution is valid. ∎

######  Lemma 2.

If Algorithm $k$-priority Approximation computes a pairwise partitioning, then
the algorithm provides a valid solution.

###### Proof.

After we merge the independent solutions, the general constraints will be
satisfied. Also, the second step of the merging operation will make sure that
for each pair of terminals there is exactly one path if we are computing
priority Steiner trees. Hence, in that case, the output will be a valid
priority Steiner tree. Now consider a sparsification where distance
constraints must be satisfied to obtain a valid solution. Consider any pair of
terminals $t_{i}$ and $t_{j}$. If $\ell(t_{i})=\ell(t_{j})=k$, then the
partition $S_{k}$ contains this pair. Hence, when we compute the independent
solution of $S_{k}$, the distance constraint of this pair is satisfied.
Otherwise, let $\min(\ell(t_{i}),\ell(t_{j}))=k$. Then the distance constraint
needs to be satisfied at priority $k$. Also, the pair will be in $S_{k}$.
Hence, after computing the independent solution the constraint will be
satisfied. Hence, in both cases, we have a valid sparsification. ∎

Both the pairwise partitioning and inclusive partitioning are theoretically no
worse than four times the optimal solution as we prove later. The proof is the
same for both cases. However, in practice, pairwise partitioning will perform
better than inclusive partitioning as indicated by the following claim.

######  Lemma 3.

The total number of distance constraints in pairwise partitioning is less than
or equal to the number of distance constraints in an inclusive partitioning.

###### Proof.

In pairwise partitioning, the total number of distance constraints is equal to
the total number of pairs in $S_{1},S_{2},\cdots,S_{k}$. On the other hand,
the total number of distance constraints in inclusive partitioning is equal to
$\sum_{i}{|S_{i}|\choose 2}$. Consider a pair of terminals $t_{i}$ and $t_{j}$
such that both $\ell(t_{i})$ and $\ell(t_{j})$ are not equal to 1. Then in the
inclusive partitioning this pair will be considered in partitions
$S_{\min(\ell(t_{i}),\ell(t_{j}))}$ to $S_{1}$. On the other hand, in the
pairwise partitioning, this pair will be only considered in
$S_{\min(\ell(t_{i}),\ell(t_{j}))}$. Hence, pairwise partitioning will have
only one constraint for this pair and the inclusive partitioning will have
more than one constraint. Overall, the pairwise partitioning will have a
smaller number of constraints and better running time. ∎

Algorithm $k$-priority Approximation provides valid solutions for both
inclusive partitioning and pairwise partitioning as shown in Lemma 1 and 2.
Lemma 3 shows that pairwise partitioning is better in terms of the number of
distance constraints. We now provide an approximation guarantee for Algorithm
$k$-priority Approximation that is independent of the partitioning method.

######  Theorem 2.1.

Consider an instance $\varphi=\langle G,P,w\rangle$ of the $k$-priority
problem with linear edge weights. If we are given an oracle that can compute
the minimum weight sparsification of $G$ over $T$, then with at most
$\log_{2}k+1$ queries to the oracle, Algorithm $k$-priority computes a
$k$-priority sparsification with weight at most $4\
\text{weight}(\textnormal{OPT})$.

###### Proof.

The $k$-priority problem does not explicitly require some vertex has priority
$k$, so we will assume w.l.o.g. $k$ is a power of 2. Given $\varphi$,
construct the rounded-up instance $\varphi^{\prime}$ which is obtained by
rounding up the priority of each vertex to the nearest power of 2. Then, if
$\textnormal{OPT}^{\prime}$ is an optimum solution to the rounded-up instance,
we have $\text{weight}(\textnormal{OPT}^{\prime})\leq 2\
\text{weight}(\textnormal{OPT})$, since edge weights are linear.

Then for each rounded-up priority $i\in\\{1,2,4,8,\ldots,k\\}$, compute a
sparsification independently over the partition $S_{i}$, creating
$\log_{2}k+1$ graphs. Denote these graphs $\textnormal{ALG}_{1}$,
$\textnormal{ALG}_{2}$, $\textnormal{ALG}_{4}$, …, $\textnormal{ALG}_{k}$.
Combine these sparsifications into a single subgraph ALG. This is done using
the “merging” operation described earlier in this section: (i) add each edge
of $H_{i}$ to all sparsification of lower priorities
$H_{i-1},H_{i-2},\cdots,H_{1}$ and (ii) prune some edges to make sure that
there is exactly one path between each pair of terminals if we are computing
priority Steiner tree.

It is not obvious why after this merging operation we have a $k$-priority
sparsification with cost no more than $4\ \text{weight}(\textnormal{OPT})$.
The approximation algorithm computes solutions independently, which means it
is unaware of the terminal sets at the lower levels. Consider the top most
partition $S_{k}$ of the rounded up instance. The approximation algorithm
computes an optimal solution for that partition. The optimal algorithm of the
$k$-priority sparsification computes the solution while considering all the
terminals and all priorities. Let $\textnormal{OPT}_{i}$ be the minimum
weighted subgraph in an optimal $k$-priority solution OPT to generate a valid
sparsification on partition $S_{i}$. Then weight($\textnormal{ALG}_{k}$)
$\leq$ weight($\textnormal{OPT}_{k}$), i.e., if we only consider the top
partition $S_{k}$, then the approximation algorithm is no worse than the
optimal algorithm.

However, the approximation algorithm may incur additional cost when merging
the edges of $\textnormal{ALG}_{k}$ in lower priorities. In the worst case,
merged edges might not be needed to compute the solutions of the lower
partitions (if the merged edges are used in the lower partitions in their
independent solutions, then we do not need to pay any cost for the merging
operation). This is because the approximation algorithm computes the solutions
independently. On the other hand, in the worst case, it may happen that
$\textnormal{OPT}_{k}$ includes all the edges to satisfy all the constraints
of lower partitions. In this case, the cost of the optimal $k$-priority
solution is $k\ $weight($\textnormal{OPT}_{k}$). If
weight($\textnormal{ALG}_{k}$) $\approx$ weight($\textnormal{ALG}_{k-1}$)
$\approx\cdots\approx$ weight($\textnormal{ALG}_{1}$) and the edges of the
sparsification of a particular priority do not help in the lower priorities,
then it seems like the approximation algorithm can perform around $k$ times
worse than the optimal $k$-priority solution. However, the hypothesis (the
edges of the sparsification of a particular priority do not help in the lower
priorities) will not be true because we are considering a rounded up instance.
In a rounded up instance $S_{k}=S_{k-1}=\cdots=S_{\frac{k}{2}+1}$. Hence,
weight($\textnormal{ALG}_{i}$) $\leq$ weight($\textnormal{OPT}_{i}$) for
$i=k,k/2,\cdots,\frac{k}{2}+1$.

######  Lemma 4.

If we compute independent solutions of a rounded up $k$-priority instance and
merge them, then the cost of the solution is no more than $2\
\text{weight}(\textnormal{OPT})$.

###### Proof.

Let the set of partitions be $S_{k},S_{k/2},\cdots,S_{1}$. Suppose we have
computed the independent solution and merged them in lower priorities. We
actually prove a stronger claim, and use that to prove the lemma. Note that in
the worst case the cost of approximation algorithm is
$2^{k}\text{weight}(\textnormal{ALG}_{k})+2^{k/2}\text{weight}(\textnormal{ALG}_{k/2})+\cdots+\text{weight}(\textnormal{ALG}_{1})$.
And the cost of the optimal algorithm is
$\text{weight}(\textnormal{OPT}_{k})+\text{weight}(\textnormal{OPT}_{k-1})+\cdots+\text{weight}(\textnormal{OPT}_{1})$.
We show that
$2^{k}\text{weight}(\textnormal{ALG}_{k})+2^{k/2}\text{weight}(\textnormal{ALG}_{k/2})+\cdots+\text{weight}(\textnormal{ALG}_{1})\leq
2\
(\text{weight}(\textnormal{OPT}_{k})+\text{weight}(\textnormal{OPT}_{k-1})+\cdots+\text{weight}(\textnormal{OPT}_{1}))$.
Let $k=2^{i}$. We provide a proof by induction on $i$.

Base step: If $i=0$, then we have just one partition $S_{1}$. The
approximation algorithm computes a sparsification for $S_{1}$ and there is
nothing to merge. Since the approximation algorithm uses an optimal algorithm
to compute independent solutions, weight($\textnormal{ALG}_{1}$) $\leq 2\ $
weight($\textnormal{OPT}_{1}$).

Inductive step: We assume that the claim is true for $i=j$ which is the
induction hypothesis. Hence
$2^{j}\text{weight}(\textnormal{ALG}_{2^{j}})+2^{j-1}\text{weight}(\textnormal{ALG}_{2^{j-1}})+\cdots+\text{weight}(\textnormal{ALG}_{1})\leq
2\
(\text{weight}(\textnormal{OPT}_{2^{j}})+\text{weight}(\textnormal{OPT}_{2^{j}-1})+\cdots+\text{weight}(\textnormal{OPT}_{1}))$.
We now show that the claim is also true for $i=j+1$. In other words, we have
to show that
$2^{j+1}\text{weight}(\textnormal{ALG}_{2^{j+1}})+2^{j}\text{weight}(\textnormal{ALG}_{2^{j}})+\cdots+\text{weight}(\textnormal{ALG}_{1})\leq
2\
(\text{weight}(\textnormal{OPT}_{2^{j+1}})+\text{weight}(\textnormal{OPT}_{2^{j+1}-1})+\cdots+\text{weight}(\textnormal{OPT}_{1}))$.
We know,

L.H.S.
$\displaystyle=2^{j+1}\text{weight}(\textnormal{ALG}_{2^{j+1}})+2^{j}\text{weight}(\textnormal{ALG}_{2^{j}})+\cdots+\text{weight}(\textnormal{ALG}_{1})$
$\displaystyle=\text{weight}(\textnormal{ALG}_{2^{j+1}})+\text{weight}(\textnormal{ALG}_{2^{j+1}})+\cdots+\text{weight}(\textnormal{ALG}_{2^{j+1}})$
$\displaystyle+2^{j}\text{weight}(\textnormal{ALG}_{2^{j}})+2^{j-1}\text{weight}(\textnormal{ALG}_{2^{j}-1})+\cdots+\text{weight}(\textnormal{ALG}_{1}))$
$\displaystyle\leq\text{weight}(\textnormal{OPT}_{2^{j+1}})+\text{weight}(\textnormal{OPT}_{2^{j+1}})+\cdots+\text{weight}(\textnormal{OPT}_{2^{j+1}})$
$\displaystyle+2^{j}\text{weight}(\textnormal{ALG}_{2^{j}})+2^{j-1}\text{weight}(\textnormal{ALG}_{2^{j}-1})+\cdots+\text{weight}(\textnormal{ALG}_{1}))$
$\displaystyle=2^{j+1}\text{weight}(\textnormal{OPT}_{2^{j+1}})+2^{j}\text{weight}(\textnormal{ALG}_{2^{j}})+\cdots+\text{weight}(\textnormal{ALG}_{1})$
$\displaystyle=2\
(\text{weight}(\textnormal{OPT}_{2^{j+1}})+\text{weight}(\textnormal{OPT}_{2^{j+1}-1})+\cdots+\text{weight}(\textnormal{OPT}_{2^{j}+1}))$
$\displaystyle+2^{j}\text{weight}(\textnormal{ALG}_{2^{j}})+2^{j-1}\text{weight}(\textnormal{ALG}_{2^{j}-1})+\cdots+\text{weight}(\textnormal{ALG}_{1}))$
$\displaystyle\leq 2\
(\text{weight}(\textnormal{OPT}_{2^{j+1}})+\text{weight}(\textnormal{OPT}_{2^{j+1}-1})+\cdots+\text{weight}(\textnormal{OPT}_{2^{j}+1}))$
$\displaystyle+2\
(\text{weight}(\textnormal{OPT}_{2^{j}})+\text{weight}(\textnormal{OPT}_{2^{j}-1})+\cdots+\text{weight}(\textnormal{OPT}_{1}))$
$\displaystyle=2\
(\text{weight}(\textnormal{OPT}_{2^{j+1}})+\text{weight}(\textnormal{OPT}_{2^{j+1}-1})+\cdots+\text{weight}(\textnormal{OPT}_{1}))$
$\displaystyle=\text{R.H.S.}$

Here, the second equality is just a simplification. The third inequality uses
the fact that an independent optimal solution has a cost lower than or equal
to any other solution. The fourth equality is a simplification, the fifth
inequality uses the fact that the input is a rounded up instance. The sixth
inequality uses the induction hypothesis. The L.H.S. is greater than the cost
of the approximation algorithm. The R.H.S. is smaller than $2\
\text{weight}(\textnormal{OPT})$. ∎

We have shown earlier that the solution of the rounded up instance has a cost
of no more than $2\ \text{weight}(\textnormal{OPT})$. Combining that claim and
the previous claim, we can show that the solution of the approximation
algorithm has cost no more than $4\ \text{weight}(\textnormal{OPT})$. ∎

In most cases, computing the optimal sparsification is computationally
difficult. If an oracle is instead replaced with a $\rho$-approximation, the
rounding-up approach is a $4\rho$-approximation, by following the same proof
as above.

##  3 Subset spanners and distance preservers

Here we provide a bound on the size of subsetwise graph spanners, where
lightness is expressed with respect to the weight of the corresponding Steiner
tree.

A _spanner_ of a graph $G$ is a subgraph $H$ which approximates distances in
$G$ up to some error. Specifically, given a (possibly edge-weighted) graph $G$
and $\alpha\geq 1$, we say that $H$ is a (multiplicative) $\alpha$-spanner if
$d_{H}(u,v)\leq\alpha\cdot d_{G}(u,v)$ for all $u,v\in V$, where $\alpha$ is
the _stretch factor_ of the spanner and $d_{G}(u,v)$ is the graph distance
between $u$ and $v$ in $G$. A _subset spanner_ over $T\subseteq V$
approximates distances between pairs of vertices in $T$ (e.g.,
$d_{H}(u,v)\leq\alpha\cdot d_{G}(u,v)$ for all $u,v\in T$). For clarity, we
refer to the case where $T=V$ as an _all-pairs spanner_. The _lightness_ of an
all-pairs spanner is defined as its total edge weight divided by $w(MST(G))$.
A _distance preserver_ is a spanner with $\alpha=1$.

Althöfer et al. [9] give a simple greedy algorithm which constructs an all-
pairs $(2k-1)$-spanner $H$ of size $O(n^{1+1/k})$ and lightness
$1+\frac{n}{2k}$. The lightness has been subsequently improved; in particular
Chechik and Wulff-Nilsen [16] give a $(2k-1)(1+\varepsilon)$ spanner with size
$O(n^{1+1/k})$ and lightness $O_{\varepsilon}(n^{1/k})$. Up to $\varepsilon$
dependence, these size and lightness bounds are conditionally tight assuming a
girth conjecture by Erdős [20], which states that there exist graphs of girth
$2k+1$ and $\Omega(n^{1+1/k})$ edges.

For subset spanners over $T\subseteq V$, the lightness is defined with respect
to the minimum Steiner tree over $T$, since that is the minimum weight
subgraph which connects $T$. We remark that in general graphs, the problem of
finding a light multiplicative subset spanner can be reduced to that of
finding a light spanner:

######  Lemma 5.

Let $G$ be a weighted graph and let $T\subseteq V$. Then there is a poly-time
constructible subset spanner with stretch $(2k-1)(1+\varepsilon)$ and
lightness $O_{\varepsilon}(|T|^{1/k})$.

###### Proof.

Let $\tilde{G}$ be the metric closure over $(G,T)$, namely the complete graph
$K_{|T|}$ where each edge $uv\in E(\tilde{G})$ has weight $d_{G}(u,v)$. Let
$H^{\prime}$ be a $(2k-1)(1+\varepsilon)$-spanner of $\tilde{G}$. By replacing
each edge of $H^{\prime}$ with the corresponding shortest path in $G$, we
obtain a subset spanner $H$ of $G$ with the same stretch and total weight.
Using the spanner construction of [16], the total weight of $H^{\prime}$ is
$O_{\varepsilon}(|T|^{1/k})w(MST(\tilde{G}))$. Using the well-known fact that
the MST of $\tilde{G}$ is a 2-approximation for the minimum Steiner tree over
$(G,T)$, it follows that the total weight of $H^{\prime}$ is also
$O_{\varepsilon}(|T|^{1/k})$ times the minimum Steiner tree over $(G,T)$. ∎

Thus, the problem of finding a subset spanner with multiplicative stretch
becomes more interesting when the input graph is restricted (e.g., planar, or
$H$-minor free). Klein [24] showed that every _planar_ graph has a subset
$(1+\varepsilon)$-spanner with lightness $O_{\varepsilon}(1)$. Le [27] gave a
poly-time algorithm which computes a subset $(1+\varepsilon)$-spanner with
lightness $O_{\varepsilon}(\log|T|)$, where $G$ is restricted to be $H$-minor
free.

On the other hand, subset spanners with additive $+\beta$ error are more
interesting, as one cannot simply reduce this problem to the all-pairs spanner
as in Lemma 5. It is known that every unweighted graph $G$ has $+2$, $+4$, and
$+6$ spanners with $O(n^{3/2})$ edges [8], $\widetilde{O}(n^{7/5})$ edges
[15], and $O(n^{4/3})$ edges [11, 25] respectively, and that the upper bound
of $O(n^{4/3})$ edges cannot be improved even with $+n^{o(1)}$ additive error
[2].

###  3.1 Subset distance preservers

Unlike spanners, general graphs do not contain sparse distance preservers that
preserve all distances exactly; the unweighted complete graph has no
nontrivial distance preserver and thus $\Theta(n^{2})$ edges are needed.
Similarly, subset distance preservers over a subset $T\subseteq V$ may require
$\Theta(|T|^{2})$ edges. It is an open question whether there exists $c>0$
such that any undirected, unweighted graph and subset of size $|T|=O(n^{1-c})$
has a distance preserver on $O(|T|^{2})$ edges [12]. Moreover, when
$|T|=O(n^{2/3})$, there are graphs for which any subset distance preserver
requires $\Omega(|T|n^{2/3})$ edges, which is $\omega(|T|^{2})$ when
$|T|=o(n^{2/3})$ [12].

######  Theorem 3.1.

If the above open question is true, then every unweighted graph with
$|T|=O(n^{1-c})$ and terminal priorities in $[k]$ has a priority distance
preserver of size $4\ \text{weight}(\textnormal{OPT})$.

##  4 Multi-Priority Approximation Algorithms

In this section, we illustrate how the subset spanners mentioned in Section 3
can be used in Theorem 2.1, and show several corollaries of the kinds of
guarantees one can obtain in this manner. In particular, we give the first
weight bounds for multi-priority graph spanners. The case of Steiner trees was
discussed [3].

###  4.1 Spanners

If the input graph is planar, then we can use the algorithm by Klein [24] to
compute a subset spanner for the set of priorities we get from the rounding
approach. The polynomial-time algorithm in [24] has constant approximation
ratio, assuming constant stretch factor, yielding the following corollary.

######  Corollary 1.

Given a planar graph $G$ and $\varepsilon>0$, there exists a rounding approach
based algorithm to compute a multi-priority multiplicative
$(1+\varepsilon)$-spanner of $G$ having $O(\varepsilon^{-4})$ approximation.
The algorithm runs in $O(\frac{|T|\log|T|}{\varepsilon})$ time, where $T$ is
the set of terminals.

The proof of this corollary follows from combining the guarantee of Klein [24]
with the bound of Theorem 2.1. Using the approximation result for subset
spanners provided in Lemma 5, we obtain the following corollary.

######  Corollary 2.

Given an undirected weighted graph $G$, $t\in\mathbb{N}$, $\varepsilon>0$,
there exists a rounding approach based algorithm to compute a multi-priority
multiplicative $(2t-1)(1+\varepsilon)$-spanner of $G$ having
$O(|T|^{\frac{1}{\varepsilon}})$ approximation, where $T$ is the set of
terminals. The algorithm runs in $O(|T|^{2+\frac{1}{k}+\varepsilon})$ time.

For additive spanners, there are algorithms to compute subset spanners of size
$O(n|T|^{\frac{2}{3}})$, $\tilde{O}(n|T|^{\frac{4}{7}})$ and
$O(n|T|^{\frac{1}{2}})$ for additive stretch $2$, $4$ and $6$, respectively
[1, 23]. Similarly, there is an algorithm to compute a near-additive subset
$(1+\varepsilon,4)$–spanner of size $O(n\sqrt{\frac{|T|\log n}{\varepsilon}})$
[23]. If we use these algorithms as subroutines in Lemma 5 to compute subset
spanners for different priorities, then we have the following corollaries.

######  Corollary 3.

Given an undirected weighted graph $G$, there exist polynomial-time algorithms
to compute multi-priority graph spanners with additive stretch 2, 4 and 6, of
size $O(n|T|^{\frac{2}{3}})$, $\tilde{O}(n|T|^{\frac{4}{7}})$, and
$O(n|T|^{\frac{1}{2}})$, respectively.

######  Corollary 4.

Given an undirected unweighted graph $G$, there exists a polynomial-time
algorithm to compute multi-priority $(1+\varepsilon,4)$–spanners of size
$O(n\sqrt{\frac{|T|\log n}{\varepsilon}})$.

Several of the above results involving additive spanners have been recently
generalized to weighted graphs; more specifically, there are algorithms to
compute subset spanners in weighted graphs of size $O(n|T|^{\frac{2}{3}})$,
and $O(n|T|^{\frac{1}{2}})$ for additive stretch $2W(\cdot,\cdot)$, and
$6W(\cdot,\cdot)$, respectively [18, 19, 4], where $W(u,v)$ denotes the
maximum edge weight along the shortest $u$-$v$ path in $G$. Hence, we have the
following corollary.

######  Corollary 5.

Given an undirected weighted graph $G$, there exist polynomial-time algorithms
to compute multi-priority graph spanners with additive stretch
$2W(\cdot,\cdot)$, and $6W(\cdot,\cdot)$, of size $O(n|T|^{\frac{2}{3}})$, and
$O(n|T|^{\frac{1}{2}})$, respectively.

###  4.2 $t$–Connected Subgraphs

Another example which fits the framework of Section 1.1 is that of finding
$t$–connected subgraphs [28, 26, 29], in which (similar to the Steiner tree
problem) a set $T\subseteq V$ of terminals is given, and the goal is to find
the minimum-cost subgraph $H$ such that each pair of terminals is connected
with at least $t$ vertex-disjoint paths in $H$. Nutov [28] presents an
approximation algorithm for this problem giving approximation ratio
$O(t^{2}\log t)$. Laekhanukit [26] improves the approximation guarantee to
$O(t\log t)$ if $|T|\geq t^{2}$ and shows that the hardest instances of the
problem are when $|T|\approx t$. Nutov [29] studies the subset
$t$–connectivity augmentation problem where given a graph $G$ and a
$(t-1)$–connected subgraph $H$, we want to augment some edges to $H$ to make
it $t$–connected. The objective is to minimize the size of the set of
augmented edges. If we use the algorithm of [26] in Theorem 2.1 to compute
subsetwise $t$–connected subgraphs for different priorities, then we have
following corollary.

######  Corollary 6.

Given an undirected weighted graph $G$, using the algorithm of [26] as a
subroutine in Theorem 2.1 yields a polynomial-time algorithm which computes a
multi-priority $t$–connected subgraph over the terimals with approximation
ratio $O(t\log t)$ provided $|T|\geq t^{2}$.

##  5 Conclusions and Future Work

We defined a class of $k$-priority sparsification problems and analyzed their
difficulty relative to their corresponding single-priority problems. The
proposed technique solves these problems using a subroutine for the
corresponding single-priority problem. Assuming linearly increasing edge
weights and an exact oracle for the single priority module, our algorithm
yields a constant approximation to the optimal solution that is independent of
the number of priorities $k$. Naturally, a $\rho$-approximation can be used in
place of the oracle, yielding a $O(\rho)$-approximation to the $k$-priority
problem, which is again independent of the number of priorities $k$. Since the
$k$-priority sparsification problem relies on a single priority subroutine, we
studied the single priority subsetwise problem for graph spanners and distance
preservers. A feature in common for all the results in this paper is that
solving the $k$-priority problem relies on single priority solutions (exact or
approximate). A nice open problem is whether these $k$-priority problems can
be solved directly, without relying on single priority solvers, by building
the solution simultaneously for all priorities.

## References

  * [1] Abboud, A., Bodwin, G.: Lower bound amplification theorems for graph spanners. In: Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 841–856 (2016)
  * [2] Abboud, A., Bodwin, G.: The 4/3 additive spanner exponent is tight. Journal of the ACM (JACM) 64(4), 28 (2017)
  * [3] Ahmed, A.R., Angelini, P., Sahneh, F.D., Efrat, A., Glickenstein, D., Gronemann, M., Heinsohn, N., Kobourov, S., Spence, R., Watkins, J., Wolff, A.: Multi-level Steiner trees. In: 17th International Symposium on Experimental Algorithms, (SEA). pp. 15:1–15:14 (2018). https://doi.org/10.4230/LIPIcs.SEA.2018.15, https://doi.org/10.4230/LIPIcs.SEA.2018.15
  * [4] Ahmed, R., Bodwin, G., Hamm, K., Kobourov, S., Spence, R.: On additive spanners in weighted graphs with local error. In: Graph-Theoretic Concepts in Computer Science. pp. 361–373. Springer International Publishing, Cham (2021)
  * [5] Ahmed, R., Bodwin, G., Sahneh, F.D., Hamm, K., Jebelli, M.J.L., Kobourov, S., Spence, R.: Graph spanners: A tutorial review. Computer Science Review 37, 100253 (2020)
  * [6] Ahmed, R., Bodwin, G., Sahneh, F.D., Hamm, K., Kobourov, S., Spence, R.: Multi-Level Weighted Additive Spanners. In: Coudert, D., Natale, E. (eds.) 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 190, pp. 16:1–16:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2021). https://doi.org/10.4230/LIPIcs.SEA.2021.16, https://drops.dagstuhl.de/opus/volltexte/2021/13788
  * [7] Ahmed, R., Hamm, K., Jebelli, M.J.L., Kobourov, S., Sahneh, F.D., Spence, R.: Approximation algorithms and an integer program for multi-level graph spanners. In: Proceedings of the Special Event on Analysis of Experimental Algorithms (2019)
  * [8] Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28, 1167–1181 (04 1999). https://doi.org/10.1137/S0097539796303421
  * [9] Althöfer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry 9(1), 81–100 (1993)
  * [10] Balakrishnan, A., Magnanti, T.L., Mirchandani, P.: Modeling and heuristic worst-case performance analysis of the two-level network design problem. Management Sci. 40(7), 846–867 (1994). https://doi.org/10.1287/mnsc.40.7.846
  * [11] Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: Additive spanners and ($\alpha$, $\beta$)-spanners. ACM Transactions on Algorithms (TALG) 7(1), 5 (2010)
  * [12] Bodwin, G.: New results on linear size distance preservers. SIAM Journal on Computing 50(2), 662–673 (2021). https://doi.org/10.1137/19M123662X, https://doi.org/10.1137/19M123662X
  * [13] Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6:1–6:33 (2013). https://doi.org/10.1145/2432622.2432628
  * [14] Charikar, M., Naor, J., Schieber, B.: Resource optimization in QoS multicast routing of real-time multimedia. IEEE/ACM Transactions on Networking 12(2), 340–348 (April 2004). https://doi.org/10.1109/TNET.2004.826288
  * [15] Chechik, S.: New additive spanners. In: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. pp. 498–512. Society for Industrial and Applied Mathematics (2013)
  * [16] Chechik, S., Wulff-Nilsen, C.: Near-optimal light spanners. ACM Transactions on Algorithms (TALG) 14(3), 33 (2018)
  * [17] Chuzhoy, J., Gupta, A., Naor, J.S., Sinha, A.: On the approximability of some network design problems. ACM Trans. Algorithms 4(2), 23:1–23:17 (2008). https://doi.org/10.1145/1361192.1361200
  * [18] Elkin, M., Gitlitz, Y., Neiman, O.: Almost shortest paths and PRAM distance oracles in weighted graphs. arXiv preprint arXiv:1907.11422 (2019)
  * [19] Elkin, M., Gitlitz, Y., Neiman, O.: Improved weighted additive spanners. arXiv preprint arXiv:2008.09877 (2020)
  * [20] Erdős, P.: Extremal problems in graph theory. In: Proceedings of the Symposium on Theory of Graphs and its Applications. p. 2936 (1963)
  * [21] Hauptmann, M., Karpiński, M.: A compendium on Steiner tree problems. Inst. für Informatik (2013)
  * [22] Karpinski, M., Mandoiu, I.I., Olshevsky, A., Zelikovsky, A.: Improved approximation algorithms for the quality of service multicast tree problem. Algorithmica 42(2), 109–120 (2005). https://doi.org/10.1007/s00453-004-1133-y
  * [23] Kavitha, T.: New pairwise spanners. Theory of Computing Systems 61(4), 1011–1036 (Nov 2017). https://doi.org/10.1007/s00224-016-9736-7, https://doi.org/10.1007/s00224-016-9736-7
  * [24] Klein, P.N.: A subset spanner for planar graphs, with application to subset tsp. In: Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing. pp. 749–756. STOC ’06, ACM, New York, NY, USA (2006). https://doi.org/10.1145/1132516.1132620, http://doi.acm.org/10.1145/1132516.1132620
  * [25] Knudsen, M.B.T.: Additive spanners: A simple construction. In: Scandinavian Workshop on Algorithm Theory. pp. 277–281. Springer (2014)
  * [26] Laekhanukit, B.: An improved approximation algorithm for minimum-cost subset k-connectivity. In: International Colloquium on Automata, Languages, and Programming. pp. 13–24. Springer (2011)
  * [27] Le, H.: A ptas for subset tsp in minor-free graphs. In: Proceedings of the Thirty-First Annual. Society for Industrial and Applied Mathematics, USA (2020)
  * [28] Nutov, Z.: Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions. In: IEEE 50th Annual Symposium on Foundations of Computer Science (FOCS 2009). IEEE Computer Society, Los Alamitos, CA, USA (oct 2009). https://doi.org/10.1109/FOCS.2009.9, https://doi.ieeecomputersociety.org/10.1109/FOCS.2009.9
  * [29] Nutov, Z.: Approximating subset k-connectivity problems. Journal of Discrete Algorithms 17, 51–59 (2012)
  * [30] Sahneh, F.D., Kobourov, S., Spence, R.: Approximation algorithms for the priority Steiner tree problem. 27th International Computing and Combinatorics Conference (COCOON) (2021), http://arxiv.org/abs/1811.11700