English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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 edge-disjoint cycles plus at most 2n edges. Chu et al. improved the running time considerably to m1+o(1), while increasing both the length of the cycles and the number of omitted edges by a factor of no(1). Even more recently, Liu-Sachdeva-Yu [SODA’19] showed that for every constant δ ∈ (0, 1] there is an O(m · nδ)-time algorithm that provides, w.h.p., cycles of length O(log n)1/δ and O(n) extra edges. In this paper, we improve upon these bounds. We first show an m1+o(1)-time deterministic algorithm for computing nearly optimal cycle decomposition, i.e., with cycle length O(log2 n) and an extra subset of O(n log n) edges not in any cycle. This algorithm is based on a reduction to low-congestion cycle covers, introduced by the authors in [SODA’19]. We also provide a simple deterministic algorithm that runs in nearly linear time of Õ(m), and computes edge-disjoint cycles of length O(log n) and a leftover of n1+o(1) edges. For dense graphs with n1+δ edges for some constant δ ∈ (0, 1], we provide a nearly optimal decomposition in nearly linear time. These decomposition algorithms lead to improvements in all the algorithmic applications of Chu et al. as well as to new distributed constructions. ∗Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel. Emails: {merav.parter,eylon.yogev}@weizmann.ac.il. †Supported in part by grants from the Israel Science Foundation grant no. 950/16.

Optimal Short Cycle Decomposition in Almost Linear Time.