{"id":"bc48c161-905d-4a37-8707-b7bad5852ad5","arxiv_id":"1908.04673","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Permutation Pattern Matching can be solved in n^{k/4+o(k)} time and in O(1.6181^n) polynomial-space time, with matching counting algorithms and an ETH-based near-optimal lower bound for the counting problem.","lead":"Two algorithmic results improve the best known running times for deciding whether one permutation contains another, framing the search as a constraint satisfaction problem. The new bounds are n^{k/4+o(k)} in general and O(1.6181^n) with polynomial space, and the counting version is shown nearly optimal under a standard hardness assumption.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The k/4 exponent in Theorem 1 rests on an unproved treewidth reduction: deleting |X|-1 strip-crossing edges is asserted to lower treewidth to (k-|X|)/3, which does not follow from Lemma 9 and is not derived.","rationale":"The reader's weakest assumption matches the main gap I find. Section 3's k/4 improvement is the paper's headline, and the treewidth bound (k-|X|)/3 is asserted with a citation but no proof; it is not derivable from Lemma 9 by the argument given, since deleting a matching of edges does not reduce the vertex count or maximum degree for the degree-based bound. The running-time sum collapses to k/4 exactly when this stronger bound holds; otherwise only the k/3 result is obtained. I also note the paper's self-identified limitations: special-pattern details deferred to a forthcoming thesis (Section 4) and the acknowledgement of a previous error in the Theorem 2 analysis, but these are secondary. If the treewidth bound can be supplied, the paper's main results are plausible; hence the CONDITIONAL verdict is appropriate. My concrete test attempts to falsify the bound on small cubic-expander-based instances, which is feasible with exact treewidth solvers and would settle whether the concern actually lands.","tokens_in":20523,"tokens_out":42670,"duration_ms":432773,"concrete_test":"Construct a permutation pi whose incidence graph is the union of a high-treewidth cubic graph H (e.g., a Fomin-Hoie worst-case cubic graph or a random cubic Hamiltonian expander) and the horizontal path 1,2,...,k, with H's perfect matching placed on pairs (1,2),(3,4),...; then set the text tau = pi and partition into blocks of size two. Compute the exact treewidth of G_pi with the crossing edges {(2,3),(4,5),...} deleted. If it exceeds (k - |{1,3,5,...}|)/3 ≈ k/6, the k/4 analysis is invalid; if it never exceeds the bound on these instances, the assertion still needs a proof before the theorem can be accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central contribution, Theorem 1 (PPM in n^{k/4+o(k)}), depends entirely on the assertion in Section 3 that after guessing the leftmost strip-entry set X and deleting the |X|-1 horizontal constraints that cross strip boundaries, the remaining constraint graph has treewidth at most (k-|X|)/3 + o(k), cited to [28,23]. This is not a consequence of Lemma 9: that lemma bounds treewidth by k/3 for any max-degree-4 graph, and deleting a matching of size |X|-1 leaves k vertices and max degree 4, so the bound k/3 still applies. The paper provides no derivation, and the cited sources are not reproduced. The k/4 running-time calculation n^{|X|/4} * n^{(3/4)(k/3-|X|/3)} = n^{k/4+o(k)} is only valid with the stronger (k-|X|)/3 bound. If that bound fails, Theorem 1 falls back to the k/3 result. The gap is real rather than cosmetic: one can realize a cubic expander H as a permutation incidence graph G with a matching M of horizontal edges such that G-M = H; with strip blocks of size two, |X| is about k/2, and the asserted bound is about k/6, which would contradict any H with treewidth greater than k/6. Thus the main new exponent is unsupported as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":20818,"tokens_out":39024,"duration_ms":416334,"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":[{"comment":"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.","section":"Section 3 (running-time derivation of Theorem 1)"}],"minor_comments":[{"comment":"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":"Section 5 (definition of PSI)"},{"comment":"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":"Section 2 (proof of Lemma 7)"},{"comment":"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":"Section 4 (proof of Theorem 5(i))"},{"comment":"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.","section":"Section 4 (proof of Theorem 6)"}],"recommendation":"reject","confidential_remarks":"The flaw in Section 3 is decisive for the paper's headline result: the treewidth-reduction assertion is not merely unproved but appears to be false in the generality needed, and the counterexample is realizable with a valid permutation incidence graph and a valid strip structure. I would not recommend a revision aimed at patching Theorem 1. The remaining contributions — the even-odd algorithm, the ETH lower bound for counting, and the special-pattern treewidth results — seem sound and could form the basis of a separate, more modest paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThat'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.\n\nWho 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.\n\nRecommendation: 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.","headline":"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.","tokens_in":21388,"tokens_out":9560,"would_cite":true,"duration_ms":97621,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A05","05C85","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["permutation pattern matching","constraint satisfaction","treewidth","incidence graph","pattern counting","exponential-time hypothesis","parameterized complexity"],"falsifier":"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.","tokens_in":20336,"feed_emoji":"🔍","tokens_out":9125,"duration_ms":90193,"temperature":0.7,"pith_summary":"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).","feed_headline":"Permutation matching speeds up to n^{k/4+o(k)}","feed_subtitle":"A CSP reformulation plus strip guessing beats the old n^{0.47k} and O(1.79^n) bounds.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes the previous n^{0.47k+o(k)} running time that Theorem 1 must beat.","marker":"[1]"},{"why":"Gives the previous O(1.79^n) bound for the n-only regime, improved by Theorem 2.","marker":"[18]"},{"why":"Provides the treewidth-based CSP algorithm (Lemma 8) that solves the reduced instance in O(n^{t+1}).","marker":"[32,24]"},{"why":"Supplies the pathwidth/treewidth bound k/3+o(k) for maximum-degree-4 graphs, the basis of the k/4 analysis.","marker":"[28,29]"},{"why":"Contributes the strip-guessing technique that lowers the exponent from k/3 to k/4.","marker":"[23]"},{"why":"Introduces the fixed-parameter PPM algorithm and the partitioned PPM problem, and notes that the FPT approach cannot count; the paper's counting lower bound works through this contrast.","marker":"[33]"},{"why":"Supplies the ETH-hardness of partitioned subgraph isomorphism, the starting point of the counting lower bound.","marker":"[44]"}],"fun_headline_variants":["Permutation matching drops to n^{k/4+o(k)} via CSP","Counting near-optimal: no n^{o(k/log k)} under ETH","Strip guessing plus CSP: permutation match in n^{k/4+o(k)}","New bounds: n^{k/4} match, count near-optimal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Permutation matching drops to n^{k/4+o(k)} via CSP","Counting near-optimal: no n^{o(k/log k)} under ETH","Strip guessing plus CSP: permutation match in n^{k/4+o(k)}","New bounds: n^{k/4} match, count near-optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001462,"raw_usage":{"total_tokens":5955,"prompt_tokens":1090,"completion_tokens":4865,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":706,"completion_tokens_details":{"reasoning_tokens":4779}},"tokens_in":706,"tokens_out":4865,"duration_ms":37245,"temperature":1.0,"reasoning_tokens":4779,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:35:33.659580+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}