2026-08-25T18:47:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27294 2026-08-25T13:18:21Z ddc:004 open_access

Online and Incremental Fractional Vertex Cover on Trees Baligács, Júlia Bosek, Bartłomiej Disser, Yann Feldmann, Andreas Emil Gutowski, Grzegorz Kępińska, Katarzyna Putra, Paweł Zych-Pawlewicz, Anna fractional vertex cover online algorithms incremental algorithms edge arrival model trees competitive analysis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Júlia Baligács and Bartłomiej Bosek and Yann Disser and Andreas Emil Feldmann and Grzegorz Gutowski and Katarzyna Kępińska and Paweł Putra and Anna Zych-Pawlewicz 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.158 urn:nbn:de:0030-drops-272943 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.158 eng https://creativecommons.org/licenses/by/4.0/legalcode