Dudek, Bartłomiej ;
Gawrychowski, Paweł
Counting 4Patterns in Permutations Is Equivalent to Counting 4Cycles in Graphs
Abstract
Permutation σ appears in permutation π if there exists a subsequence of π that is orderisomorphic to σ. The natural algorithmic question is to check if σ appears in π, and if so count the number of occurrences. Only since very recently we know that for any fixed length k, we can check if a given pattern of length k appears in a permutation of length n in time linear in n, but being able to count all such occurrences in f(k)⋅ n^o(k/log k) time would refute the exponential time hypothesis (ETH). Together with practical applications in statistics, this motivates a systematic study of the complexity of counting occurrences for different patterns of fixed small length k. We investigate this question for k = 4. Very recently, EvenZohar and Leng [arXiv 2019] identified two types of 4patterns. For the first type they designed an 𝒪̃(n) time algorithm, while for the second they were able to provide an 𝒪̃(n^1.5) time algorithm. This brings up the question whether the permutations of the second type are inherently harder than the first type.
We establish a connection between counting 4patterns of the second type and counting 4cycles (not necessarily induced) in a sparse undirected graph. By designing twoway reductions we show that the complexities of both problems are the same, up to polylogarithmic factors. This allows us to leverage the work done on the latter to provide a reasonable argument for why there is a difference in the complexities for counting 4patterns of the first and the second type. In particular, even for the seemingly simpler problem of detecting a 4cycle in a graph on m edges, the best known algorithm works in 𝒪(m^{4/3}) time. Our reductions imply that an 𝒪(n^{4/3ε}) time algorithm for counting occurrences of any 4pattern of the second type in a permutation of length n would imply an exciting breakthrough for counting (and hence also detecting) 4cycles. In the other direction, by plugging in the fastest known algorithm for counting 4cycles, we obtain an algorithm for counting occurrences of any 4pattern of the second type in 𝒪(n^1.48) time.
BibTeX  Entry
@InProceedings{dudek_et_al:LIPIcs:2020:13367,
author = {Bart{\l}omiej Dudek and Pawe{\l} Gawrychowski},
title = {{Counting 4Patterns in Permutations Is Equivalent to Counting 4Cycles in Graphs}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {23:123:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13367},
URN = {urn:nbn:de:0030drops133678},
doi = {10.4230/LIPIcs.ISAAC.2020.23},
annote = {Keywords: Permutations, pattern avoidance, counting cycles}
}
04.12.2020
Keywords: 

Permutations, pattern avoidance, counting cycles 
Seminar: 

31st International Symposium on Algorithms and Computation (ISAAC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 