Technical Report MSC-2021-09

Title: Batched Vertex Cover Reconfiguration
Authors: Shahar Romem Peled
Supervisors: Keren Censor-Hillel
PDFCurrently accessibly only within the Technion network
Abstract: Reconfiguration schedules, i.e., sequences that gradually transform one solution of a problem to another while always maintaining feasibility, have been extensively studied. Most research has dealt with the decision problem of whether a reconfiguration schedule exists, and the complexity of finding one. A prime example is the reconfiguration of vertex covers (sets of vertices that touches all edges in a graph). We initiate the study of \emph{batched vertex cover reconfiguration}, which allows to reconfigure multiple vertices concurrently while requiring that any adversarial reconfiguration order within a \emph{batch} maintains feasibility. The latter provides robustness, e.g., if the simultaneous reconfiguration of a batch cannot be guaranteed. The quality of a schedule is measured by the number of batches until all nodes are reconfigured, and its \emph{cost}, i.e., the maximum size of an intermediate vertex cover.

First, we design a black-box compression scheme that for any graph, takes any well-behaved sequential (= non-batched) vertex cover reconfiguration schedule and compresses it into a short batch schedule, while only incurring a $1+\varepsilon$ multiplicative increase in the cost when using $O(1/\varepsilon)$ batches; we show that this is optimal. Second, we show that a similar transformation scheme can be efficiently run in a distributed setting, where computation is done at the vertices. The distributed result is based on the new concept of a \emph{small separator decomposition} that could be of independent interest.

In addition, we show that this approach is optimal, in the sense that if a small separator decomposition does not yield a good schedule, no method will.

Both results apply to various graph classes such as chordal graphs and cacti, and provide efficient approximation schemes that have polynomial run-time in the centralized setting and take $O(\log^* n/\eps)$ rounds in the distributed setting.

Lastly, we propose greedy-style sequential and batch reconfiguration schedules and study their performance for graphs of bounded arboricity. as well as their distributed implementation.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2021
To the main CS technical reports page

Computer science department, Technion