论文标题
带对数追索性预算的重新着色单元间隔图
Recoloring Unit Interval Graphs with Logarithmic Recourse Budget
论文作者
论文摘要
在本文中，我们研究了为动态变化的单位间隔图着色的问题。在我们的模型中，当时添加或删除了单位间隔，并且必须立即进行颜色，以便没有两个重叠的间隔共享相同的颜色。每次更新之后，仅允许重新上色数量有限的间隔。每次更新的重新加工数量的限制称为“追索预算”。在本文中，我们表明，如果该图始终保持$ k $可颜色，并且更新仅由插入组成，那么我们可以实现$ o（k^7 \ log n）$的摊销追索性预算，同时保持$ k $颜色的适当着色。这是对[Bosek等人的结果的指数改进，Repolourse预算有限。 SWAT 2020]就$ k $和$ n $而言。我们通过在完全动态的环境中显示摊销的追索性预算中的$ω（n）$的下限来补充这一结果。我们的增量算法可以有效地实现。 作为独立利益的副产品，我们为适当的圆弧图着色时包括一个新的结果。令$ l $为一组单位圆弧$ \ Mathcal {a} $的一组弧相交的弧的最大数量。我们表明，如果有一个$ \ MATHCAL {a}'的非相互作用单位弧的大小$ l^2-1 $，以至于$ \ Mathcal {a} \ cup \ cup \ mathcal {a} $不包含$ l+1 $ a+1 $ arc的颜色，那么它可能会与$ \ nmath $ \ $ \ $ \ $ \ \ $ \ \ $ \ a} $ {a。这补充了单元圆形弧色上的工作，该作品指定了$ \ Mathcal {a} $带有$ L+1 $ $或更多颜色所需的足够条件。
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 is 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, and the updates consist of insertions only, then we can achieve the amortized recourse budget of $O(k^7 \log n)$ while maintaining a proper coloring with $k$ colors. This is an exponential improvement over the result in [Bosek et al., Recoloring Interval Graphs with Limited Recourse Budget. SWAT 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 a byproduct of independent interest we include a new result on coloring proper circular arc graphs. Let $L$ be the maximum number of arcs intersecting in one point for some set of unit circular arcs $\mathcal{A}$. We show that if there is a set $\mathcal{A}'$ of non-intersecting unit arcs of size $L^2-1$ such that $\mathcal{A} \cup \mathcal{A}'$ does not contain $L+1$ arcs intersecting in one point, then it is possible to color $\mathcal{A}$ with $L$ colors. This complements the work on unit circular arc coloring, which specifies sufficient conditions needed to color $\mathcal{A}$ with $L+1$ colors or more.
