Parter, Merav ;
Yogev, Eylon
Optimal Short Cycle Decomposition in Almost Linear Time
Abstract
Short cycle decomposition is an edge partitioning of an unweighted graph into edgedisjoint short cycles, plus a small number of extra edges not in any cycle. This notion was introduced by Chu et al. [FOCS'18] as a fundamental tool for graph sparsification and sketching. Clearly, it is most desirable to have a fast algorithm for partitioning the edges into as short as possible cycles, while omitting few edges.
The most naïve procedure for such decomposition runs in time O(m * n) and partitions the edges into O(log n)length edgedisjoint cycles plus at most 2n edges. Chu et al. improved the running time considerably to m^{1+o(1)}, while increasing both the length of the cycles and the number of omitted edges by a factor of n^{o(1)}. Even more recently, LiuSachdevaYu [SODA'19] showed that for every constant delta in (0,1] there is an O(m * n^{delta})time algorithm that provides, w.h.p., cycles of length O(log n)^{1/delta} and O(n) extra edges.
In this paper, we significantly improve upon these bounds. We first show an m^{1+o(1)}time deterministic algorithm for computing nearly optimal cycle decomposition, i.e., with cycle length O(log^2 n) and an extra subset of O(n log n) edges not in any cycle. This algorithm is based on a reduction to lowcongestion cycle covers, introduced by the authors in [SODA'19].
We also provide a simple deterministic algorithm that computes edgedisjoint cycles of length 2^{1/epsilon} with n^{1+epsilon}* 2^{1/epsilon} extra edges, for every epsilon in (0,1]. Combining this with LiuSachdevaYu [SODA'19] gives a linear time randomized algorithm for computing cycles of length poly(log n) and O(n) extra edges, for every nvertex graphs with n^{1+1/delta} edges for some constant delta.
These decomposition algorithms lead to improvements in all the algorithmic applications of Chu et al. as well as to new distributed constructions.
BibTeX  Entry
@InProceedings{parter_et_al:LIPIcs:2019:10665,
author = {Merav Parter and Eylon Yogev},
title = {{Optimal Short Cycle Decomposition in Almost Linear Time}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {89:189:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10665},
URN = {urn:nbn:de:0030drops106653},
doi = {10.4230/LIPIcs.ICALP.2019.89},
annote = {Keywords: Cycle decomposition, lowcongestion cycle cover, graph sparsification}
}
04.07.2019
Keywords: 

Cycle decomposition, lowcongestion cycle cover, graph sparsification 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 