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.

We consider a graph coloring algorithm that processes vertices in order taken uniformly at random and assigns colors to them using First-Fit strategy. We show that this algorithm uses, in expectation, at most (1+o(1))⋅ln n / ln ln n different colors to color any forest with n vertices. We also construct a family of forests that shows that this bound is best possible.

In this paper we study the problem of coloring a unit interval graph which changes dynamically. In our model the unit intervals are added or removed one at the time, and have to be colored immediately, so that no two overlapping intervals share the same color. After each update only a limited number of intervals are allowed to be recolored. The limit on the number of recolorings per update is called the recourse budget. In this paper we show, that if the graph remains k-colorable at all times, the updates consist of insertions only, and the final instance consists of n intervals, then we can achieve an amortized recourse budget of 𝒪({k⁷ log n}) while maintaining a proper coloring with k colors. This is an exponential improvement over the result in [Bartłomiej Bosek et al., 2020] in terms of both k and n. We complement this result by showing the lower bound of Ω(n) on the amortized recourse budget in the fully dynamic setting. Our incremental algorithm can be efficiently implemented. As an additional application of our techniques we include a new combinatorial result on coloring unit circular arc graphs. Let L be the maximum number of arcs intersecting in one point for some set of unit circular arcs 𝒜. We show that if there is a set 𝒜' of non-intersecting unit arcs of size L²-1 such that 𝒜 ∪ 𝒜' does not contain L+1 arcs intersecting in one point, then it is possible to color 𝒜 with L colors. This complements the work on circular arc coloring [Belkale and Chandran, 2009; Tucker, 1975; Valencia-Pabon, 2003], which specifies sufficient conditions needed to color 𝒜 with L+1 colors or more.

The shortest augmenting path (Sap) algorithm is one of the most classical approaches to the maximum matching and maximum flow problems, e.g., using it Edmonds and Karp (J. ACM 19(2), 248–264 1972) have shown the first strongly polynomial time algorithm for the maximum flow problem. Quite astonishingly, although it has been studied for many years already, this approach is far from being fully understood. This is exemplified by the online bipartite matching problem. In this problem a bipartite graph G = (W ⊎ B, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. After arrival of this vertex we augment the current matching by using shortest augmenting path. It was conjectured by Chaudhuri et al. (INFOCOM’09) that the total length of all augmenting paths found by Sap is $\mathcal {O}(n \log n)$ . However, no better bound than $\mathcal {O}(n^{2})$ is known even for trees. In this paper we prove an $\mathcal {O}(n \log ^{2}n)$ upper bound for the total length of augmenting paths for trees.

This paper investigates the problem of maintaining maximum size matchings in incremental bipartite graphs. In this problem a bipartite graph G between n clients and n servers is revealed online. The clients arrive in an arbitrary order and request to be matched to a subset of servers. In our model we allow the clients to switch between servers and want to maximize the matching size between them, i.e., after a client arrives we find an augmenting path from a client to a free server. Our goals in this model are twofold. First, we want to minimize the number of times clients are reallocated between the servers. Second, we want to give fast algorithms that recompute such reallocation. As for the number of changes, we propose a greedy algorithm that chooses an augmenting path π that minimizes the maximum number of times each server in π was used by augmenting paths so far. We show that in this algorithm each server has its client reassigned O(√n) times. This gives an O(n3/2) bound on the total number of changes, what gives a progress towards the main open question risen by Chaudhuri et al. (INFOCOM'09) who asked to prove O(n log n) upper bound. Next, we argue that the same bound holds in the decremental case. Moreover, we show incremental and decremental algorithms that maintain (1 - ε)-approximate matching with total of O(ε-1n) reallocations, for any ε > 0. Finally, we address the question of how to efficiently compute paths given by this greedy algorithm. We show that by introducing proper amortization we can obtain an incremental algorithm that maintains the maximum size matching in total O(√nm) time. This matches the running time of one of the fastest static maximum matching algorithms that was given by Hopcroft and Karp (SIAM J. Comput '73). We extend our result to decremental case where we give the same total bound on the running time. Additionally, we show O(ε-1m) time incremental and decremental algorithms that maintain (1 - ε)-approximate matching for any ε > 0. Observe that this bound matches the running time of the fastest approximate static solution as well.

One of the simplest heuristics for obtaining a proper coloring of a graph is the first-fit algorithm. First-fit visits each vertex of the graph in the specified order and assigns to every point the least possible number. Let $\mathcal{G}$ be a class of incomparability graphs with bounded maximum clique size, closed under taking induced subgraphs. We prove that first-fit uses a bounded number of colors on the graphs in $\mathcal{G}$ iff there is an incomparability graph of clique size $2$ not contained in $\mathcal{G}$.

The main question in the on-line chain partitioning problem is to determine whether there exists an algorithm that partitions on-line posets of width at most w into polynomial number of chains see Trotter's chapter Partially ordered sets in the Handbook of Combinatorics. So far the best known on-line algorithm of Kierstead used at most (5ω- 1)/4 chains; on the other hand Szemeredi proved that any on-line algorithm requires at least (ω+1/2) chains. These results were obtained in the early eighties and since then no progress in the general case has been done. We provide an on-line algorithm that partitions orders of width ω into at most ω16 log ωchains. This yields the first subexponential upper bound for on-line chain partitioning problem.

We consider a problem of partitioning a partially ordered set into chains by first-fit algorithm. In general this algorithm uses arbitrarily many chains on a class of bounded width posets. In this paper we prove that First-Fit uses at most $3tw^2$ chains to partition any poset of width w which does not induce two incomparable chains of height t. In this way we get a wide class of posets with polynomial bound for the on-line chain partitioning problem. We also discuss some consequences of our result for coloring graphs by First-Fit.