Online and Incremental Fractional Vertex Cover on Trees

Prelegent(ci)

Paweł Putra

Język referatu

angielski

Termin

29 maja 2026 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori and the edges arrive one at a time. The goal is to maintain a fractional vertex cover of the tree, i.e., an assignment of fractional weights from [0, 1] to the vertices such that the weights of endpoints of every edge sum up to at least one. After each edge arrival, we need to modify the fractional vertex cover to cover the new edge as well. However, we can only increase the values assigned to vertices. The problem was studied before (in the vertex arrival model) by Wang and Wong, who motivated it as a generalization of the ski-rental problem, but also (more importantly) by its close connection to the dual online matching problem. They presented a 1.901-competitive algorithm for general graphs in the vertex arrival model. We present an 11/6 ≈ 1.83-competitive algorithm for trees in the more general edge arrival model.
In addition, we study the fractional vertex cover problem in an incremental model, where we again seek a fractional vertex cover after every update, but all the updates to the tree are known to the algorithm a priori. In this model, we give a 1.5-competitive algorithm and provide a matching lower bound.

This is joint work Anna Zych-Pawlewicz, Grzegorz Gutowski, Bartłomiej Bosek, Julia Baligács, Yann Disser, Andreas Feldmann, Katarzyna Kępińska.

---