# Knowledge Enhanced Model for Live Video Comment Generation

Jieting Chen  School of Information
Renmin University of China
Beijing, China
<EMAIL_ADDRESS>Junkai Ding  Department of Statistics
Columbia University
New York, United States
<EMAIL_ADDRESS>Wenping Chen  School of Information
Renmin University of China
Beijing, China
<EMAIL_ADDRESS>Qin Jin *Qin Jin is the corresponding author. School
of Information
Renmin University of China
Beijing, China
<EMAIL_ADDRESS>
###### Abstract

Live video commenting is popular on video media platforms, as it can create a
chatting atmosphere and provide supplementary information for users while
watching videos. Automatically generating live video comments can improve user
experience and enable human-like generation for bot chatting. Existing works
mostly focus on short video datasets while ignoring other important video
types such as long videos like movies. In this work, we collect a new Movie
Live Comments (MovieLC) dataset to support research on live video comment
generation for long videos. We also propose a knowledge enhanced generation
model inspired by the divergent and informative nature of live video comments.
Our model adopts a pre-training encoder-decoder framework and incorporates
external knowledge. Extensive experiments show that both objective metrics and
human evaluation demonstrate the effectiveness of our proposed model. The
MovieLC dataset and our code will be released.

###### Index Terms:

video comment generation, knowledge enhancement, multi-modal understanding

##  I Introduction

Many video platforms have the “live video commenting” feature, which allows
users to comment at any time while watching a video, and the comments
instantly slide across the video screen, making users feel like watching
together with others, even if they are watching alone. Live video commenting
has become more and more popular among web users. The video platform
Bilibili111https://www.bilibili.com/ reported that the number of live comments
reached 10 billion in 2021 and there are more than 60 million live comment
users on its platform222https://new.qq.com/rain/a/20211129A0AKBB00. Live
comments can also provide supplementary information that is related to but
goes beyond the video content, which helps users understand the video, enjoy
the video, and provoke discussion for more user interaction. Besides, live
commenting technologies can be applied in bot chatting scenarios to support
human-like user experience because of the flexible and divergent expressions.
Therefore, automatic live video comment generation, as a meaningful and
challenging task, has attracted increasing attention in the research
community.

Figure 1: An example from MovieLC Dataset. The blue words associate with
external knowledge that goes beyond the video content. Best viewed in color.

One might intuitively think that video comment generation is similar to video
caption generation. However, we argue that video comments and video captions
differ greatly in the data characteristics and pragmatics. Video captions are
normally objective descriptions of the visual semantic content, while live
video comments are very divergent but informative. Existing live video
comments datasets including Livebot [1], VideoIC [2], and the extensional
Livebot [3], are all collected from the same video platform
Bilibili333https://www.bilibili.com/, where most of the videos are user-
generated short videos, and the live comments are often sloppy. They ignore
other important types of videos such as long videos like movies, which may
trigger more live comments and discussions due to the long video duration. In
order to ensure sufficient exploration for the live comment generation task,
we collect a new Movie Live Comments (MovieLC)
dataset444https://github.com/AIM3-RUC/MovieLC, which contains 1,406,219 live
comments from 85 movies, totaling 175 hours. As shown in the examples in
Fig.1, in addition to objective descriptions of the video content, live video
comments may include divergent information associated with external knowledge,
for example, the awards Sean Penn has won and other representative works in
which he played the leading role, etc.

Most of the existing works on live comment generation follow the routines of
video captioning approaches. The live video comments generation task is first
defined in [1]. The following works mainly focus on addressing the
interactivity between modalities [2, 4] and the diversity of generation [5,
4]. These works typically ignore the informative and divergent features of
live video comments. We argue that the generation model should introduce
external knowledge beyond the visual and text context. Therefore, we propose a
Knowledge Enhanced Model for Live Video Comment Generation (KLVCG), which
adopts a pre-training encoder-decoder framework inspired by [6]. Specifically,
we design independent encoders for visual context, comment context, and
external knowledge respectively. A cross encoder is built for interaction
across modalities, and an auto-regressive decoder is constructed for the
generation. We recall external knowledge from knowledge graphs and comments
from other videos. Then we incorporate them via the masked language prediction
task in the pre-training stage.

We standardize a more reasonable evaluation setting and conduct experiments on
three datasets, including Livebot [1], VideoIC [2] and MovieLC datasets. Our
model significantly outperforms baselines on three datasets on both objective
metrics and human evaluation.

The main contributions of this work include: 1) We build MovieLC, a movie live
comments dataset. The long movie videos with informative live comments can
well complement existing datasets. 2) We propose the KLVCG model, which can
generate higher-quality live video comments by effectively leveraging external
knowledge. 3) Extensive experiments on three benchmark datasets validate that
our model significantly outperforms other competing methods.

##  II Related Works

Live video comment generation. Existing works on live comment generation
typically follow the captioning routines. The task is firstly defined in [1],
which releases a benchmark dataset called Livebot and proposes a model that
employs transformers with multiple blocks. The following works on this task
[7, 2, 4] mainly focus on the interactivity among different modalities. For
example, a multi-modal transformer trained with a multi-task learning is
proposed to enhance inter-modal and intra-modal interactions [2]. Another line
of works [5, 4] focus on the diversity of generation. Works on other aspects
like cold start in generation [3] and timestamp prediction for generation [8]
are also proposed. All these works use user-generated short videos for
validation. Additionally, existing works ignore the divergent feature of
comments, while we believe that introducing extra knowledge beyond visual
content is important for better generation.

Knowledge enhanced generation. Incorporating knowledge for text generation has
shown promising performance on many tasks, such as Visual Question Answering
(VQA) [9, 10] and dialogue response generation [11, 12]. To the best of our
knowledge, knowledge enhancement for video comment generation has not been
well investigated. The key challenge is how to effectively fuse knowledge into
model. Pre-training is a commonly used method, which incorporates the
knowledge into the model by designing specific pre-training tasks like masked
language modeling or entity/relation prediction [13, 14, 15]. Some works
implicitly incorporate the knowledge as feature [13]. The knowledge can be
embedded in a feature by the knowledge representation model such as TransE
[16]. The other works explicitly incorporate the knowledge as natural language
tokens [14, 15], which is intuitive and effective. We choose the explicit way
and leverage a pre-training task to introduce external knowledge.

##  III Datasets

MovieLC data collection. We select 85 famous movies and collect the live
comments data from a public video platform555https://v.qq.com/. We check the
data manually to ensure that the live comments are correctly aligned with the
visual content. In addition, we also acquire the movie scripts from the public
website666http://assrt.net, and the meta information including storylines,
tags, and casts from Douban777https://movie.douban.com/ for future
exploration. We split the data in MovieLC into training, validation, and
testing sets by the ratio of 8:1:1 (more details can be found in the
supplementary material). We will release the dataset and processed data for
easy reproduction. To protect the copyrights of movies, we will only provide
the IMDb urls following the same protocol that has been applied in other
movie/TV shows datasets such as TRIPOD [17] and VIOLIN [18].

TABLE I: Statistics of three datasets. Dataset | Livebot[1] | VideoIC[2] | MovieLC
---|---|---|---
#Videos | 2,361 | 4,951 | 85
#Comments | 895,929 | 5,330,393 | 1,406,219
Durations (h) | 114 | 557 | 175
Avg. Dur(s) | 174 | 405 | 7412
Avg. #Comm | 380 | 1,077 | 16,544
Avg. #Char | 9.08 | 9.14 | 10.37
Avg. #Word | 5.42 | 5.39 | 6.53

MovieLC data statistics. Our MovieLC dataset contains 1,406,219 live comments,
aligned with 85 movies, spanning in total 175 hours. Table I shows the
statistics of three datasets. Different from previous datasets, MovieLC
consists of long videos lasting 7412 seconds on average, and more comments
with 16,544 comments per video on average. The lengths of characters/words are
longer as well. It is because that the movie live comments are with more
meaningful expressions and fewer buzzwords. As shown in Figure 1, the
diversity and informativeness of movie live comments bring more challenges for
the generation task.

TABLE II: Notation table. Symbol | Definition
---|---
$t$ | the target time step for comment generation
$l$ | the time range of the context window
$\bm{F}$=$\\{\bm{f}_{i}\\}$ | the context of frame sequence
$\bm{C}$=$\\{\bm{c}_{i}\\}$ | the context of comment sequences
$\bm{c}_{i}$=$\\{\bm{w}_{ij}\\}$ |  the word sequence of comments at time step $i$
$\bm{K}$=$\\{\bm{k}_{i}\\}$ | the word sequence of recalled knowledge
$\bm{Y}$=$\\{\bm{y}_{i}\\}$ | the word sequence of the target comment
$\bm{V}$=$\\{\bm{v}_{i}\\}$ | the feature sequence of context frames
$\mathbbm{M}$=$\\{\bm{M}_{i}\\}$ | the feature sequence of context comments
$\bm{W}$ | the output of the cross encoder
$\bm{D}$ | the output hidden states of the decoder
$\bm{P}$ | the output prediction of the model
$\mathcal{L}_{\mathrm{mask}}$ | the loss of pre-training task
$\mathcal{L}_{\mathrm{gen}}$ | the loss of fine-tuning task
Figure 2: The left side shows the model structure of KLVCG. It incorporates
recalled knowledge by a knowledge encoder. The comment context is augmented by
related comments from other videos (in orange). The outputs of single modality
encoders are added by token type embedding (in grey) and period type embedding
(in purple). The right side shows the process of recalling knowledge from the
knowledge graph (in blue) and comments from other videos (in green). Best
viewed in color.

##  IV Methodology

We propose a new framework for live video comment generation KLVCG that
recalls external knowledge and integrates them to enhance the comment
generation. At time step $t$, we consider the time range $[t$-$l,t$+$l]$ as
its context window. Given the video context $\bm{F}$, comment context
$\bm{C}$, and auxiliary external knowledge $\bm{K}$, KLVCG aims to generate a
comment $\bm{Y}$=$\\{\bm{y}_{1},\bm{y}_{2},...,\bm{y}_{g}\\}$ at time step
$t$, where $g$ denotes the maximum length of the generated words. Table II
provides the exposition of symbols we used in the following part.

###  IV-A Model architecture

The left side of Fig.2 illustrates the overall framework of our knowledge
enhanced model for live video comment generation (KLVCG). Following the
encoder-decoder framework, KLVCG consists of independent modality encoders for
video context, comment context, and external knowledge respectively, a cross
encoder, and a decoder. All encoders are multi-layer transformers with the
hidden size of $d$.

Visual encoder. Given the target time step $t$, we sample one frame per second
from the context window $[t$-$l,t$+$l]$ and form the visual frame context
$\bm{F}$=$\\{\bm{f}_{t-l},\cdots,\bm{f}_{t},\cdots,\bm{f}_{t+l}\\}$ for the
target time. The visual features are then extracted by a pre-trained ResNet101
[19], followed by a linear layer to project the feature to the $d$-dimensional
visual context
$\bm{V}$=$\\{\bm{v}_{t-l},\cdots,\bm{v}_{t},\cdots,\bm{v}_{t+l}\\}\\!\in\\!\mathbb{R}^{(2l+1)\times{d}}$.
Position embedding is added to preserve the temporal information. Finally, the
contextualized encoding $\bm{V^{{}^{\prime}}}$ is generated via a transformer
encoder:
$\bm{V^{{}^{\prime}}}\in\mathbb{R}^{(2l+1)\times{d}},\bm{V^{{}^{\prime}}}=Transformer_{v}(\bm{V})$.

Comment@TimeStep encoder. At the target time step $t$, users may post the
comment based on not only the visual content, but also the surrounding
comments. As multiple comments normally appear at a time step, we concatenate
the comments appearing at the same time step $i$ with SEP separator token and
add a CLS token at the beginning. We then tokenize the
sequence888https://github.com/fxsjy/jieba into a word sequence
$\bm{c}_{i}=\\{\bm{w}_{i1},\bm{w}_{i2},...,\bm{w}_{in}\\}$, where ${n}$
denotes the maximum length of the sequence. After adding the position
embedding, the Comment@TimeStep encoder produces the contextualized feature
$\bm{{c_{i}}^{{}^{\prime}}}\in\mathbb{R}^{n\times{d}},\bm{c}_{i}^{{}^{\prime}}=Transformer_{m}(\bm{c}_{i})$.
After that, we use the contextualized CLS token to represent the comments at
time step $i$. We simply denote it as $\bm{M}_{i}$.

Comment@TimeSpan encoder. The sequence of comments at each time step in the
context window $\mathbbm{M}$=$\\{\bm{M}_{t-l},...,\bm{M}_{t-1},$
$\bm{M}_{t+1},...,$ $\bm{M}_{t+l}\\}$ with position embedding is fed to the
Comment@TimeSpan encoder to produce contextualized comment context embedding.
$\bm{{C}^{{}^{\prime}}}\in\mathbb{R}^{2l\times{d}},\bm{{C}^{{}^{\prime}}}=Transformer_{c}(\mathbbm{M})$.

Knowledge encoder. We further incorporate external knowledge to enhance the
informativeness and diversity of generated comments. We first recall relevant
knowledge facts based on the comment context. We then concatenate and tokenize
them into a word sequence
$\bm{K}$=$\\{\bm{k}_{1},\bm{k}_{2},...,\bm{k}_{m}\\}$, where $m$ denotes the
maximum length of knowledge words. The knowledge encoder first performs self
attention among knowledge words. Then, we use the Comment@TimeStep encoding
$\bm{M}$=$\\{\bm{M}_{t-l},...,\bm{M}_{t-1},\bm{M}_{t+1},...,\bm{M}_{t+l}\\}$
as query to perform cross attention for modality interaction and denoising.
The comment context is beneficial for attending to related information and
ignoring the noise in the recalled knowledge. The Knowledge Encoder output
$\bm{K^{{}^{\prime}}}\in\mathbb{R}^{2l\times{d}}$ is produced by

$\displaystyle\tilde{\bm{K}}$
$\displaystyle=SelfAttention_{k}(\bm{K},\bm{K},\bm{K}),$
$\displaystyle\bm{{K}^{{}^{\prime}}}$
$\displaystyle=CrossAttention_{k}({\bm{M}},\bm{\tilde{K}},\bm{\tilde{K}}).$
(1)

Cross encoder. The outputs of visual encoder, knowledge encoder, and
Comment@TimeSpan encoder are then concatenated as the input sequence to the
cross encoder for inter-modality interaction. We add a token type embedding to
mark the modality of each token. Furthermore, we notice that viewing period is
related to the user comment pattern. For example, users tend to express
greetings at the beginning of the video. In the middle, live comments are more
about the discussions of story and characters. While at the end, most comments
are emotional expressions or farewell greetings. We quantify the viewing
period into five stages and add a period type embedding. The output of the
cross encoder is
$\bm{W}\in\mathbb{R}^{(6l+1)\times{d}},{\bm{W}}$=$Transformer_{cross}([\bm{V^{{}^{\prime}}};\bm{C^{{}^{\prime}}};\bm{K^{{}^{\prime}}}])$.

Decoder. Based on the cross encoder output $\bm{W}$, a transformer decoder
produces the hidden state $\bm{D}\in\mathbb{R}^{2l\times{d}}$ which is
projected into prediction $\bm{P}\in\mathbb{R}^{g\times{vocab\\_size}}$ by a
linear layer, and then generates the comment
$\bm{Y}$=$\\{\bm{y}_{1},\bm{y}_{2},...,\bm{y}_{g}\\}$.

$\displaystyle{\bm{D}}$ $\displaystyle=Transformer_{decoder}(\bm{W}),$
$\displaystyle{\bm{P}}$ $\displaystyle=Linear(\bm{D}).$ (2)

###  IV-B Knowledge enhancing

As shown in the right side of Fig.2, KLVCG is enhanced by two types of
external knowledge: the knowledge graph and the comments from other videos.
Enhancing by knowledge graph. We choose
Ownthink999https://github.com/ownthink/KnowledgeGraphData as knowledge source
for general datasets (Livebot and VideoIC) and FilmkG [20] for the movie
dataset (MovieLC). Ownthink is a public open-domain knowledge graph in Chinese
with 140 million facts. FilmKG contains 8,090 entities and 98,661 facts for
the film domain. All the facts are organized in the triplet format <entity1,
relation, entity2>. Then, we recall knowledge facts based on the keywords of
context comments. We build the keyword set for each video by TF-IDF value.
These words are used as searching entities to link the knowledge facts. Figure
2 shows that our method is able to recall external knowledge facts like the
awards and representative works of the actor, which is relevant to the content
and helpful for enjoying the video.

Enhancing by the comments from other videos. The comments from other videos
can also provide useful information. We recall comments about the same
entities from other videos. Similar to the above strategy, we select noun
words of context comments by TF-IDF value as key entities for each video. Then
we concatenate retrieved comments with original context comments. The case in
the right side of Fig. 2 shows that the retrieved comment points out the
semantic relation between _the Spider-man_ and _the Hacksaw Ridge_.

###  IV-C Training strategy

Pre-training. We incorporate the external knowledge via the masked language
prediction task. We randomly mask 30% words of the target comment
$\bm{Y}$=$\\{\bm{y}_{1},\bm{y}_{2},...,\bm{y}_{g}\\}$. For these masked
locations, 80% of them are replaced by a [MASK] token, and 10% are replaced by
a random word. The pre-training objective is to predict the masked words
$\bm{y}_{\mathrm{m}}$ based on the seen ones $\bm{y}_{\setminus\mathrm{m}}$.
We use the cross-entropy loss as follows:

$\mathcal{L}_{\mathrm{mask}}=-\mathbb{E}_{\bm{y}_{\mathrm{m}}\sim\bm{Y}}\log
p(\bm{y}_{\mathrm{m}}|\bm{y}_{\setminus\mathrm{m}},\bm{P}).$ (3)

Fine-tuning. The decoder generates the comments in an auto-regressive manner.
We also use the cross-entropy loss in the fine-tuning stage:

$\mathcal{L}_{\mathrm{gen}}=-\mathbb{E}_{\bm{y}_{i}\sim\bm{Y}}\log
p(\bm{y}_{i}|\bm{y}_{<i},\bm{P}).$ (4)

##  V Experiments

###  V-A Experiment settings

Evaluation setup. We evaluate the comment generation performance in a ranking
manner following previous works [1, 21]. The common practice is to ask the
model to rank 100 candidate comments according to its generation
probabilities. We average the cross-entropy losses of each token in the
comment as the ranking score. The metrics for retrieval, including Recall@k
(R@k), Mean Rank (MR), and Mean Reciprocal Rank (MRR) are reported. The
candidate comments include 5 ground-truth comments (posted by viewers at the
target TimeStep) and some negative comments chosen from the training set in 3
ways: 1) Popular: 20 most frequent comments. 2) Plausible: 20 comments with
the highest TF-IDF cosine similarity to the context comments. 3) Random: the
rest comments are picked randomly. Further details are put in the
supplementary material.

TABLE III: Comparison between UT (Unified Transformer) [1], MML-CG [2], and
KLVCG. KLVCG+ represents results of our model pre-trained on the mixture of
all three datasets.

Livebot | R@1↑ | R@5↑ | R@10↑ | MR↓ | MRR↑
---|---|---|---|---|---
UT | 9.65 | 35.48 | 53.62 | 14.98 | 0.230
MML-CG | 10.42 | 36.43 | 54.81 | 15.64 | 0.239
KLVCG | 13.49 | 41.43 | 59.31 | 13.09 | 0.276
KLVCG+ | 14.88 | 44.81 | 62.50 | 11.91 | 0.295
MovieLC | R@1↑ | R@5↑ | R@10↑ | MR↓ | MRR↑
UT | 6.24 | 18.98 | 31.98 | 23.76 | 0.147
MML-CG | 6.25 | 17.81 | 30.64 | 24.70 | 0.143
KLVCG | 7.36 | 19.26 | 29.92 | 24.87 | 0.154
KLVCG+ | 8.01 | 20.51 | 31.68 | 23.71 | 0.163
VideoIC | R@1↑ | R@5↑ | R@10↑ | MR↓ | MRR↑
UT | 30.46 | 55.17 | 68.92 | 9.96 | 0.428
MML-CG | 31.26 | 55.15 | 68.70 | 10.23 | 0.433
KLVCG | 34.08 | 57.22 | 71.37 | 9.51 | 0.458
KLVCG+ | 34.11 | 57.33 | 71.32 | 9.43 | 0.459

Training setup. We set the context window as $[t$-$5,t$+$5]$. The max
generated word length is set as $g$=$20$, including [BOS] and [EOS] tokens. We
adopt teacher-forcing for training and evaluation, and apply beam search for
inference. The beam size is set to 5. For the encoder-decoder framework, the
transformer hidden size $d$ is set to 384. The visual encoder,
Comment@TimeStep encoder, and Comment@TimeSpan encoder all have 2 layers
transformer blocks with 6 attention heads. The knowledge encoder consists of a
self-attention block and a cross-attention block both with 6 attention heads.
The cross encoder has 2 layers transformer blocks with 12 attention heads. The
decoder has 1 layer transformer block with 12 attention heads. We run
experiments on 4 1080Ti GPUs with batch size 128. The learning rate for both
pre-training and fine-tuning is set as 0.0001 and decays in the same way as
UniVL [6]. More details can be found in the supplementary material.

###  V-B Main results

We compare to two state-of-the-art baseline models: 1) Unified Transformer:
The first live comment generation model that employs transformers with
multiple blocks [1]. 2) MML-CG: The model enhances modalities interaction by
multi-modal transformer and multi-task learning [2].

In Table III, the ’KLVCG’ row shows the results from our models that are pre-
trained on the target dataset. Numbers in red mark the highest results, and
numbers in blue are the second-best results. Our KLVCG model significantly
outperforms baselines on all three datasets in almost all metrics. On the
user-generated short videos dataset Livebot, the Recall@1 is boosted from 9.65
to 13.49, the MRR is improved from 0.230 to 0.276. On the larger dataset
VideoIC, the Recall@1 of our KLVCG model also increases from 30.46 to 34.08.
On the long movie video dataset MovieLC, the performance metrics are lower
than that on the other two datasets, which indicates more challenges in long
video understanding and comment generation. However, the performance of KLVCG
still improves by incorporating knowledge (from 6.24 to 8.01). When mixing all
three datasets for pre-training, performances are further improved as shown in
the ’KLVCG+’ row.

According to the results, knowledge enhancement is helpful for generating live
video comments for both general short videos and long movie videos.
Furthermore, the parameter size of our model (43M) is smaller than that of the
MML-CG model (78M) and the Unified Transformer model (82M). It indicates that
the performance improvement comes from our model design rather than more
parameters.

###  V-C Robustness in sparse context scenarios

Fig.3 shows the performance trend under different sparse context scenarios on
the Livebot dataset (results on all three datasets are shown in the
supplementary material). We reduce the context comment density to 80%, 50%,
and 20% respectively. Results show that even in sparse context scenarios, our
model significantly outperforms MML-CG in a wide range of the context comment
density. Experiment results demonstrate higher robustness of our model in
sparse context scenarios, which is important for real applications.

###  V-D Ablation study

We carry out the ablation study of KLVCG model framework on MovieLC and
Livebot datasets. As reported in Table IV, we first ablate the performance of
our framework trained from scratch without pre-training and other auxiliary
information, which obviously outperforms the baselines as shown in the first
row. Adding the pre-training stage boosts the performance (row 2). Both
enhancing by knowledge graphs (row 3) and by comments from other videos (row
4) bring additional gain to the general video dataset Livebot and film domain
dataset MovieLC. In addition, considering the period type is also beneficial
to the generation process (row 5). In summary, all the designed components in
our model contribute to the performance improvement.

TABLE IV: Ablation study. Basic: Our framework trained from scratch. MLM: Adding a pre-training stage with masked language prediction task. KG: Enhancing by the knowledge graph. AC: Enhancing by comments from other videos. Period: Adding the period embedding.  Livebot | R@1↑ | R@5↑ | R@10↑ | MR↓ | MRR↑
---|---|---|---|---|---
Basic | 12.33 | 39.98 | 56.57 | 14.09 | 0.262
+MLM | 12.54 | 40.42 | 57.57 | 13.32 | 0.266
+KG | 12.90 | 41.61 | 58.90 | 13.18 | 0.272
+AC | 13.29 | 41.35 | 58.57 | 13.22 | 0.273
+Period | 13.49 | 41.43 | 59.31 | 13.09 | 0.276
MovieLC | R@1↑ | R@5↑ | R@10↑ | MR↓ | MRR↑
Basic | 6.41 | 18.77 | 29.50 | 25.53 | 0.146
+MLM | 7.30 | 18.30 | 28.68 | 25.39 | 0.151
+KG | 7.30 | 19.03 | 29.32 | 25.00 | 0.153
+AC | 7.35 | 18.81 | 29.69 | 24.82 | 0.154
+Period | 7.36 | 19.26 | 29.92 | 24.87 | 0.154
Figure 3: Performance under sparse context scenarios. The KLVCG model (solid
lines) consistently outperforms the MML-CG baseline (dashed lines).

###  V-E Human evaluation

We also carry out the human evaluation by recruiting 15 experienced live
comments users. They are asked to choose the best comment out of candidates
that are generated by Unified Transformer, MML-CG, and our model KLVCG. For
the 900 testing samples, 44% of the KLVCG generated comments are selected as
the best, while only 15% of the MML-CG generated comments and 11% of the UT
generated comments are selected as the best. Our KLVCG model clearly wins the
preference of users.

Figure 4: Generation case of KLVCG (in orange), MML-CG (in green), Unified
Transformer (in blue), and the ground-truth (in black). Best viewed in color.

###  V-F Case study

Examples of generated comments on the MovieLC dataset are visualized in Fig.4.
Our model (in orange) can successfully introduce knowledge like the full name
of the actor (_Leonardo Dicaprio_) and his other masterpiece (_Catch Me If You
Can_), which do not appear in the original comment context. More cases can be
found in the supplementary material. Furthermore, we found that the KLVCG
model can generate non-null comments for 97% of the testing samples, while
MML-CG and UT models can only reach 32% and 62%. It indicates that the
knowledge enhancement helps the model to generate meaningful content in more
scenarios.

##  VI Conclusion

In this work, we build a Movie live comments (MovieLC) dataset to support
research on live comments generation for long videos. We also propose a novel
knowledge enhanced model (KLVCG), which leverages external knowledge to
improve the diversity and informativeness of generated comments. Extensive
experiments on three datasets demonstrate that our model significantly
outperforms the competing approaches. The human evaluation and the case study
further show that our model can generate more meaningful live comments. In the
future work, we will further explore long video understanding and leveraging
rich external knowledge.

##  VII Acknowledgments

This work was partially supported by National Natural Science Foundation of
China (No. 62072462), National Key R&D Program of China (No. 2020AAA0108600).

## References

  * [1] S. Ma, L. Cui, D. Dai, F. Wei, and X. Sun, “Livebot: Generating live video comments based on visual and textual contexts,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, no. 01, 2019, pp. 6810–6817.
  * [2] W. Wang, J. Chen, and Q. Jin, “Videoic: A video interactive comments dataset and multimodal multitask learning for comments generation,” in _Proceedings of the 28th ACM International Conference on Multimedia_ , 2020, pp. 2599–2607.
  * [3] H. Wu, F. Pitié, and G. Jones, “Cold start problem for automated live video comments,” in _Proceedings of the Third Workshop on Multimodal Artificial Intelligence_ , 2021, pp. 54–62.
  * [4] Z. Zeng, N. Gao, C. Xue, and C. Tu, “Plvcg: A pretraining based model for live video comment generation,” in _Advances in Knowledge Discovery and Data Mining: 25th Pacific-Asia Conference, PAKDD 2021, Virtual Event, May 11–14, 2021, Proceedings, Part II_. Springer, 2021, pp. 690–702.
  * [5] Z. Zhang, Z. Yin, S. Ren, X. Li, and S. Li, “Dca: Diversified co-attention towards informative live video commenting,” in _Natural Language Processing and Chinese Computing: 9th CCF International Conference, NLPCC 2020, Zhengzhou, China, October 14–18, 2020, Proceedings, Part II 9_. Springer, 2020, pp. 3–15.
  * [6] H. Luo, L. Ji, B. Shi, H. Huang, N. Duan, T. Li, J. Li, T. Bharti, and M. Zhou, “Univl: A unified video and language pre-training model for multimodal understanding and generation,” _arXiv preprint arXiv:2002.06353_ , 2020.
  * [7] C. Duan, L. Cui, S. Ma, F. Wei, C. Zhu, and T. Zhao, “Multimodal matching transformer for live commenting,” _arXiv preprint arXiv:2002.02649_ , 2020\.
  * [8] H. Wu, G. J. F. Jones, and F. Pitie, “Knowing where and what to write in automated live video comments: A unified multi-task approach,” in _Proceedings of the 2021 International Conference on Multimodal Interaction_ , 2021, pp. 619–627.
  * [9] K. Marino, X. Chen, D. Parikh, A. Gupta, and M. Rohrbach, “Krisp: Integrating implicit and symbolic knowledge for open-domain knowledge-based vqa,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 14 111–14 121.
  * [10] F. Gao, Q. Ping, G. Thattai, A. Reganti, Y. N. Wu, and P. Natarajan, “Transform-retrieve-generate: Natural language-centric outside-knowledge visual question answering,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 5067–5077.
  * [11] P. Zhou, K. Gopalakrishnan, B. Hedayatnia, S. Kim, J. Pujara, X. Ren, Y. Liu, and D. Hakkani-Tur, “Think before you speak: Explicitly generating implicit commonsense knowledge for response generation,” in _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 2022, pp. 1237–1252.
  * [12] S. Shen, V. Pérez-Rosas, C. Welch, S. Poria, and R. Mihalcea, “Knowledge enhanced reflection generation for counseling dialogues,” in _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 2022, pp. 3096–3107.
  * [13] Z. Zhang, X. Han, Z. Liu, X. Jiang, M. Sun, and Q. Liu, “Ernie: Enhanced language representation with informative entities,” _arXiv preprint arXiv:1905.07129_ , 2019.
  * [14] W. Liu, P. Zhou, Z. Zhao, Z. Wang, Q. Ju, H. Deng, and P. Wang, “K-bert: Enabling language representation with knowledge graph,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 03, 2020, pp. 2901–2908.
  * [15] T. Sun, Y. Shao, X. Qiu, Q. Guo, Y. Hu, X. Huang, and Z. Zhang, “Colake: Contextualized language and knowledge embedding,” _arXiv preprint arXiv:2010.00309_ , 2020.
  * [16] A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko, “Translating embeddings for modeling multi-relational data,” _Advances in neural information processing systems_ , vol. 26, 2013.
  * [17] P. Papalampidi, F. Keller, and M. Lapata, “Movie plot analysis via turning point identification,” _arXiv:1908.10328_ , 2019.
  * [18] J. Liu, W. Chen, Y. Cheng, Z. Gan, L. Yu, Y. Yang, and J. Liu, “Violin: A large-scale dataset for video-and-language inference,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 10 900–10 910.
  * [19] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [20] H. Zhou, C. Zheng, K. Huang, M. Huang, and X. Zhu, “Kdconv: A chinese multi-domain dialogue dataset towards multi-turn knowledge-driven conversation,” _arXiv preprint arXiv:2004.04100_ , 2020.
  * [21] H. Wu, G. J. Jones, and F. Pitie, “Response to livebot: Generating live video comments based on visual and textual contexts,” _arXiv preprint arXiv:2006.03022_ , 2020.


# Revisiting Garg’s 2-Approximation Algorithm
for the $k$-MST Problem in Graphs

Emmett Breen  Renee Mirka  Zichen Wang  David P. Williamson

({ejb284, rem379, zw336<EMAIL_ADDRESS>
Cornell University, Ithaca, NY 14850)

###### Abstract

This paper revisits the 2-approximation algorithm for $k$-MST presented by
Garg [9] in light of a recent paper of Paul et al. [14]. In the $k$-MST
problem, the goal is to return a tree spanning $k$ vertices of minimum total
edge cost. Paul et al. [14] extend Garg’s primal-dual subroutine to improve
the approximation ratios for the budgeted prize-collecting traveling salesman
and minimum spanning tree problems. We follow their algorithm and analysis to
provide a cleaner version of Garg’s result. Additionally, we introduce the
novel concept of a kernel which allows an easier visualization of the stages
of the algorithm and a clearer understanding of the pruning phase. Other
notable updates include presenting a linear programming formulation of the
$k$-MST problem, including pseudocode, replacing the coloring scheme used by
Garg with the simpler concept of neutral sets, and providing an explicit
potential function.

##  1 Introduction

Given as input an undirected graph $G=(V,E)$ and non-negative costs $c_{e}$
for each edge $e\in E$, the goal of the $k$-MST problem is to find a tree
spanning at least $k$ vertices of minimum total cost. In the rooted case of
the problem, a special root vertex $r$ is denoted which must be contained in
the final tree, whereas no such $r$ exists for the unrooted case. These two
cases are equivalent for the $k$-MST problem: Garg [9] shows that an
$\alpha$-approximation algorithm for one version can be translated into an
$\alpha$-approximation algorithm for the other. An $\alpha$-approximation
algorithm for $k$-MST is a polynomial-time algorithm which returns a solution
at most $\alpha$ times the cost of the optimal tree.

Approximation algorithms have been considered for $k$-MST since Ravi et al.
introduced the problem [15]. They proved the problem is NP-hard and presented
a $3\sqrt{k}$-approximation algorithm. Since then, one line of work by
numerous authors [4, 6, 8, 3] developed a $(2+\epsilon)$-approximation
algorithm running in time polynomial in $\epsilon^{-1}$ [2]. Currently, the
best known approximation is a 2-approximation algorithm by Garg using primal-
dual techniques [9]. A separate line of work considers a special case of
$k$-MST where the input is given by $n$ points in the plane with edge costs
determined by the Euclidean metric [15, 10, 7, 5, 13, 1, 12].

This paper focuses on Garg’s result. His 2-approximation algorithm is not only
the best known for $k$-MST, but Garg also shows that his algorithm leads to a
2-approximation algorithm for the $k$-TSP problem (where one seeks a min-cost
tour on at least $k$ vertices instead of a tree and edge costs satisfy the
triangle inequality) and 3-approximation algorithm for the budgeted version of
$k$-MST (where a budget $B$ is given and one seeks to maximize the number of
vertices in a tree of cost at most $B$) due to an observation by Johnson et
al. [11]. More recently, Paul et al. have extended Garg’s technique to improve
the approximation algorithms for the budgeted prize-collecting traveling
salesman and minimum spanning tree problems [14]. We revisit Garg’s algorithm
and analysis in light of the paper of Paul et al. In particular, we seek to
provide a cleaner version of Garg’s algorithm and analysis by adapting the
results of Paul et al. We use Paul et al.’s explicit potential function and
use of neutral sets to replace the coloring scheme used by Garg. Both of these
changes improve the clarity and comprehensibility of the initial analysis.
Additionally, and distinct from both previous papers, we introduce the notion
of a kernel in this primal-dual algorithm; its use in part enables a clearer
visualization of the mechanics of the algorithm. We believe this perspective
yields a more accessible version of Garg’s result.

The structure of the paper is as follows. Section 2 introduces a linear
programming formulation of the $k$-MST problem. Section 3 describes the
primal-dual subroutine used by Garg, and Section 4 provides an overview of the
entire algorithm along with a lower bound on the cost of the optimal tree. In
Sections 5 and 6, we describe the details of finding a specific tree through
parameter setting and modifying the results of the primal-dual subroutine.
Finally, Section 7 proves the 2-approximation.

##  2 Linear Programming Formulation

In this section, we provide a linear programming (LP) relaxation of the
$k$-MST problem. The constraints in the dual LP will determine when an $event$
happens in the primal-dual subroutine.

For each $S\subseteq V$, let variable $z_{S}\in\\{0,1\\}$ denote whether $S$
constitutes the vertices of the spanning tree. For each edge $e\in E$, let
variable $x_{e}\in\\{0,1\\}$ denote whether edge $e$ is included in the
spanning tree. Then, the following is a linear programming relaxation for the
k-MST problem:

minimize $\displaystyle~{}~{}\sum_{e\in E}c_{e}x_{e}$ subject to
$\displaystyle\sum_{e:e\in\delta(S)}x_{e}\geq\sum_{S_{T}:S\subset
S_{T}}z_{S_{T}}\qquad\forall S\subset V,$ $\displaystyle~{}~{}\sum_{S\subseteq
V}|S|z_{S}\geq k,$ $\displaystyle~{}~{}\sum_{S\subseteq V}z_{S}\leq 1,$
$\displaystyle~{}~{}~{}z_{S},~{}x_{e}\geq 0.$

The first constraint guarantees that the spanning tree is connected. If $S$ is
a strict subset of the vertices $S_{T}$ of a spanning tree $T$, then there
must be at least one edge across $\delta(S)$, the cut of $S$. Given there are
no negative-cost edges, any optimal integral solution to the LP will be a tree
and have $x_{e}\leq 1$ for each $e\in E$, and thus these constraints are
omitted. We shall also be careful with our subsequent approximation algorithm
to not violate these two constraints. We can now write down the dual of this
linear program:

maximize $\displaystyle~{}~{}\lambda_{1}k-\lambda_{2}$ subject to
$\displaystyle\sum_{S:e\in\delta(S)}y_{S}\leq c_{e}\qquad\forall e\in E,$
$\displaystyle~{}~{}\sum_{T\subset
S}y_{T}+\lambda_{2}\geq\lambda_{1}|S|\qquad\forall S\subset V,$
$\displaystyle~{}~{}\lambda_{1},\lambda_{2},y_{S}\geq 0.$

To produce a tree, we use a primal-dual subroutine for these formulations that
will be described in the next section. However, we first observe (similar to
Paul et al.) that for any $\lambda_{1}$ and $y$ satisfying the edge
constraints, we can find a $\lambda_{2}$ value satisfying the subset
constraints. Particularly, we can let $\lambda_{2}$ be the maximum of 0 and
$\max_{S\subset V}\\{\lambda_{1}|S|-\sum_{S_{T}\subset S}y_{S_{T}}\\}$ and we
have a feasible dual solution. Therefore, a key component of this algorithm
and the following analysis is choosing a $\lambda_{1}$ value leading to a
primal-dual subroutine solution with a tree of the appropriate size. In what
follows, we’ll see that too small of a $\lambda_{1}$ value leads to too few
selected edges, whereas a value of $\lambda_{1}$ that is too large leads to
too many selected edges. More details are provided in Section 5.

##  3 Primal-Dual Subroutine

We now present the primal-dual subroutine used by Garg. The algorithm assumes
a fixed $\lambda_{1}$ and, instead of explicitly finding the minimal
$\lambda_{2}$ value, greedily grows a forest with respect to a heuristic
function of the dual variables. In our case, the function is the potential
that we define as below.

######  Definition 1.

For any subset $S\subseteq V$, the potential of $S$ is

$\pi(S)=\lambda_{1}|S|-\sum_{T:T\subset S}y_{T}.$

######  Definition 2.

A subset $S\subseteq V$ is neutral if $\displaystyle\sum_{T:T\subseteq
S}y_{T}=\lambda_{1}|S|$, or equivalently, if $y_{S}=\pi(S)$.

Intuitively, each vertex has a budget of $\lambda_{1}$, and we spend the
budget amassed in connecting vertices to cover the costs of the edges. In this
way, we are able to consider the vertices and edges of a set $S$ as a single
variable $\pi(S)$ that measures how much budget we have left to spend on
future edges. The objective is to connect $k$ vertices with the cheapest
possible edge cost; this corresponds well to maximizing the potential.

Algorithm 1 Primal-Dual Subroutine PD($\lambda_{1}$)

$y_{S}\leftarrow 0$

PD $\leftarrow\emptyset$

$\mathcal{C}\leftarrow\\{\\{v\\}:v\in V\\}$

while $\mathcal{C}\neq\emptyset$ do

raise all $y_{S}$ corresponding to active components uniformly until either

if $y_{S}=\pi(S)$ then

$\mathcal{C}\leftarrow\mathcal{C}-S$

else if $\sum_{S:e\in\delta(S)}y_{S}=c_{e}$ for some $e$ between sets
$S_{1},S_{2}$ then

PD $\leftarrow$ PD $\cup\\{e\\}$

$\mathcal{C}\leftarrow\mathcal{C}-S_{1}-S_{2}$

$\mathcal{C}\leftarrow\mathcal{C}\cup\\{S_{1}\cup S_{2}\\}$

end if

end while

return PD

The primal-dual subroutine is given in Algorithm 1. Described in words,
initially $y_{S}=0$ for all $S$, and all sets consisting of a single vertex
are active. At any stage of the algorithm with active components, we uniformly
increase $y_{S}$ corresponding to all active components until either a set
event or an edge event happens. Here, a set event is a set becoming neutral,
while an edge event is the constraint corresponding to an edge becoming tight
(that is, the dual constraint is met with equality). If a set becomes neutral,
then we mark this set inactive and remove it from the set of active
components. If the dual constraint for an edge between sets $S_{1}$ and
$S_{2}$ reaches equality, then the edge is tight. We add this edge to the set
of selected edges, mark $S_{1}$ and $S_{2}$ inactive if not already, and mark
$S_{1}\cup S_{2}$ active. We’ll sometimes say that we have merged the two
sets.

We make a few observations about the structure of the result of the primal-
dual subroutine. First, the collection $\mathcal{S}$ of all sets that are ever
active during the subroutine is laminar; that is, for any pair of sets
$A,B\in\mathcal{S}$, either $A\subseteq B$, $B\subseteq A$, or $A\cap
B=\emptyset$. Initially, all sets consisting of a single vertex are active. By
design, the only way a new, larger set becomes active is through merging two
previously active sets when an edge event occurs. This maintains the laminar
property. Secondly, the subroutine returns a forest. Each time an edge event
occurs, two trees are connected into a larger tree. Furthermore, no cycles can
exist. If an edge $(u,v)$ was added that created a cycle, there must have been
an active set that contained exactly one of $u$ or $v$. However, since $u$ and
$v$ must already be connected (otherwise this edge would not complete a
cycle), any active set that contains $u$ or $v$ must contain them both. If two
edges that would complete a cycle go tight at the same time, we choose one of
the edges through a tie-breaking procedure described in Sections 5 and 6.

We observe that this procedure always maintains a feasible dual solution. Note
that all dual edge constraints are initially satisfied with $y_{S}=0$.
Furthermore, if an edge becomes tight, the sets corresponding to the endpoints
of the edge are marked inactive, so the constraint will never be violated.

Active sets play a crucial role in the subroutine, as these are the sets with
the capability for growth. Because of this, we formalize the decomposition of
currently-active or once-active sets into neutral subsets and subsets of
always-active vertices through the notion of a kernel, one of the key points
of distinction between our work and Garg’s initial presentation as well as
Paul et al.’s work.

######  Definition 3.

For an active set $S$ corresponding to a tree $T$ in the set of tight edges of
$PD$, the kernel of $S$, denoted by $K(S)$, is the smallest cardinality subset
of $S$ such that

  * 1.

if $v\in S$ has always been part of an active set, then $v\in K(S)$,

  * 2.

$K(S)$ is connected in $T$, and

  * 3.

for every once-active set $I\subset S$ either $I\subset K(S)$ or $I\cap
K(S)=\emptyset$.

The kernel of a once-active set $S$ is the kernel at the moment $S$ becomes
neutral.

Since initially $y_{S}=0$ for all subsets $S$ and all sets consisting of a
single vertex are active, every vertex is the kernel of itself at the start of
the primal-dual subroutine. By the definition of the kernel, we know that the
kernel of a once-active (but now inactive) set is the kernel of the set when
it went neutral. It remains to understand how the kernel changes as active
sets grow throughout the primal-dual subroutine. We illustrate this growth
through two possible cases:

  * 1.

an active set $S$ merges with an inactive set $I$ or

  * 2.

an active set $S$ merges with another active set $A$.

In the first case, the kernel of $S\cup I$ is simply the kernel of $S$. Since
$I$ was inactive at the time of the merge, every vertex in $I$ has been part
of an inactive set. Therefore adding any vertices of $I$ to $K(S)$ would
simply increase the cardinality of the kernel. Since we want the minimal
cardinality set maintaining connectivity (and $K(S)$ is already connnected
since it was previously a kernel), we do not add any of the vertices of $I$.
See Figure 1.

(a) An active and inactive set with their kernels before an edge event
occurring at the dashed edge.

(b) The new active set and its kernel after the merge.

Figure 1: These figures illustrate how the sets and kernels change when an
active set merges with an inactive set. Sets surrounded by a bold (resp.
dashed) line are active (resp. inactive). Sets with a grey background are the
kernel of the smallest active or inactive set they are contained in.

In the second case, the kernel of $S\cup A$ will contain both the kernel of
$S$ and the kernel of $A$ since both of these contain vertices which have
always been contained in active sets. However, we must be careful since the
edge event merging $S$ and $A$ may not occur on an edge connecting the kernel
of $S$ to the kernel of $A$ and the resulting set should be connected. In this
case, we must add the fewest possible number of once-active subsets of $S$ and
$A$ by including only the ones on the path from $K(S)$ to $K(A)$. This
maintains that $K(S\cup A)$ is connected in the new tree. See Figure 2.

(a) Two active sets with their kernels before an edge event occurring at the
dashed edge.

(b) The new active set and its kernel after the merge.

Figure 2: These figures illustrate how the sets and kernels change when an two
active sets merge. Sets surrounded by a bold (resp. dashed) line are active
(resp. inactive). Sets with a grey background are the kernel of the smallest
active or inactive set they are contained in.

The kernel is used in the next step of the algorithm after the primal-dual
subroutine – the pruning phase. In this phase, we want to remove sets of
vertices that do not help us achieve our end goal. Particularly, we want to
remove neutral sets without disconnecting any tree in the forest returned by
the primal-dual subroutine. We do so by pruning each tree $T$, with vertex set
$S_{T}$, in the forest returned by $PD$ to return exactly the edge-set
determined by the kernel of $S_{T}$. In particular, a pruned tree $T$ is given
by $E(K(S_{T}))\cap T$ where $E(S)=\\{(u,v)\in E:u,v\in S\\}$. The following
lemma shows that this has our desired effect; the proof is delayed until
Section 7. For sets $S^{\prime}\subset S\subset V$, let
$\delta_{K(S)}(S^{\prime})=\\{(u,v)\in E(S):u\in S^{\prime},v\in
K(S)-S^{\prime}\\}.$

######  Lemma 1.

The kernel $K(S)$ of a set $S$ contains no neutral subset $N\subset K(S)$ such
that $|\delta_{K(S)}(N)|=1.$

Clearly the size of each tree may decrease during the pruning phase, so
measures must be taken to ensure we have a tree of suitable size at the end of
the primal-dual subroutine. Recalling that we can find a feasible
$\lambda_{2}$ value for any $\lambda_{1}$ and feasible $y_{S}$ solution, we
carefully select $\lambda_{1}$ guaranteeing at least one kernel in our primal-
dual output forest has at least $k$ vertices. After pruning, we execute a
picking routine to obtain a tree with exactly $k$ vertices such that the
2-approximation holds. The details of this selection of $\lambda_{1}$ and the
picking routine implemented after the primal-dual subroutine and pruning occur
are described in the following sections.

##  4 Algorithm Overview

In this section, we provide an overview of how the forest from the primal-dual
subroutine is used to construct a feasible $k$-MST. Assume we have run the
primal-dual subroutine with some value of $\lambda_{1}$ to find a feasible
dual solution $(y,\lambda_{1},\lambda_{2})$, though we may not know
$\lambda_{2}$ exactly. We also have a forest $F$ from which we need to select
a tree spanning $k$ vertices. In order to do so, we need to guarantee that
there exists a tree in $F$ containing at least $k$ vertices after it is
pruned. If the fixed $\lambda_{1}$ is too small, this may not be the case as a
small $\lambda_{1}$ allows sets to become neutral earlier which limits the
potential for growth. On the other hand, if $\lambda_{1}$ is too large, the
primal-dual subroutine degrades to greedily selecting the cheapest edges,
which is sub-optimal. In order to balance these two scenarios, we search for
an appropriate $\lambda_{1}$ value. Specifically, we identify a $\lambda_{1}$
value such that $PD(\lambda_{1}^{-})$ returns a forest where every pruned tree
is too small and $PD(\lambda_{1}^{+})$ contains at least one pruned tree large
enough. Here $x^{-}=x-\epsilon$ and $x^{+}=x+\epsilon$, where $\epsilon$ is
arbitrarily small. Once we have this threshold value of $\lambda_{1}$, we
prune our selected tree to return a kernel with at least $k$ vertices and
bounded cost on the corresponding tree. Finally, we select a sub-tree of our
pruned tree containing exactly $k$ vertices.

Before describing how we choose a $\lambda_{1}$ value, we derive a lower bound
of the cost of the optimal $k$-MST in terms of the potential function that
works for any choice of $\lambda_{1}$. In the following sections, we will see
how to set $\lambda_{1}$ to give an upper bound. Together, this will give us a
2-approximation.

Let $\mathcal{S}$ be the laminar set of all once-active sets plus the set of
all vertices. Denote $T^{*}$ the optimal $k$-MST, $S_{T^{*}}$ its set of
vertices, and $S_{1}$ the set with the minimal potential in $\mathcal{S}$ such
that $S_{T^{*}}\subset S_{1}$. Since $V\in\mathcal{S}$, such an $S_{1}$ always
exists. In general, for a tree, we will refer to the set of edges by $T$ and
the corresponding set of vertices by $S_{T}$.

######  Lemma 2.

For any $S\subseteq V$, $\displaystyle\sum_{U:U\subseteq
S}y_{U}\leq\lambda_{1}|S|$.

###### Proof.

If $S$ was once active, then the inequality holds by the design of the primal-
dual subroutine. We prove this by induction. Suppose $S_{1}$ and $S_{2}$
merged to form $S$, and

$\sum_{U:U\subseteq S_{1}}y_{U}\leq\lambda_{1}|S_{1}|,$ $\sum_{U:U\subseteq
S_{2}}y_{U}\leq\lambda_{1}|S_{2}|.$

Initially $y_{S}=0$, so

$\displaystyle\sum_{U:U\subseteq S}y_{U}$ $\displaystyle=\sum_{U:U\subseteq
S_{1}}y_{U}+\sum_{U:U\subseteq S_{2}}y_{U}+y_{S}$
$\displaystyle\leq\lambda_{1}|S_{1}|+\lambda_{1}|S_{2}|$
$\displaystyle=\lambda_{1}|S|.$

We increase $y_{S}$ either until $S$ merges with another active set or until
$\displaystyle\sum_{U:U\subseteq S}y_{U}=\lambda_{1}|S|$ and $S$ gets marked
neutral. In either case, we no longer increase $y_{S}$, so the claim continues
to hold. For an arbitrary set $S$, we can partition it into maximal disjoint
laminar subsets $S_{1},S_{2},...,S_{c}\in\mathcal{S}$. Therefore,

$\sum_{U:U\subseteq S}y_{U}=\sum_{i=1}^{c}\sum_{U:U\subseteq
S_{i}}y_{U}\leq\sum_{i=1}^{c}\lambda_{1}|S_{i}|=\lambda_{1}|S|.$

∎

######  Theorem 1.

The minimal spanning tree has cost at least $\lambda_{1}\cdot k-\pi(S_{1})$.

###### Proof.

By the potential definition and Lemma 1,

$\displaystyle\lambda_{1}|S_{1}|$ $\displaystyle=\sum_{U:U\subset
S_{1}}y_{U}+\pi(S_{1})$ $\displaystyle=\sum_{U:U\subseteq
S_{1}-S_{T^{*}}}y_{U}+\sum_{\begin{subarray}{c}U:U\subset S_{1}\\\ U\cap
S_{T^{*}}\neq\emptyset\end{subarray}}y_{U}+\pi(S_{1})$
$\displaystyle\leq\lambda_{1}|S_{1}-S_{T^{*}}|+\sum_{\begin{subarray}{c}U:U\subset
S_{1}\\\ U\cap S_{T^{*}}\neq\emptyset\end{subarray}}y_{U}+\pi(S_{1}),\text{
so}$ $\displaystyle\lambda_{1}|S_{T^{*}}|$
$\displaystyle\leq\sum_{\begin{subarray}{c}U:U\subset S_{1}\\\ U\cap
S_{T^{*}}\neq\emptyset\end{subarray}}y_{U}+\pi(S_{1})$
$\displaystyle\leq\sum_{e\in S_{T^{*}}}\sum_{U:e\in\delta(U)}y_{U}+\pi(S_{1})$
$\displaystyle\leq\sum_{e\in S_{T^{*}}}c_{e}+\pi(S_{1}).$

The first inequality follows from Lemma 1. The third inequality says that for
every set that intersects $S_{T^{*}}$, an edge in its cut must lie in $T^{*}$.
Since we only allow edges with non-negative costs, the spanning tree is
minimal when it covers exactly $k$ vertices. By rearranging, we obtain the
claim. ∎

##  5 Setting $\lambda_{1}$

Figure 3: Finding Threshold $\lambda_{1}$. Each line represents the time for
an event to occur next in terms of $\lambda_{1}$. The bold line shows the next
event, where each segment is from a given subinterval.

We now describe how to set $\lambda_{1}$ to enable us to pick $k$ vertices
from a pruned tree in our primal-dual subroutine forest. Recall
$x^{-}=x-\epsilon$ and $x^{+}=x+\epsilon$, where $\epsilon$ is arbitrary
small. We will later use infinitesimal to refer to variables that approximate
their originals as $\epsilon\rightarrow 0$. We adapt two lemmas from Paul et
al. to the $k$-MST situation. The first tells us that we can find our desired
threshold value $\lambda_{1}$.

######  Lemma 3.

In polynomial time, we can find a threshold value $\lambda_{1}$ such that all
pruned trees of PD($\lambda_{1}^{-}$) have less than $k$ vertices and there
exists at least one pruned tree in PD($\lambda_{1}^{+}$) with at least $k$
vertices.

As the details of this proof closely mirror those of Paul et al., we omit them
here and refer the reader to Lemma 2 [14]. The key idea is that the time for
each set and edge event to occur can be represented as a linear function in
$\lambda_{1}$; see Figure 3. Then by observing the threshold $\lambda_{1}$
must occur at an intersection of these lines, we can consider smaller and
smaller intervals of $\lambda$ determined by the intersections until we find
our desired value. In particular, we recurse onto a smaller subinterval where
the next event to occur is consistent throughout the subinterval and consider
the possible events that can follow. Eventually, there must be a time
(intersection) where the difference in next events translates to a difference
in sizes of the resulting kernels; this is where our threshold $\lambda_{1}$
occurs. The next lemma tells us two important properties regarding the primal-
dual subroutine for values around our threshold $\lambda_{1}$.

######  Lemma 4.

Throughout the two subroutines $PD(\lambda_{1}^{-})$ and
$PD(\lambda_{1}^{+})$, the following two properties hold:

  * •

All active components are the same except for during infinitesimal time.

  * •

For all $S\subseteq V$, the difference between $y_{S}^{+}$ and $y_{S}^{-}$ is
infinitesimal. Here $y_{S}^{+}$ and $y_{S}^{-}$ are the dual variables when
running $PD(\lambda_{1}^{+})$ and $PD(\lambda_{1}^{-})$, respectively.

Here, again we present an overview of the proof of Lemma 3 [14] with a few
minor changes. The main observation is the claim could only fail if two
different events occur at the same time in $PD(\lambda)$, and the events cause
lasting disparity in $PD(\lambda_{1}^{-})$ and $PD(\lambda_{1}^{+})$.
Furthermore, there are four possible ways that two different events could
occur at the same time:

  * 1.

different sets go neutral in $PD(\lambda_{1}^{-})$ and $PD(\lambda_{1}^{+})$,

  * 2.

an edge goes tight in $PD(\lambda_{1}^{-})$ while a set goes neutral in
$PD(\lambda_{1}^{+})$,

  * 3.

a set goes neutral in $PD(\lambda_{1}^{-})$ while an edge goes tight in
$PD(\lambda_{1}^{+})$, or

  * 4.

different edges go tight in $PD(\lambda_{1}^{-})$ and $PD(\lambda_{1}^{+})$.

In the first case, the times for the two sets to go neutral must differ by an
infinitesimally small amount and thus one will go neutral immediately after
the other. The second case cannot occur for this problem since the time for a
set to go neutral has a positive slope in $\lambda_{1}$ while the time for an
edge to go tight has a negative slope in $\lambda_{1}$.

For the third case, if the tight edge has an endpoint in an active set
different than the set going neutral, the edge will still go tight immediately
after the set event. If the edge going tight in $PD(\lambda_{1}^{+})$ merges
the set going neutral in $PD(\lambda_{1}^{-})$ and another neutral set, the
merged set must have infinitesimally small potential and will go neutral
immediately after the edge event. This maintains the active sets. Furthermore,
if an active set merges with the set going neutral in the future in
$PD(\lambda_{1}^{-})$, the edge will go tight immediately after, still
maintaining the active sets.

Finally, for the fourth case, if the edges are between different components
one will go tight immediately after the other (similar to the first case).
Meanwhile, if they are between the same components, only one will go tight in
each subroutine but the resulting active components will be the same.

The main role of Lemma 4 is insight into the potential differences between
$PD(\lambda_{1}^{-})$ and $PD(\lambda_{1}^{+})$. In particular, there may be
subsets marked neutral in $PD(\lambda_{1}^{-})$ but with infinitesimally small
potential in $PD(\lambda_{1}^{+})$ or there may be different edges that went
tight between the same components. If, every time two events tied in
$PD(\lambda)$, we broke the tie by selecting what $PD(\lambda_{1}^{+})$ would
do, we will end up with at least one kernel having at least $k$ vertices. On
the other hand, we can consider breaking ties in favor of
$PD(\lambda_{1}^{-})$ one at a time. By doing so, we will find the smallest
$i$ such that if the first $i$ ties are broken according to
$PD(\lambda_{1}^{-})$ and the rest by $PD(\lambda_{1}^{+}),$ we return a
forest with all kernels containing less than $k$ vertices. By Lemma 3, the
dual variables only change by an infinitesimally small amount, and the only
differences occur during the pruning phase.

In finding this value of $i$, we have also either identified a neutral subset
$X$ such that if $X$ remained active our forest would contain a kernel of
appropriate size, or found two edges $e$ and $f$ between the same components
such that adding $f$ instead of $e$ returns a forest containing a kernel of
appropriate size. These two cases will play a role in picking our final set of
vertices in the next section.

##  6 Constructing a Tree

Let $\lambda_{1}$ be our found threshold value and
$(y,\lambda_{1},\lambda_{2})$ our feasible dual solution acquired through tie-
breaking in the manner described at the end of Section 5. Currently, all
kernels of our primal-dual subroutine output forest have fewer than $k$
vertices, but Section 5 tells us that either we have identified a neutral
subset $X$ such that if $X$ remained active our forest would contain a kernel
with at least $k$ vertices (Case I) or found two edges $e$ and $f$ between the
same components such that adding $f$ instead of $e$ returns a forest
containing a kernel with at least $k$ vertices (Case II). The final
construction of our tree depends on which of these cases are present and
requires us to pick $k$ vertices. Specifically, pick$(X,w,k)$ returns a sub-
tree of $X$ with $k$ vertices and contains the vertex $w$. The idea is to
inspect the last two subsets that merged to form the set. Suppose that $X_{1}$
and $X_{2}$ merged to form $X$, with edge $(u,v)$ connecting them, and that
$X_{1}$ contains $w$. If $X_{1}$ contains at least $k$ vertices, then we
invoke pick$(X_{1},w,k)$. If $X_{1}$ has less than $k$ vertices, then we pick
all vertices in $X_{1}$ and continue to pick$(X_{2},v,k-|X_{1}|)$. We repeat
the process recursively until we have picked exactly $k$ vertices.

Algorithm 2 Pick Routine pick$(X,w,k)$

let $X_{1}$ and $X_{2}$ be the two subsets that merged on edge $e=(u,v)$ to
form $X$

suppose without loss of generality that $w\in X_{1}$

if $|X_{1}|>k$ then

call pick($X_{1},w,k$)

else if $|X_{1}|<k$ then

pick all vertices in $X_{1}$

call pick($X_{2},v,k-|X_{1}|$)

else

pick all vertices in $X_{1}$

end if

In Case I, a set goes neutral the same time an edge goes tight; see Figure 4.
Let $K(S_{1})$ and $K(S_{2})$ be the two kernels of the merging two subsets
$S_{1}$ and $S_{2}$. If we break the tie by choosing the set event, then we
would end up with both $K(S_{1})$ and $K(S_{2})$ having less than $k$
vertices. On the other hand, if we break the tie by choosing the edge event,
then the new kernel $K(S_{1}\cup S_{2})=K(S_{1})\cup N_{1}\cup\dots\cup
N_{p}\cup K(S_{2})$ would have at least $k$ vertices. Here $N_{i}$ denotes the
neutral sets on the path from $K(S_{1})$ to $K(S_{2})$. Now we show how to
pick exactly $k$ vertices from this new kernel using the pick routine.
Starting from $K(S_{1})$, we select neutral sets $N_{1},N_{2},\dots,N_{q-1}$
until adding another neutral set $N_{q}$ will cause $K(S_{1})\cup
N_{1}\cup\dots\cup N_{q}$ to have at least $k$ vertices. Suppose edge
$e=(u,v)$ links $N_{q-1}$ to $N_{q}$, then pick$(N_{q},v,r)$ will pick the
remaining vertices needed, where $r=k-|K(S_{1})|-\sum_{i=1}^{q-1}|N_{i}|$ is
the number of additional vertices we need to pick.

(a) Sets $S_{1}$ and $S_{2}$ and their kernels before the edge event causing
$e$ to go tight and the set event causing $S_{2}$ to go neutral tie in
$PD(\lambda_{1})$.

(b) Sets $S_{1}$ and $S_{2}$ and their kernels after the tie is broken by
allowing $S_{2}$ to go neutral.

(c) Set $S_{1}\cup S_{2}$ and its kernel after the tie is broken by allowing
$e$ to go tight.

Figure 4: Case I. $S_{2}$ goes neutral the same time $e$ goes tight.

In Case II, two edges go tight simultaneously; see Figure 5. Again, let
$K(S_{1})$ and $K(S_{2})$ be the two kernels of the merging two subsets
$S_{1},S_{2}$. Denote $e,f$ the two edges both between $S_{1}$ and $S_{2}$. If
we choose edge $e$, then the new kernel $K(S_{1}\cup S_{2})=K(S_{1})\cup
N_{1}\cup...\cup N_{p}\cup K(S_{2})$ would have less than $k$ vertices, where
$N_{1},\dots,N_{p}$ are the neutral sets between $K(S_{1})$ and $K(S_{2})$
using edge $e$. On the other hand, if we choose edge $f$, then the new kernel
$K(S_{1}\cup S_{2})=K(S_{1})\cup N^{\prime}_{1}\cup...\cup N^{\prime}_{q}\cup
K(S_{2})$ would have at least $k$ vertices, where
$N^{\prime}_{1},\dots,N^{\prime}_{q}$ are the neutral sets between $K(S_{1})$
and $K(S_{2})$ using edge $f$. The difference clearly results from the neutral
sets in between $K(S_{1})$ and $K(S_{2})$. Once again, we pick
$K(S_{1}),N^{\prime}_{1},N^{\prime}_{2},\dots,N^{\prime}_{t-1}$ where picking
$N^{\prime}_{t}$ would give at least $k$ vertices and invoke
pick$(N^{\prime}_{t},v,r)$ to finish the rest ($N^{\prime}_{t},v,r$ defined
similar to Case I).

(a) Sets $S_{1}$ and $S_{2}$ and their kernels before the edge events causing
$e$ and $f$ to go tight tie in $PD(\lambda_{1})$.

(b) Set $S_{1}\cup S_{2}$ and its kernel after the tie is broken so $e$ goes
tight.

(c) Set $S_{1}\cup S_{2}$ and its kernel after the tie is broken so $f$ goes
tight.

Figure 5: Case II. Edges $e$ and $f$ between $S_{1}$ and $S_{2}$ go tight at
the same time.

##  7 2-Approximation

Now that we have finished describing the mechanics of the algorithm, we can
finally present the proof of the 2-approximation. Let $T^{\prime}$ denote the
tree we obtained after pruning with vertex set (kernel) $K^{\prime}$,
$T_{0}\subseteq K^{\prime}$ the tree of $k$ vertices we obtained by the pick
routine, and $S_{T_{0}}$ the set of vertices of $T_{0}$. Further, let $v$ be
the vertex in $S_{T_{0}}$ where the pick routine terminated. Before proceeding
with the necessary lemmas, we present the proof of Lemma 1 from Section 3.

###### Proof.

We prove this by induction on the number of events. In the base case, at the
start of the primal-dual subroutine, every vertex is the kernel of itself and
no neutral sets have appeared yet.

Suppose that for the first $k$ events the claim holds, and we consider the
next event. If the $(k+1)$-st event is a set event, then a set $S$ goes
neutral. A set going neutral does not affect its kernel, so as previously, the
claim still holds for $S$; other sets are also unaffected so the claim holds
for them.

If the $(k+1)$-st event is an edge event, then an edge $e$ between sets
$S_{1}$ and $S_{2}$ goes tight and the two sets merge to form a new active set
$S$. First of all, this event does not affect the kernel of $S_{1}$, $S_{2}$,
or of any other set besides $S$, so the claim still holds for all of them.
Since at least one of the merging sets is active, we can suppose without loss
of generality that $S_{1}$ is active. Then, if $S_{2}$ is inactive, the kernel
of $S$ would be the kernel of $S_{1}$. For a neutral set $N\subset K(S)$,
$|\delta_{K(S)}(N)|=1$ for some $N$ would imply that
$|\delta_{K(S_{1})}(N)|=1$, which contradicts that the claim holds previously.

If $S_{2}$ is active, then the kernel of $S$ would be the kernel of $S_{1}$
and $S_{2}$, plus some neutral sets on the path between the two kernels. If
$N\subset K(S)$, then either $N$ is on the path between $K(S_{1})$ and
$K(S_{2})$ or $N$ is a subset of $K(S_{1})$ or $K(S_{2})$. But every neutral
set $N$ on the path has $|\delta_{K(S)}(N)|=2$, and by the inductive
hypothesis, no neutral subset $N$ of $K(S_{1})$ or $K(S_{2})$ can have
$|\delta_{K(S_{i})}(N)|=1$, $i=1,2$.

∎

Again, we utilize a result by Paul et al. (Lemma 4 in [14]).

######  Lemma 5.

$\displaystyle\sum_{e\in T_{0}}\sum_{S:e\in\delta(S)}y_{S}\leq
2\sum_{\begin{subarray}{c}U:U\cap S_{T_{0}}\neq\emptyset\\\ v\not\in
U\end{subarray}}y_{U}.$

###### Proof.

We will prove the inequality for any arbitrary iteration in the primal-dual
algorithm. Consider an iteration in which we let $\mathcal{C}$ be the current
set of components $C$ such that $|\delta(C)\cap T_{0}|\geq 1$. We can
partition $\mathcal{C}$ into active components $\mathcal{C}_{A}$ and inactive
components $\mathcal{C}_{I}$. Let $v$ be the final vertex picked and $C_{v}$
be the unique set in ${\cal C}$ containing $v$.

We claim that if $C_{v}\in{\cal C}_{A}$, then $\sum_{C\in{\cal
C}_{A}}|\delta(C)\cap T_{0}|\leq 2|{\cal C}_{A}|-2$, otherwise if
$C_{v}\in{\cal C}_{I}$, then $\sum_{C\in{\cal C}_{A}}|\delta(C)\cap T_{0}|\leq
2|{\cal C}_{A}|-1$. Suppose for now that the claim is true. We now prove the
inequality in Lemma 4 by induction on the algorithm. At the start of the
algorithm, with $y_{S}=0$ for all $S$, both sides of the inequality are equal
to $0$. At each iteration, let $\epsilon$ be the amount that we raise $y_{C}$
for each active component $C\in\mathcal{C}_{A}$. The LHS of the inequality
increases by $\sum_{C\in\mathcal{C}_{A}}|\delta(C)\cap T_{0}|\epsilon$, while
the RHS of the inequality increases by either $2|{\cal C}_{A}|\epsilon$ (if
$C_{v}\in{\cal C}_{I}$) or $2(|{\cal C}_{A}|-1)\epsilon=(2|{\cal
C}_{A}|-2)\epsilon$ (if $C_{v}\in{\cal C}_{A}$). Then given the claim, the
inequality continues to hold inductively. Thus the lemma statement will hold
at the end of the algorithm.

To prove the claim, first suppose that $C_{v}$ is inactive. By Lemma 1, all
other neutral subsets of $S_{T_{0}}$ have degree at least $2$. Since $v$ is
the last vertex added, $C_{v}$ is the only inactive component such that
possibly $|\delta(C_{v})\cap T_{0}|=1$. Thus we have

$\sum_{C\in\mathcal{C}_{I}}|\delta(C)\cap T_{0}|\geq 2|\mathcal{C}_{I}|-1.$

Note that edges of $T_{0}$ link components in $\mathcal{C}$ to form a tree, so

$\sum_{C\in\mathcal{C}_{A}}|\delta(C)\cap
T_{0}|+\sum_{C\in\mathcal{C}_{I}}|\delta(C)\cap T_{0}|\leq
2|\mathcal{C}_{A}|+2|\mathcal{C}_{I}|-2.$

Then the last two inequalities imply

$\sum_{C\in\mathcal{C}_{A}}|\delta(C)\cap T_{0}|\leq 2|\mathcal{C}_{A}|-1,$

and the claim holds for this case.

Now consider the case where $C_{v}\in\mathcal{C}_{A}$. By a similar logic,
there is no component $C\in\mathcal{C}_{I}$ such that $|\delta(C)\cap
T_{0}|=1$, and therefore

$\sum_{C\in\mathcal{C}_{I}}|\delta(C)\cap T_{0}|\geq 2|\mathcal{C}_{I}|,\text{
implying}$ $\sum_{C\in\mathcal{C}_{A}}|\delta(C)\cap T_{0}|\leq
2|\mathcal{C}_{A}|-2,$

and the claim holds for this case, so the proof of the lemma is complete. ∎

The result of Lemma 5 allows us to prove the following upper bound on the cost
of our tree.

######  Theorem 2.

The picked tree has cost at most $2(\lambda_{1}\cdot k-\pi(S_{2}))$, where
$S_{2}$ is the maximal potential set that contains the picked tree.

###### Proof.

By the pick procedure, vertices in $S_{2}-S_{T_{0}}$ are either (i) in a
pruned neutral subset $N^{\prime}_{i}$ or (ii) in the subset $N_{p}$ where we
started our pick procedure. Thus, we have $S_{2}=\bigcup
N^{\prime}_{i}\cup(N_{p}-S_{T_{0}})\cup S_{T_{0}}$. Since $N^{\prime}_{i}$ are
neutral, we have

$\displaystyle\lambda_{1}|\cup N^{\prime}_{i}|=\sum_{U:U\subseteq\cup
N^{\prime}_{i}}y_{U}.$

$N_{p}$ is also neutral, and we can partition its subsets into two types: ones
that contain vertices in $N_{p}-S_{T_{0}}$ and ones that do not. Then we have

$\lambda_{1}|N_{p}|=\sum_{\begin{subarray}{c}U:U\subset N_{p}\\\
U\cap(N_{p}-S_{T_{0}})\neq\emptyset\end{subarray}}y_{U}+\sum_{U:U\subseteq
N_{p}\cap S_{T_{0}}}y_{U}\leq\sum_{\begin{subarray}{c}U:U\subseteq N_{p}\\\
U\cap(N_{p}-S_{T_{0}})\neq\emptyset\end{subarray}}y_{U}+\lambda_{1}|N_{p}\cap
S_{T_{0}}|$

by Lemma 1 which implies

$\lambda_{1}|N_{p}-S_{T_{0}}|\leq\sum_{\begin{subarray}{c}U:U\subseteq
N_{p}\\\ U\cap(N_{p}-S_{T_{0}})\neq\emptyset\end{subarray}}y_{U}.$

Combining with Lemma 5, this gives us

$\displaystyle\lambda_{1}|S_{2}|$ $\displaystyle=\sum_{U:U\subset
S_{2}}y_{U}+\pi(S_{2})$ $\displaystyle\geq\sum_{\begin{subarray}{c}U:U\cap
S_{T_{0}}\neq\emptyset\\\ v\not\in
U\end{subarray}}y_{U}+\sum_{\begin{subarray}{c}U:U\subset N_{p}\\\
U\cap(N_{p}-S_{T_{0}})\neq\emptyset\end{subarray}}y_{U}+\sum_{U:U\subseteq\cup
N^{\prime}_{i}}y_{U}+\pi(S_{2})$ $\displaystyle\geq\frac{1}{2}\sum_{e\in
T_{0}}\sum_{S:e\in\delta(S)}y_{S}+\lambda_{1}|N_{p}-S_{0}|+\lambda_{1}|\bigcup
N^{\prime}_{i}|+\pi(S_{2}).$

Rearranging gives $\lambda_{1}|S_{T_{0}}|\geq\frac{1}{2}\sum_{e\in
T_{0}}c_{e}+\pi(S_{2}).$ ∎

Combining our lower bound from Theorem 1 with the upper bound in Theorem 2, we
achieve the 2-approximation.

######  Theorem 3.

The tree returned by the picked routine has at most twice the cost of the
optimal spanning tree of $k$ vertices, that is

$\sum_{e\in T_{0}}c_{e}\leq 2\sum_{e\in T^{*}}c_{e}.$

###### Proof.

Recall from Theorem 1 we have that

$\sum_{e\in T^{*}}c_{e}\geq\lambda_{1}\cdot k-\pi(S_{1}),$

where $S_{1}$ is the set with minimal potential in $\mathcal{S}$ that contains
$S_{T^{*}}$. Since we include the set of all vertices $V(G)$ in $\mathcal{S}$,
the fact that both $S_{T^{*}}$ and $S_{T_{0}}$ are subsets of $V(G)$ implies
that $\pi(S_{2})\geq\pi(V(G))$ and $\pi(S_{1})\leq\pi(V(G))$. Thus we have

$\displaystyle\sum_{e\in T_{0}}c_{e}$ $\displaystyle\leq 2(\lambda_{1}\cdot
k-\pi(S_{2}))$ by Theorem 2 $\displaystyle\leq 2(\lambda_{1}\cdot
k-\pi(S_{1}))$ $\displaystyle\leq 2\sum_{e\in T^{*}}c_{e}.$

∎

## Acknowledgments

The second, third, and fourth authors were partially supported by the National
Science Foundation [NSF CCF-2007009].

## References

  * [1] S. Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, in Journal of the ACM, 45 (1998), pp. 753–782.
  * [2] S. Arora and G. Karakostas, A $2+\epsilon$ approximation algorithm for the $k$-MST problem, in Mathematical Programming Series A, 107 (2006), pp. 491–504.
  * [3] S. Arya and H. Ramesh, A 2.5-factor approximation algorithm for the k-MST problem, Information Processing Letters, 65.3 (1998), pp. 117–118.
  * [4] B. Awerbuch, Y. Azar, A. Blum, and S. Vempala, Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen, in Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995, pp. 277–283.
  * [5] A. Blum, P. Chalasani, and S. Vempala, A constant-factor approximation for the k-MST problem in the plane, in Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995, pp. 294–302.
  * [6] A. Blum, R. Ravi, and S. Vempala, A constant-factor approximation algorithm for the k MST problem (Extended Abstract), in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 1996, pp. 442–448.
  * [7] D. Eppstein, Faster geometric K-point MST approximation, in Comput. Geom., 8 (1997), pp. 231–240.
  * [8] N. Garg, A 3-approximation for the minimum tree spanning k vertices, in Proceedings of 37th Conference on Foundations of Computer Science, 1996, pp. 302–309.
  * [9] N. Garg, Saving an epsilon: a 2-approximation for the k-MST problem in graphs, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 396–402.
  * [10] N. Garg and D. S. Hochbaum, An $O(\log k)$ approximation algorithm for the $k$ minimum spanning tree problem in the plane, in Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994, pp. 432–438.
  * [11] D. S. Johnson, M. Minkoff, and S. Phillips, The prize collecting Steiner tree problem: theory and practice, in Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, pp. 760–769.
  * [12] J. S. B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, $k$-MST, and related problems, in SIAM Journal on Computing, 28 (1999), pp. 1298–1309.
  * [13] J. S. B. Mitchell, A. Blum, P. Chalasani, and S. Vempala, A constant-factor approximation algorithm for the geometric k-MST problem in the plane, SIAM Journal on Computing, 28.3 (1998), pp. 771–781.
  * [14] A. Paul, D. Freund, A. Ferber, D. B. Shmoys, and D. P. Williamson, Budgeted prize-collecting traveling salesman and minimum spanning tree problems, Mathematics of Operations Research, 45 (2020), pp. 576–590.
  * [15] R. Ravi, R. Sundaram, M. V. Marathe, D. J. Rosenkrantz, and S. S. Ravi, Spanning trees short or small, in SIAM Journal on Discrete Mathematics, 9 (1996), pp. 178–200.