论文标题
修补部分解决方案，几乎没有更改
Mending Partial Solutions with Few Changes
论文作者
论文摘要
在本文中，我们研究了修补的概念，即给出了图形问题的部分解决方案，我们研究了将其变成适当的解决方案需要多少精力。例如，如果我们具有部分颜色的图形，那么将其变成适当的颜色有多困难？ 在先前的工作（Sirocco 2022）中，从修补半径的角度进行了形式化并研究了这个问题：如果我们需要修补一个孔，我们需要多远修改解决方案？在这项工作中，我们研究了修补量的互补概念：需要修改多少个节点以修补一个孔？ We focus on the case of locally checkable labeling problems (LCLs) in trees, and show that already in this setting there are two infinite hierarchies of problems: for infinitely many values $0 < α\le 1$, there is an LCL problem with mending volume $Θ(n^α)$, and for infinitely many values $k \ge 1$, there is an LCL problem with mending volume $Θ(\log^k n)$.因此，树木上LCL问题的修复性是一个比仅基于修补半径的预期要高得多的问题。 We define three variants of the theme: (1) existential mending volume, i.e., how many nodes need to be modified, (2) expected mending volume, i.e., how many nodes we need to explore to find a patch if we use randomness, and (3) deterministic mending volume, i.e., how many nodes we need to explore if we use a deterministic algorithm.我们表明，这三个概念彼此不同，我们分析了相应模型的LCL问题复杂性的景观。
In this paper, we study the notion of mending, i.e. given a partial solution to a graph problem, we investigate how much effort is needed to turn it into a proper solution. For example, if we have a partial coloring of a graph, how hard is it to turn it into a proper coloring? In prior work (SIROCCO 2022), this question was formalized and studied from the perspective of mending radius: if there is a hole that we need to patch, how far do we need to modify the solution? In this work, we investigate a complementary notion of mending volume: how many nodes need to be modified to patch a hole? We focus on the case of locally checkable labeling problems (LCLs) in trees, and show that already in this setting there are two infinite hierarchies of problems: for infinitely many values $0 < α\le 1$, there is an LCL problem with mending volume $Θ(n^α)$, and for infinitely many values $k \ge 1$, there is an LCL problem with mending volume $Θ(\log^k n)$. Hence the mendability of LCL problems on trees is a much more fine-grained question than what one would expect based on the mending radius alone. We define three variants of the theme: (1) existential mending volume, i.e., how many nodes need to be modified, (2) expected mending volume, i.e., how many nodes we need to explore to find a patch if we use randomness, and (3) deterministic mending volume, i.e., how many nodes we need to explore if we use a deterministic algorithm. We show that all three notions are distinct from each other, and we analyze the landscape of the complexities of LCL problems for the respective models.
