Finding and counting permutations via CSPs

Benjamin Aram Berendsohn; D\'aniel Marx; L\'aszl\'o Kozma

REVIEW 1 major objections 4 minor 14 references

Finding and counting permutations via CSPs

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Permutation pattern matching can be solved in time n^{k/4+o(k)}, and counting occurrences is almost optimally hard under the exponential-time hypothesis.

desk verdict CSP reformulation and even-odd algorithm are solid, but the main n^{k/4} bound rests on an unproved treewidth reduction that a referee must push on. read the letter →

arxiv 1908.04673 v1 pith:RC2MBFV3 submitted 2019-08-13 cs.DS math.CO

Benjamin Aram Berendsohn , László Kozma , Dániel Marx This is my paper · ORCID

classification cs.DSmath.CO MSC 05A0505C8568Q25

keywords permutationpatternmatchingconstraintsatisfactiontreewidthincidencegraphcountingexponential-timehypothesisparameterizedcomplexity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Permutation pattern matching asks whether a length-k order pattern appears inside a length-n text permutation; the problem is NP-complete in general. The paper establishes new worst-case running times: $n^{{k/4+o(k)}}$ in general, and, with polynomial space, either O(1.6181^n) or O($n^{{k/2+1}}$). The key move is to view the problem as a binary constraint-satisfaction problem whose constraint graph is the pattern's incidence graph, so known treewidth algorithms apply; a strip-guessing trick then lowers the exponent. The same algorithms count occurrences, and the paper shows under the exponential-time hypothesis that near-optimal counting is impossible in time f(k) $n^{{o(k/log k)}}$. If correct, these are the fastest known algorithms for pattern length k in Ω(log n).

What carries the argument

The central object is the incidence graph of a permutation: the graph whose vertices are the points (i, π(i)) and whose edges connect each point to its immediate predecessor and successor by index and by value. It is exactly the union of two Hamiltonian paths, so it has maximum degree 4 and treewidth at most k/3+o(k). The reduction from PPM to a binary CSP makes this graph the constraint graph; a known CPS result then solves any such CSP in time O($n^{{t+1}}$) for treewidth t. The strip-guessing trick of [23]—guessing which of $n^{{1/4}}$ vertical strips contains each 'leftmost' pattern entry—cuts both domain size and remaining graph treewidth, driving the exponent to k/4. The even-odd method is the second machinery: guessing all even-index entries removes all horizontal constraints, leaving only vertical constraints, which form a union of paths of treewidth 1.

What would settle it

Compute the exact treewidth of the reduced constraint graph, after strip guessing and removal of crossing constraints, for all length-k permutations up to k≈15: if any family exceeds (k−|X|)/3+o(k), the $n^{{k/4+o(k)}}$ bound fails; separately, any counting algorithm running in f(k)$n^{{o(k/log k)}}$ would falsify the ETH lower bound.

Watch

Extended reading notes

Core claim

The paper's central claim is that the combinatorial structure of a permutation pattern—specifically the treewidth of its incidence graph—determines how fast the pattern can be found or counted. Formulating PPM as a CSP reduces the problem to solving binary constraints over a domain of n values on a graph of treewidth at most k/3+o(k), immediately beating previous $n^{{0.47k+o(k)}}$. Guessing, for a subset X of pattern entries, which vertical strip of the text they map to shrinks the domain to $n^{{3/4}}$ and the relevant treewidth to (k−|X|)/3+o(k), yielding $n^{{k/4+o(k)}}$. For the polynomial-space algorithm, guessing all even-index pattern entries leaves a constraint graph that is a union of paths, so each guess is verified in linear time; counting the valid guesses gives O(1.6181^n). The counting lower bound follows from reducing partitioned subgraph isomorphism to partitioned PPM and then using inclusion-exclusion to reduce partitioned counting to ordinary counting.

Load-bearing premise

The main speedup assumes that guessing the position of the leftmost pattern entry in each of several vertical bands makes the network of remaining constraints sparse enough that its complexity is at most one third of the remaining pattern size; if that sparsity fails for some family of patterns, the exponent k/4 is not reached.

Editorial extensions

If this is right

The n^{k/4+o(k)} running time applies to deciding PPM and, by a direct modification, to counting occurrences.
The polynomial-space algorithm runs in either O(1.6181^n) or O(n^{k/2+1}), whichever is better for the instance.
Assuming ETH, no algorithm can count occurrences of a pattern in time f(k) n^{o(k/log k)} for any function f.
For 2-monotone and Jordan patterns, PPM is solvable in n^{O(√k)} time via planar-treewidth bounds.
There exist 3-increasing and 3-decreasing patterns whose incidence graphs have treewidth Ω(k/log k), so sub-exponential time is unlikely even for these restricted classes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the polynomial-space even-odd algorithm is extremely simple, it may be practical for moderate n even where the theoretical bounds are not tight; a prototype could test whether the greedy lowest-point choice rarely backtracks on real instances.
The strip-guessing trick is a general template: any CSP whose constraint graph has bounded degree and a treewidth bound can be accelerated by guessing strip memberships of a few variables; applying it to other permutation problems is a natural next step.
The treewidth dichotomy between 2-monotone (O(√k)) and 3-increasing (Ω(k/log k)) patterns suggests the computational boundary is not between 'structured' and 'unstructured' patterns but between incidence graphs that are planarizable and those that contain large grids.
The inclusion-exclusion step from partitioned counting to ordinary counting is likely reusable: any colored pattern-matching problem whose colored version is ETH-hard can be shown to have a hard counting version by the same 2^k oracle calls.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. First, the CSP reformulation is genuinely useful, and the even-odd polynomial-space algorithm (Theorem 2) is simple, self-contained, and, as far as I can tell, correct. Second, the headline result — n^{k/4+o(k)} — is not actually established by what's written. The proof of Theorem 1 hinges on a claim in Section 3: after guessing the set X of leftmost pattern entries per strip and deleting the |X|-1 horizontal constraints that cross strip boundaries, the remaining constraint graph has treewidth (k-|X|)/3 + o(k). The paper cites [28,23] for this, but does not derive it. It is not a consequence of Lemma 9, which bounds treewidth by k/3 for any order-k graph of max degree 4; deleting |X|-1 edges from such a graph does not automatically lower the bound by |X|/3. The stress-test note gives a concrete worry: if one can realize a cubic expander as a permutation incidence graph minus a matching of horizontal edges with strip blocks of size two, then the asserted bound would contradict tw(H) ≥ Ω(k). I have not verified that construction, but the missing proof is real, and the claim is load-bearing: without it Theorem 1 falls back to k/3.

That's the main soft spot, and it's serious. The rest of the paper is in good shape. The CSP lens unifies earlier algorithms in a way I haven't seen spelled out before, and the even-odd observation — that fixing the even-index entries leaves a graph of disjoint paths — is clean and produces a nice polynomial-space O(1.6181^n) bound. The counting versions follow from standard CSP counting, and the ETH lower bound for #PPM via PSI and inclusion-exclusion is well-constructed. The special-pattern results (O(√k) treewidth for 2-monotone and Jordan patterns, and the Ω(k/log k) lower bound for 3-increasing via minor embedding) are interesting; some small cases are deferred to the first author's thesis, which is a minor irritation rather than a defect. The citation pattern looks normal — earlier work by Marx and others is cited appropriately, and there's no fitting-to-target.

Who gets value? Permutation pattern people, parameterized complexity folks, and anyone using the CSP-to-treewidth pipeline. If the k/4 claim survives, it's an important improvement; if it doesn't, the paper still offers a clean algorithm, a useful framework, and a lower bound that's close to matching. I'd bring it to reading group, and I'd cite it for the even-odd method and the CSP formulation.

Recommendation: send to peer review. The Section 3 gap is exactly what a referee should push on — ask for a complete proof of the treewidth reduction, or state Theorem 1 with k/3. A serious editor shouldn't desk-reject this.

Referee Report

1 major / 4 minor

Summary. The paper studies Permutation Pattern Matching (PPM) and its counting version. It formulates PPM as a binary constraint-satisfaction problem whose constraint graph is the incidence graph of the pattern, and then uses treewidth-based CSP algorithms. The main claimed contributions are: (i) an n^{k/4+o(k)}-time algorithm for PPM, obtained by a vertical-strip guessing technique that is asserted to reduce the relevant treewidth from k/3 to (k-|X|)/3; (ii) a polynomial-space algorithm running in either O(1.6181^n) or O(n^{k/2+1}) via an even-odd method; (iii) counting versions of these algorithms; (iv) an ETH-based lower bound showing that no f(k) n^{o(k/log k)} counting algorithm exists; and (v) treewidth bounds for special pattern classes, including O(sqrt k) for 2-monotone and Jordan permutations and an Omega(k/log k) lower bound for 3-increasing permutations.

Significance. If the main n^{k/4} result were correct, it would be a genuine advance over the previous n^{0.47k+o(k)} and O(1.79^n) bounds and would demonstrate a clean unifying CSP view of existing algorithms. The even-odd method in Theorem 2 is simple, self-contained, and appears sound; the ETH lower bound for the counting problem (Theorem 4) is a substantial and interesting result; and the special-pattern treewidth results (Theorems 5 and 6) are elegant. These parts give the paper real value. However, the central algorithmic claim of the paper, Theorem 1, rests on an unsupported and in fact false treewidth-reduction assertion. Because that assertion is load-bearing for the headline n^{k/4} exponent, the main contribution is not established by the manuscript as written.

major comments (1)

[Section 3 (running-time derivation of Theorem 1)] The derivation of the n^{k/4+o(k)} bound hinges on the assertion that after deleting the |X|-1 horizontal constraints of the leftmost entries, the treewidth is at most (k-|X|)/3 + o(k), cited to [28,23]. This does not follow from Lemma 9: that lemma bounds the treewidth of any order-k maximum-degree-4 graph by k/3 + o(k), and deleting a matching of size |X|-1 leaves a maximum-degree-4 graph on k vertices, so Lemma 9 still gives only k/3 with no dependence on |X|. The displayed product n^{|X|/4} * n^{(3/4)(k/3 - |X|/3)} telescopes to n^{k/4} precisely because of the |X|/3 term; without it, the sum over all X subset of [k] does not yield n^{k/4}. Moreover, the asserted bound is false in the generality needed. Take a bounded-degree expander H that is the union of a Hamiltonian path P_y and a perfect matching N (e.g., a 3-regular expander with a Hamiltonian cycle, with one cycle edge deleted), and add a matching M so that N union M is a Hamiltonian path P_x. Then G = P_x union P_y is a permutation incidence graph by the characterization in Section 2. If the text strips are the blocks of size two along P_x, then X contains one vertex per block, |X| = k/2, the deleted L-edges are exactly M, and G - M = H has treewidth Omega(k), contradicting the claimed (k-|X|)/3 = k/6. Thus Theorem 1 and the first counting bound in Theorem 3 are not established by the given argument.

minor comments (4)

[Section 5 (definition of PSI)] The definition of Partitioned Subgraph Isomorphism states that {u,v} in E(H) if and only if {g(u),g(v)} in E(G), but the reduction in Appendix A.6 only enforces the forward implication: pattern points are placed only for edges of H, and no constraint forbids extra edges among the selected text vertices. This matches the standard non-induced PSI used in the cited hardness result [44, Corr. 6.3], so the lower bound is likely unaffected, but the 'if and only if' wording should be corrected to avoid a seeming gap.
[Section 2 (proof of Lemma 7)] In the backward direction of the proof of Lemma 7, the text says 'pi(i_{j'}) < pi(i_{j''})' where it should say 'pi(j') < pi(j'')'; the iterated application of the NU operator over j''-j' steps is also unclear and should be replaced by a walk along the value-Hamiltonian path.
[Section 4 (proof of Theorem 5(i))] The crossing argument for 2-monotone patterns is compressed: the claim that the only possible y-order is u.y < t.y < s.y < v.y under the WLOG assumption u.y < v.y uses implicitly the fact that s.y and t.y are consecutive values, so no other point can lie between them. Without that observation, the case analysis appears to have additional cases; please expand the proof.
[Section 4 (proof of Theorem 6)] The proof chooses 'a permutation whose incidence graph has treewidth Omega(n)' without a reference or a proof. This is standard (e.g., random permutations give expander-like incidence graphs with high probability), but it should be stated explicitly for completeness.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the new bounds follow from external treewidth/CSP theorems and ETH reductions, not from self-referential fits; the k/4 step is a potential gap but not circular.

full rationale

No significant circularity. The upper bounds in Theorems 1–3 are derived by reducing PPM to a binary CSP whose constraint graph is the pattern incidence graph Gπ (Lemma 7), applying the standard treewidth-based CSP algorithm (Lemma 8, [32,24]), and bounding treewidth via the external max-degree-4 pathwidth theorem (Lemma 9, [28,29]); the strip-guessing step is a direct combinatorial argument, and its running-time arithmetic is explicit. The exponential-time bound O(1.6181^n) follows from a binomial-coefficient estimate, not from any fitted quantity. The lower bound (Theorem 4) is built on the independent ETH-hardness of Partitioned Subgraph Isomorphism [44, Corr. 6.3] and a new PPPM-to-PPM reduction, neither of which presupposes the running-time target. The only questionable step is the unsupported assertion that deleting |X|-1 strip-crossing edges lowers the treewidth to (k-|X|)/3+o(k); that is a possible correctness gap in a cited graph-theoretic bound, not a circularity, because the assertion is not defined in terms of the claimed running time and no parameter is fitted to make the equation hold. Self-citations to [33,44] provide hardness baselines and algorithmic background, but the new upper bounds do not reduce to those citations.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central upper bounds rely on standard treewidth machinery and ETH. The paper introduces no new fitted constants or postulated entities. The main unstated assumption is the strip-based treewidth reduction in Section 3, which is cited rather than derived.

assumptions (6)

domain assumption ETH (exponential-time hypothesis)
Theorem 4's lower bound assumes no O(2^{o(n)}) algorithm for 3SAT; standard in parameterized complexity.
standard math Binary CSP solvable in O(|D|^{t+1}) with tree decomposition (Lemma 8)
Cited to Freuder and Dechter-Pearl; load-bearing for both upper bound algorithms.
standard math Max-degree-4 n-vertex graph has pathwidth at most n/3+o(n) (Lemma 9)
Cited to Fomin et al. and Fomin-Hoie; gives the baseline exponent that the strip trick reduces to k/4.
standard math Planar graphs have treewidth O(sqrt n)
Used for Theorem 5 on 2-monotone and Jordan patterns.
standard math C(n - ceil(k/2), floor(k/2)) = O(1.6181^n) maximum over k
Cited to Tanny-Zuker and OEIS; used for the refined exponential bound.
standard math Counting CSP solutions can be done in O(|D|^{t+1}) (Lemma 10)
Stated as implicit in counting literature; needed for Theorem 3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Finding and counting permutations via CSPs." pith.science (2026). https://pith.science/paper/RC2MBFV3

@misc{pith2026190804673,
  author       = {Pith},
  title        = {Pith review of: Finding and counting permutations via CSPs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RC2MBFV3}},
  note         = {Machine review of arXiv:1908.04673}
}

abstract

Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science, going back at least to the seminal work of Knuth on stack-sorting (1968). Perhaps the most natural algorithmic question in this area is deciding whether a given permutation of length $n$ contains a given pattern of length $k$. In this work we give two new algorithms for this well-studied problem, one whose running time is $n^{k/4 + o(k)}$, and a polynomial-space algorithm whose running time is the better of $O(1.6181^n)$ and $O(n^{k/2 + 1})$. These results improve the earlier best bounds of $n^{0.47k + o(k)}$ and $O(1.79^n)$ due to Ahal and Rabinovich (2000) resp. Bruner and Lackner (2012) and are the fastest algorithms for the problem when $k \in \Omega(\log{n})$. We show that both our new algorithms and the previous exponential-time algorithms in the literature can be viewed through the unifying lens of constraint-satisfaction. Our algorithms can also count, within the same running time, the number of occurrences of a pattern. We show that this result is close to optimal: solving the counting problem in time $f(k) \cdot n^{o(k/\log{k})}$ would contradict the exponential-time hypothesis (ETH). For some special classes of patterns we obtain improved running times. We further prove that $3$-increasing and $3$-decreasing permutations can, in some sense, embed arbitrary permutations of almost linear length, which indicates that an algorithm with sub-exponential running time is unlikely, even for patterns from these restricted classes.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 11 canonical work pages

[12]

Testing for forbidden order patterns in an array

46 Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, and Christian Sohler. Testing for forbidden order patterns in an array. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 1582–1597,

work page 2017
[1975]

42 Donald E. Knuth. Dancing links.arXiv preprint cs/0011047,

arXiv
[1984]

A new method for solving constraint satisfaction problems

52 Raimund Seidel. A new method for solving constraint satisfaction problems. InProceedings of the 7th International Joint Conference on Artiﬁcial Intelligence, IJCAI 1981, pages 338–342,

work page 1981
[1990]

Finding small patterns in permutations in linear time

33 Sylvain Guillemot and Dániel Marx. Finding small patterns in permutations in linear time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 82–101,

work page 2014
[1997]

Hardness of permutation pattern matching

37 Vít Jelínek and Jan Kyncl. Hardness of permutation pattern matching. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 378–396,

work page 2017
[1998]

16 Karl Bringmann, László Kozma, Shay Moran, and N. S. Narayanaswamy. Hitting set for hypergraphs of low vc-dimension. In24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 23:1–23:18,

work page 2016
[1999]

Fast sorting and pattern-avoiding permutations

8 David Arthur. Fast sorting and pattern-avoiding permutations. InProceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2007, pages 169–174,

work page 2007
[2006]

Stanley-wilf limits are typically exponential.CoRR, abs/1310.8378,

30 Jacob Fox. Stanley-wilf limits are typically exponential.CoRR, abs/1310.8378,

arXiv

Show all 14 references

[2007]

9 Omri Ben-Eliezer and Clément L. Canonne. Improved bounds for testing forbidden order patterns. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 2093–2112,

2018
[2009]

Improving TSP tours using dynamic programming over tree decompositions

23 Marek Cygan, Lukasz Kowalik, and Arkadiusz Socala. Improving TSP tours using dynamic programming over tree decompositions. In25th Annual European Symposium on Algorithms, ESA 2017, pages 30:1–30:14,

2017
[2010]

Permutation Pattern matching in (213, 231)-avoiding permutations.Discrete Mathematics & Theoretical Computer Science, Vol

22 Finding and counting permutations via CSPs 45 Both Neou, Romeo Rizzi, and Stéphane Vialette. Permutation Pattern matching in (213, 231)-avoiding permutations.Discrete Mathematics & Theoretical Computer Science, Vol. 18 no. 2, Permutation Patterns 2015, March

2015
[2015]

Preprint athttps: //arxiv.org/abs/1409.5159. 59 V. Yugandhar and Sanjeev Saxena. Parallel algorithms for separable permutations.Discrete Applied Mathematics, 146(3):343 – 364, 2005

2005 arXiv
[2017]

Keogh, Stefano Lonardi, and Bill Yuan-chi Chiu

38 Eamonn J. Keogh, Stefano Lonardi, and Bill Yuan-chi Chiu. Finding surprising patterns in a time series database in linear time and space. InProceedings of the Eighth ACM SIGKDD 2002 International Conference on Knowledge Discovery and Data Mining, pages 550–556,

2002
[2018]

20 Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak

Springer International Publishing. 20 Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Pattern-avoiding access in binary search trees. InIEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pages 410–423,

2015

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [12]

Testing for forbidden order patterns in an array

46 Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, and Christian Sohler. Testing for forbidden order patterns in an array. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 1582–1597,

work page 2017

[2] [1975]

42 Donald E. Knuth. Dancing links.arXiv preprint cs/0011047,

arXiv

[3] [1984]

A new method for solving constraint satisfaction problems

52 Raimund Seidel. A new method for solving constraint satisfaction problems. InProceedings of the 7th International Joint Conference on Artiﬁcial Intelligence, IJCAI 1981, pages 338–342,

work page 1981

[4] [1990]

Finding small patterns in permutations in linear time

33 Sylvain Guillemot and Dániel Marx. Finding small patterns in permutations in linear time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 82–101,

work page 2014

[5] [1997]

Hardness of permutation pattern matching

37 Vít Jelínek and Jan Kyncl. Hardness of permutation pattern matching. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 378–396,

work page 2017

[6] [1998]

16 Karl Bringmann, László Kozma, Shay Moran, and N. S. Narayanaswamy. Hitting set for hypergraphs of low vc-dimension. In24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 23:1–23:18,

work page 2016

[7] [1999]

Fast sorting and pattern-avoiding permutations

8 David Arthur. Fast sorting and pattern-avoiding permutations. InProceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2007, pages 169–174,

work page 2007

[8] [2006]

Stanley-wilf limits are typically exponential.CoRR, abs/1310.8378,

30 Jacob Fox. Stanley-wilf limits are typically exponential.CoRR, abs/1310.8378,

arXiv