pith. machine review for the scientific record. sign in

arxiv: 2302.11619 · v1 · submitted 2023-02-22 · 💻 cs.DS · cs.DM

Recognition: 3 theorem links

· Lean Theorem

Pattern detection in ordered graphs

Guillaume Ducoffe , Laurent Feuilloley , Michel Habib , Fran\c{c}ois Pitois
Authors on Pith no claims yet

Pith reviewed 2026-05-09 01:54 UTC · model claude-opus-4-7

classification 💻 cs.DS cs.DM MSC 05C8568Q1768R1005C75
keywords ordered graphsforbidden patternsgraph class recognitionfine-grained complexitysubgraph detectionmerge-widthouterplanar patternsmatrix multiplication
0
0 comments X

The pith

"For ordered graphs, the complexity of detecting a fixed forbidden pattern is governed by a small set of structural parameters — and a new one, merge-width, lets outerplanar patterns be detected in time independent of their size."

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

"An ordered pattern is a small ordered graph with three kinds of vertex-pairs: required edges, forbidden edges, and 'don't care' pairs. Many classical graph classes (interval, chordal, split, bipartite, comparability, …) are exactly the graphs that admit a vertex ordering avoiding some such pattern, so detecting whether a given ordering contains a pattern is the verification half of a recognition algorithm. The paper asks how fast detection can be done as a function of n, and answers it across three regimes. For 3-vertex patterns, almost all admit linear-time detection by careful neighborhood scans, with the same handful of hard cases (Triangle, Comparability) that resist recognition. For 4-vertex patterns, fine-grained reductions from clique, triangle, and 4-hyperclique detection — together with a new randomized shuffle that turns induced subgraph hardness into ordered-pattern hardness — show that subquadratic detection is unlikely for nearly every fully-specified pattern. To explain when detection is fast despite large k, the authors introduce merge-width, a parameter capturing how few 'anchor' vertices need to be tracked while assembling the pattern by merges; bottom-up dynamic programming sped up by rectangular matrix multiplication gives O(n^{ct}) algorithms. As a payoff, every outerplanar pattern — and every pattern close to outerplanar — is detectable in time independent of its size."

Core claim

"The paper organizes the problem 'given a vertex-ordered graph on n vertices, does it contain a fixed ordered pattern on k vertices?' into a coherent complexity map. On three vertices, every pattern except Triangle, Comparability, and their complements is detectable in linear time, and this extends to nearly all hereditary graph classes characterized by 3-vertex patterns. On four vertices, almost every fully-specified pattern requires at least quadratic time under standard fine-grained hypotheses. And a new pattern parameter — merge-width — yields an O(n^{ct}) detection algorithm whose exponent depends only on the parameter, making, for example, all outerplanar patterns detectable in matrix-

What carries the argument

"Three tools carry the paper. (1) A 'rightmost left-neighbour' scanning trick that handles fully-specified 3-vertex patterns like Chordal in linear time without needing a special search like LexBFS. (2) A clique-reduction gadget that maps any k-vertex ordered pattern to k-clique detection in a kn-vertex graph, plus a randomized order-shuffle that turns induced subgraph isomorphism lower bounds into ordered-pattern lower bounds. (3) Merge-width: a parameter measuring, over all ways to build a pattern bottom-up by edge creation, vertex insertion, and a constrained merge of subpatterns sharing 'anchor' vertices, the maximum number of anchors ever live; dynamic programming on the merge tree, acc

If this is right

  • Almost every standard hereditary graph class characterized by 3-vertex forbidden patterns (interval, chordal, split, bipartite, etc.) admits both linear-time order generation and linear-time order verification; the only stubborn cases are comparability and triangle-free.
  • Detecting any fixed pattern on k vertices can be done in roughly n^{\omega k/3} time via the explicit reduction to k-clique on kn vertices, beating the naive n^k bound for every k.
  • Most fully-specified 4-vertex patterns cannot be detected in subquadratic time unless long-standing fine-grained hypotheses (3-clique, hyperclique, or rectangular matrix multiplication conjectures) fail.
  • Outerplanar patterns — and more generally patterns within edit distance d of outerplanar — can be detected in time O(n^{\omega(d+1)}), independent of the pattern's size.
  • Verifying a candidate vertex ordering is sometimes strictly harder than producing one (e.g. comparability), inverting the naive intuition about recognition algorithms.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The merge-width parameter resembles a one-sided analogue of treewidth tailored to the linear vertex order, and may turn out to be comparable to book thickness or to a pattern-specific pathwidth — making it a candidate organizing parameter for the whole landscape of ordered subgraph problems.
  • Because the paper reduces detection of a k-vertex pattern to k-clique detection in a kn-vertex auxiliary graph, any future improvement on rectangular matrix multiplication immediately upgrades pattern detection across the board.
  • The probabilistic reduction from induced subgraph isomorphism via a uniformly random vertex ordering is a generic bridge: improvements on either side (induced subgraph hardness, ordered pattern detection) now translate automatically.
  • Open question worth pressing: is there a dichotomy theorem separating linear-time-detectable patterns from those requiring n^{1+\epsilon}? The 3-vertex picture suggests the boundary tracks fully-specified versus partially-specified patterns plus density of decided edges.

Load-bearing premise

"The quadratic and cubic lower bounds rest on conjectures from fine-grained complexity (clique, triangle, and 4-hyperclique hardness); if any of those conjectures falls, the corresponding hardness for 4-vertex patterns falls with it."

What would settle it

"Exhibit a truly subquadratic algorithm for detecting any one of the fully-specified 4-vertex patterns the paper marks as 2-hard (for instance, any C4-based pattern or any 2K2-based pattern other than Q3): that would refute either the 3-uniform 4-hyperclique hypothesis or the triangle-detection hypothesis the lower bounds rely on."

read the original abstract

A popular way to define or characterize graph classes is via forbidden subgraphs or forbidden minors. These characterizations play a key role in graph theory, but they rarely lead to efficient algorithms to recognize these classes. In contrast, many essential graph classes can be recognized efficiently thanks to characterizations of the following form: there must exist an ordering of the vertices such that some ordered pattern does not appear, where a pattern is basically an ordered subgraph. These pattern characterizations have been studied for decades, but there have been recent efforts to better understand them systematically. In this paper, we focus on a simple problem at the core of this topic: given an ordered graph of size $n$, how fast can we detect whether a fixed pattern of size $k$ is present? Following the literature on graph classes recognition, we first look for patterns that can be detected in linear time. We prove, among other results, that almost all patterns on three vertices (which capture many interesting classes, such as interval, chordal, split, bipartite, and comparability graphs) fall in this category. Then, in a finer-grained complexity perspective, we prove conditional lower bounds for this problem. In particular we show that for a large family of patterns on four vertices it is unlikely that subquadratic algorithm exist. Finally, we define a parameter for patterns, the merge-width, and prove that for patterns of merge-width $t$, one can solve the problem in $O(n^{ct})$ for some constant~$c$. As a corollary, we get that detecting outerplanar patterns and other classes of patterns can be done in time independent of the size of the pattern.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 10 minor

Summary. The paper studies the fine-grained complexity of detecting a fixed ordered pattern P (a vertex-ordered graph with mandatory edges, forbidden edges, and undecided pairs) inside an n-vertex ordered host graph. Three contributions are offered. (i) Linear-time detection: all but four patterns on three vertices (Triangle, Comparability, and complements) can be detected in O(n+m); the result is extended to several pattern families (positive outerplanar forests, positive P4-shaped patterns, geometric patterns from grounded intersection graphs). (ii) Conditional lower bounds: a generic randomized reduction from H-Induced-SI to detection of any H-based fully-specified pattern, plus a "directed-path" reduction from k-clique to patterns whose associated DAG has a unique directed k-path. Together these classify (under hypotheses on clique, hyperclique, and combinatorial triangle detection) every fully-specified 4-vertex pattern as requiring at least n^{2-o(1)} or n^{ω-o(1)} time. (iii) A new pattern parameter, merge-width, and a dynamic-programming-with-matrix-multiplication algorithm running in O(n^{ωt/2}) for patterns of merge-width t; outerplanar patterns are shown to have merge-width 2, giving O(n^ω) detection independent of pattern size, and an extension to bounded outerplanar crossing number.

Significance. The paper opens, in a systematic way, the fine-grained complexity of an algorithmic problem that has been treated implicitly for decades inside graph-class recognition algorithms. The merge-width parameter is genuinely new and the matrix-multiplication speedup is clean: the O(n^ω) bound for outerplanar patterns of arbitrary size is a striking corollary that stands on its own. The classification of 4-vertex fully-specified patterns is comprehensive — the authors plug essentially every gap left by the existing induced-subgraph isomorphism literature using ad hoc reductions (Lemmas 1–3, Proposition 12), which constitutes solid case analysis. The directed-path reduction (Proposition 10) is a small but reusable idea. The open-problems section poses well-formed follow-up questions. As a foundational paper that re-frames an established subarea in fine-grained terms, this is a useful contribution.

major comments (3)
  1. [Lemma 5 (Appendix C.1)] The proof of Lemma 5 is the load-bearing correctness statement for the entire merge-width framework (Theorem 5, Corollary 9), and as written it is too terse. The opening sentence claims 'All the vertices in H that are not active anchors are different, by Item 1c'. Item 1c only asserts that *pattern* vertices in V1∩V2 are anchors; it gives no information about whether a non-anchor u∈V1\V2 and a different non-anchor u'∈V2\V1 might be mapped by the two realizations to the *same* host-graph vertex, which is the actual collision concern. The argument that excludes such host-level collisions is the order-based argument using Item 1e: between consecutive active anchors a<a' in the pattern, Item 1e forces all intermediate pattern vertices to lie exclusively on one side, so the realization on the other side contributes no host vertex strictly between g(a) and g(a'). The next sentence of the proof
  2. [§5 / Appendix C.3, Theorem 5] The complexity claim O(n^{ωt/2}) requires the merge tree to be supplied; the paper does not address how the merge tree is found. For outerplanar patterns Lemma 7 gives an explicit construction, and for fixed patterns the tree can be precomputed in O(1) w.r.t. n, so the published bound is correct as stated for fixed P. However, this should be made explicit, ideally by stating that t and the merge tree are part of the input/precomputation, since the corollary about 'patterns of merge-width t' otherwise reads as if t alone suffices. Relatedly, Theorem 8 asserts complexity O(n^{ω(dist_out(P)+1)}) but the proof only gives merge-width ≤ 2·dist_out(P)+2, which would yield exponent ω(dist_out(P)+1) only via the bound ω(a,b,c) ≤ ω·max(...)/2 used loosely in the analysis. The arithmetic should be stated explicitly so the reader can verify.
  3. [Appendix B.2, Proposition 9] The randomized reduction is correct but its quantitative consequences should be stated more carefully. The reduction yields a one-sided error of (k!−1)/k!; standard amplification by O(k!·log n) repetitions makes it negligible, but k! repetitions is not free in the regime where the conjectured detection time is, e.g., n^{2-o(1)}. For k=4 the constant 24 is fine; please add a sentence noting the amplification cost, since several of your corollaries (e.g., Corollary 6 invoking the C4 lower bound from [6]) are of the form 'requires n^{2-o(1)} time' and the reader should see that the randomized blow-up does not break the conditional lower bound.
minor comments (10)
  1. [Throughout] The submission is presented as an 'overview' with the bulk of the technical content in an appendix that exceeds the main body in length. For an archival journal version, please integrate the appendix into the main text and remove the dual-presentation framing (e.g., the repeated theorem statements between §3 and Appendix A).
  2. [§4.1 / Theorem 3] The reduction blows up the host graph to kn vertices and runs k-clique detection there. The claimed complexity 'roughly n^{ωk/3}' should make clear which clique algorithm is invoked and that the reduction itself takes O((kn)^2) time, which is dominated only when k≥3.
  3. [Definition 5, Item 1e] Item 1e is the most subtle of the conditions and is illustrated only in Figure 11. A formal example showing an attempted divide that violates 1e and a (different) ordered host graph that would mislead a 1e-blind algorithm would help the reader internalize why the condition is the right one. This dovetails with the major comment about Lemma 5.
  4. [§3 / Proposition 1] The bullet for 'Linear Forest' reads 'for all ij∈E(G), with i<j then i=j-1', which is a property check, not a list-manipulation property; please rephrase consistently with the surrounding bullets that operate on N^-(i) and N^+(i).
  5. [Algorithm 1 (Chordal detection)] The complexity argument 'we associate each time the list N^-(i)\{j} to j' is a touch sketchy; a one-line accounting that each edge is visited O(1) times across the whole algorithm would make linearity unambiguous.
  6. [Hypothesis 1] The hypothesis is stated for both clique and independent set detection. Please add a sentence justifying this dual form (the standard literature usually states it for clique only) — you note in §B.1 that complementing in O(n^2) suffices for k≥4 but not for k=3 under ω=2; this is worth keeping.
  7. [Lemma 1, co-paw case] The reduction goes through Gallai's modular decomposition and a case split on the quotient graph. This is fine, but the exposition jumps between cases; a short summary sentence at the top stating 'we handle the (co-)disconnected cases first and reduce to the prime quotient' would improve readability.
  8. [Typography] Numerous OCR-style artifacts in the submitted PDF (e.g., 'Coppersmith- winograd', 'efficient', italic spacing). Please regenerate from a clean source for any revision.
  9. [References] Reference [8] is cited as 'arxiv 2112.00629' without a journal venue, yet results from it are used in §F. If a venue exists, please update; otherwise note it as a preprint.
  10. [Appendix F, Proposition 17] The reduction adds a universal vertex to reduce co-comparability detection to P_ab detection. The argument is one sentence; a concrete check that the universal vertex placement does not create or destroy a co-comparability pattern would be valuable.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for a careful and constructive report and for the recommendation of minor revision. All three major comments concern presentation rather than the validity of our results, and we plan to address each in the revised version. In summary: (1) we will rewrite the proof of Lemma 5 to make explicit the interval-disjointness argument based on Item 1e, which is the actual mechanism preventing host-level collisions between non-anchor images; the appeal to Item 1c in the current draft is misleading. (2) We will state Theorem 5 with the merge tree as part of the input and add a remark on its O(1)-in-n precomputation for fixed patterns, and we will spell out the arithmetic deriving the exponent ω(dist_out(P)+1) in Theorem 8 from the merge-width bound 2·dist_out(P)+2. (3) We will add a paragraph after Proposition 9 explaining why the (k!−1)/k! one-sided error does not affect our conditional lower bounds—our hypotheses are randomized, so no amplification is needed for the lower-bound direction, and standard O(log n) amplification suffices otherwise. None of these revisions change any theorem statement or affect the scope of the results. We have no standing objections.

read point-by-point responses

  1. Referee: Lemma 5 (App. C.1) is too terse. The opening sentence appeals to Item 1c to argue that non-anchor vertices in the two realizations are distinct, but 1c only constrains pattern vertices in V1∩V2; the actual host-level collision concern between u∈V1\V2 and u'∈V2\V1 is excluded by the order-based argument using Item 1e (between consecutive active anchors, all intermediate pattern vertices lie on one side).

    Authors: We agree, and we thank the referee for the precise diagnosis. The current proof conflates two distinct issues: (a) pattern-level identification of vertices appearing in both V1 and V2, which is what Item 1c handles, and (b) host-level collisions between non-anchor images coming from the two realizations, which is in fact controlled by Item 1e. The intended argument is exactly the one the referee spells out: between two consecutive active anchors a<a' in P, Item 1e forces all intermediate pattern vertices to come from a single side (say P1), so the realization of P2 contributes no host vertex strictly between the images g(a) and g(a'); hence the two non-anchor images cannot collide because their relative positions in the host order are forced to lie in disjoint open intervals between consecutive active anchors. We will rewrite the proof of Lemma 5 to first establish this interval-disjointness lemma explicitly using Item 1e, then derive distinctness of the non-anchor images, and finally verify edge consistency. Figure 11 will be referenced at the appropriate point as the canonical illustration of why dropping Item 1e breaks the argument. No statement of the lemma or downstream result changes; only the proof is rewritten for rigor. revision: yes

  2. Referee: Theorem 5 / App. C.3: the O(n^{ωt/2}) bound assumes the merge tree is given. This should be made explicit, since 'patterns of merge-width t' otherwise reads as if t alone suffices. Likewise, Theorem 8's exponent ω(dist_out(P)+1) is obtained from merge-width ≤ 2·dist_out(P)+2 only via the loose bound ω(a,b,c) ≤ ω·max(...)/2, and the arithmetic should be made explicit.

    Authors: Both points are well taken. (1) On the merge tree: throughout the paper P is a fixed pattern of constant size, so a width-t merge tree (when one exists) can be found by brute-force enumeration in time depending only on |V(P)| and t, i.e. O(1) in n. The statement of Theorem 5 should however make this assumption visible. We will revise it to read 'Given a pattern P together with a merge tree of width t, P-detection can be solved in O(n^{ωt/2}) time', and add a remark that for fixed P this precomputation is O(1) in n, so the corollary 'merge-width t implies O(n^{ωt/2})' holds for fixed P. We will also note that we do not address the complexity of computing optimal merge-width as a function of |V(P)|, and flag it as an open question. (2) On Theorem 8: the referee is right that the exponent should be derived explicitly. Setting p = 2·dist_out(P)+2 and applying x ≤ ω·max(|U|+|X|, |X|+|V|, |U|+|V|)/2 + |Y| with |U|+|V|+|X|+|Y| ≤ p gives x ≤ ωp/2 = ω(dist_out(P)+1). We will insert this two-line computation in the proof of Theorem 8 so the reader can verify the arithmetic without rederiving the rectangular-multiplication bound. revision: yes

  3. Referee: Proposition 9 (App. B.2): the randomized reduction has one-sided error (k!−1)/k!, and amplification costs O(k!·log n) repetitions. This should be discussed, especially because corollaries such as Corollary 6 (the C4 lower bound from [6]) are stated as 'requires n^{2-o(1)} time'; the reader should see that the randomized blow-up does not break the conditional lower bound.

    Authors: We agree this deserves an explicit comment. Two observations make the corollaries safe: (a) For the contrapositive direction we use—deriving conditional lower bounds on P-detection from lower bounds on H-Induced-SI—we do not need to amplify at all. If P-detection were solvable in time T(n), then a single run of the reduction yields a randomized H-Induced-SI algorithm with success probability ≥ 1/k! and running time T(n) + O(n); since k is constant, this contradicts an n^{c-o(1)} lower bound for randomized H-Induced-SI just as much as it would contradict the deterministic version, because all our underlying hypotheses (Hypotheses 1–3, and the C4 hardness of [6]) are explicitly stated to hold for randomized algorithms. (b) If one nonetheless wishes to amplify to high probability, O(k!·log n) = O(log n) repetitions for fixed k suffice, which is sub-polynomial and therefore preserves bounds of the form n^{c-o(1)}. We will add a short paragraph after Proposition 9 making both points, and we will cross-reference it from Corollary 6 and the other applications. revision: yes

Circularity Check

0 steps flagged

No significant circularity: results are reductions to/from external complexity hypotheses and self-contained algorithms.

full rationale

The paper's derivation chain is self-contained against external benchmarks. The linear-time detection results (Section 3, Appendix A) are explicit algorithms with correctness proofs that do not rely on self-citation for load-bearing steps. The lower bounds (Section 4, Appendix B) are conditional reductions from standard fine-grained complexity hypotheses (k-Clique, BMM/Triangle, hyperclique) — these hypotheses are external to the authors and widely cited in the community (Vassilevska Williams et al.); citations to [5,6] for k-Clique hardness of induced subgraph isomorphism are used as black-box external results, not as authors' own uniqueness theorems. The merge-width upper bound (Section 5, Appendix C) is an explicit dynamic-programming algorithm whose correctness rests on Lemma 5, proved from the combinatorial Definition 5 of merge operations. The reader's skeptic concern about Lemma 5 (whether Condition 1e is properly used in the proof) is a correctness/proof-gap concern, not a circularity concern: the definition of merge-width and the algorithm are not defined in terms of each other's outputs, no parameter is fitted to the data it then 'predicts,' and no load-bearing claim is justified solely by a self-citation. Self-citations to [8,9] are used to motivate which patterns to study, not to import a load-bearing uniqueness or existence theorem. The paper introduces merge-width as a new parameter, proves a bound for it on outerplanar patterns directly (Lemmas 6,7), and applies standard matrix-multiplication speedup. None of the seven circularity patterns apply.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Model omitted the axiom ledger; defaulted for pipeline continuity.

pith-pipeline@v0.9.0 · 9725 in / 4958 out tokens · 78957 ms · 2026-05-09T01:54:28.138359+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 6 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Random Access Codes: Explicit Constructions, Optimality, and Classical-Quantum Gaps

    quant-ph 2026-04 conditional novelty 7.0

    Explicit optimal classical random access codes are constructed for general L and k, attaining upper bounds for k=L-1 and inducing quantum codes that reach a conjectured bound.

  2. MooD: Perception-Enhanced Efficient Affective Image Editing via Continuous Valence-Arousal Modeling

    cs.CV 2026-05 unverdicted novelty 6.0

    MooD is the first framework to use continuous Valence-Arousal values for fine-grained affective image editing via a VA-aware retrieval strategy, visual transfer, semantic guidance, and the new AffectSet dataset.

  3. MooD: Perception-Enhanced Efficient Affective Image Editing via Continuous Valence-Arousal Modeling

    cs.CV 2026-05 unverdicted novelty 6.0

    MooD introduces continuous valence-arousal modeling with VA-aware retrieval and perception-enhanced guidance for efficient, controllable affective image editing, plus a new AffectSet dataset.

  4. On the power of standard DFS and BFS

    cs.DS 2026-05 unverdicted novelty 6.0

    Standard DFS and BFS suffice to recognize and certify trivially perfect graphs, split graphs, bipartite chain graphs, and proper interval graphs using pattern-avoiding vertex orderings.

  5. From Skill Text to Skill Structure: The Scheduling-Structural-Logical Representation for Agent Skills

    cs.CL 2026-04 unverdicted novelty 6.0

    SSL representation disentangles skill scheduling, structure, and logic using an LLM normalizer, improving skill discovery MRR@50 from 0.649 to 0.729 and risk assessment macro F1 from 0.409 to 0.509 over text baselines.

  6. RDP LoRA: Geometry-Driven Identification for Parameter-Efficient Adaptation in Large Language Models

    cs.LG 2026-04 unverdicted novelty 6.0

    RDP-selected 13 layers for LoRA on Qwen3-8B-Base reach 81.67% on MMLU-Math, beating full 36-layer adaptation at 79.32% and random 13-layer selection at 75.56%.

Reference graph

Works this paper leans on

73 extracted references · 73 canonical work pages · cited by 5 Pith papers

  1. [1]

    A simple linear time certifying LBFS-ba sed algorithm for recognizing trivially perfect graphs and their complement s

    Frank Pok Man Chu. A simple linear time certifying LBFS-ba sed algorithm for recognizing trivially perfect graphs and their complement s. Inf. Process. Lett. , 107(1):7–12, 2008

    work page 2008

  2. [2]

    Corneil, J´ er´ emie Dusart, Michel Habib, and Ekk ehard K¨ ohler

    Derek G. Corneil, J´ er´ emie Dusart, Michel Habib, and Ekk ehard K¨ ohler. On the power of graph searching for cocomparability graphs. SIAM J. Discrete Math. , 30(1):569–591, 2016

    work page 2016

  3. [3]

    Corneil and Richard Krueger

    Derek G. Corneil and Richard Krueger. A unified view of grap h searching. SIAM J. Discrete Math. , 22(4):1259–1276, 2008

    work page 2008

  4. [4]

    Corneil, Yehoshua Perl, and Lorna K

    Derek G. Corneil, Yehoshua Perl, and Lorna K. Stewart. A li near recognition algorithm for cographs. SIAM J. Comput. , 14(4):926–934, 1985

    work page 1985

  5. [5]

    Graph pattern detection: Hardness for all induced patterns and fa ster non-induced cycles

    Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassi levska Williams. Graph pattern detection: Hardness for all induced patterns and fa ster non-induced cycles. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theor y of Com- puting, pages 1167–1178, 2019

    work page 2019

  6. [6]

    I nduced cycles and paths are harder than you think

    Mina Dalirrooyfard and Virginia Vassilevska Williams. I nduced cycles and paths are harder than you think. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 531–542. IEEE, 2022

    work page 2022

  7. [7]

    Algorithm 235: random permutation

    Richard Durstenfeld. Algorithm 235: random permutation . Communications of the ACM , 7(7):420, 1964

    work page 1964

  8. [8]

    Classifying ground ed intersection graphs via ordered forbidden patterns, December, http://arxiv.org/ abs/2112.00629ø, 2021

    Laurent Feuilloley and Michel Habib. Classifying ground ed intersection graphs via ordered forbidden patterns, December, http://arxiv.org/ abs/2112.00629ø, 2021

    work page arXiv 2021

  9. [9]

    Graph classes and fo rbidden patterns on three vertices

    Laurent Feuilloley and Michel Habib. Graph classes and fo rbidden patterns on three vertices. SIAM Journal on Discrete Mathematics (SIDMA) , 35(1):55–90, 2021

    work page 2021

  10. [10]

    Statistical tables for biological, agricultural and medical research

    Ronald Aylmer Fisher and Frank Yates. Statistical tables for biological, agricultural and medical research. Edinburgh: Oliver and Boyd, 1963

    work page 1963

  11. [11]

    C hordal graphs and their clique graphs

    Philippe Galinier, Michel Habib, and Christophe Paul. C hordal graphs and their clique graphs. In Graph-Theoretic Concepts in Computer Science, 21st Intern a- tional Workshop, WG ’95, Aachen, Germany, June 20-22, 1995, Proceedings, pages 358–371, 1995

    work page 1995

  12. [12]

    Transitiv orientierbare graphen

    Tibor Gallai. Transitiv orientierbare graphen. Acta Math. Hungarica , 18(1):25–66, 1967

    work page 1967

  13. [13]

    McConnell, Christophe Paul, and La urent Viennot

    Michel Habib, Ross M. McConnell, Christophe Paul, and La urent Viennot. Lex- bfs and partition refinement, with applications to transiti ve orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. , 234(1-2):59– 84, 2000

    work page 2000

  14. [14]

    Fast rectangular matrix m ultiplication and applications

    Xiaohan Huang and Victor Y Pan. Fast rectangular matrix m ultiplication and applications. Journal of complexity , 14(2):257–299, 1998

    work page 1998

  15. [15]

    Representation of a finite gr aph by a set of intervals on the real line

    C Lekkeikerker and J Boland. Representation of a finite gr aph by a set of intervals on the real line. Fundamenta Mathematicae, 51(1):45–64, 1962

    work page 1962

  16. [16]

    R yan Williams

    Andrea Lincoln, Virginia Vassilevska Williams, and R. R yan Williams. Tight hard- ness for shortest cycles and paths in sparse graphs. In Proceedings of the Twenty- Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1236–1252. SIAM, 2018

    work page 2018

  17. [17]

    McConnell, Kurt Mehlhorn, Stefan N¨ aher, and Pas cal Schweitzer

    Ross M. McConnell, Kurt Mehlhorn, Stefan N¨ aher, and Pas cal Schweitzer. Certi- fying algorithms. Comput. Sci. Rev. , 5(2):119–161, 2011

    work page 2011

  18. [18]

    McConnell and Jeremy P

    Ross M. McConnell and Jeremy P. Spinrad. Modular decompo sition and transitive orientation. Discrete Mathematics , 201(1-3):189–241, 1999. Pattern detection in ordered graphs 15

    work page 1999

  19. [19]

    Paw-free graphs

    Stephan Olariu. Paw-free graphs. Information Processing Letters , 28(1):53–54, 1988

    work page 1988

  20. [20]

    Donald J. Rose, R. Endre Tarjan, and George S. Lueker. Alg orithmic aspects of vertex elimination on graphs. SIAM Journal on Computing , 5(2):266–283, 1976

    work page 1976

  21. [21]

    The graph crossing number and its varia nts: A survey

    Marcus Schaefer. The graph crossing number and its varia nts: A survey. The electronic journal of combinatorics , pages DS21–Apr, 2012

    work page 2012

  22. [22]

    Tarjan and Mihalis Yannakakis

    Robert E. Tarjan and Mihalis Yannakakis. Addendum: Simp le linear-time algo- rithms to test chordality of graphs, test acyclicity of hype rgraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing , 14(1):254–255, 1985

    work page 1985

  23. [23]

    Simple line ar-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs

    Robert Endre Tarjan and Mihalis Yannakakis. Simple line ar-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. , 13(3):566–579, 1984

    work page 1984

  24. [24]

    Simpler linear- time modular decomposition via recursive factorizing perm utations

    Marc Tedder, Derek Corneil, Michel Habib, and Cristophe Paul. Simpler linear- time modular decomposition via recursive factorizing perm utations. In ICALP, pages 634–645. Springer, 2008

    work page 2008

  25. [25]

    Multiplying matrices f aster than coppersmith- winograd

    Virginia Vassilevska Williams. Multiplying matrices f aster than coppersmith- winograd. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012 , New York, NY, USA, May 19 - 22, 2012 , pages 887–898. ACM, 2012

    work page 2012

  26. [26]

    On some fine-grained que stions in algorithms and complexity

    Virginia Vassilevska Williams. On some fine-grained que stions in algorithms and complexity. In Proceedings of the International Congress of Mathematicia ns: Rio de Janeiro 2018 , pages 3447–3487. World Scientific, 2018

    work page 2018

  27. [27]

    Ryan Williams

    Virginia Vassilevska Williams and R. Ryan Williams. Sub cubic equivalences be- tween path, matrix, and triangle problems. J. ACM , 65(5):27:1–27:38, 2018

    work page 2018

  28. [28]

    Yes, Chordal found

    J.-H Yan, J.-J Chen, and G.J. Chang. Quasi-threshold gra phs. Discrete Applied Math., 69 (3), 1996. 16 G. Ducoffe, L. Feuilloley, M. Habib, F. Pitois Appendix table of contents – Appendix A: Detection of patterns on three vertices. – Appendix B: Conditional lower bounds for patterns with k ≥ 4. – Appendix C: Parametrized algorithm and merge-width. – Append...

    work page 1996

  29. [29]

    bipartite permuta- tion

    work page

  30. [30]

    triangle-free ∩ co-chordal

    work page

  31. [31]

    Exceptions are 1-split , 2-star and augmented cliques that are small variations of split, stars and c liques re- spectively

    complete bipartite Most of the classes listed are classic classes. Exceptions are 1-split , 2-star and augmented cliques that are small variations of split, stars and c liques re- spectively. We do not need to define them properly here, hence we r efer to [9]. Easy cases For all this paragraph, we refer to[9] for references. For several classes, the result...

    work page

  32. [32]

    ∪ Vk, such that each Vi is a disjoint copy of V

    V (GQ) = V1 ∪ V2 ∪ . . . ∪ Vk, such that each Vi is a disjoint copy of V . For every v ∈ V , we denote by vi its copy in Vi

    work page

  33. [33]

    , V k are independent sets

    V1, V 2, . . . , V k are independent sets

    work page

  34. [34]

    If vi and vj are adjacent (that is always true if j = i+1) then we add the edges wixj for every adjacent vertices w, x ∈ V

    Then, let i, j be such that 1 ≤ i < j ≤ k. If vi and vj are adjacent (that is always true if j = i+1) then we add the edges wixj for every adjacent vertices w, x ∈ V . Otherwise, we add the edges wixj for every vertices w, x ∈ V that are either equal or nonadjacent

    work page

  35. [35]

    This construction can be done in O((kn)2) time

    Finally, we equip GQ with a total ordering τQ such that: for every 1 ≤ i < j ≤ k, all vertices of Vi must appear before every vertex of Vj. This construction can be done in O((kn)2) time. Assume first that x1, x 2, . . . , x k form a complete subgraph of G. Then, the ordered subgraph of GQ that is induced by x1 1, x 2 2, . . . , x k k realizes the pattern ...

    work page

  36. [36]

    We add new vertices y1, y 2, . . . , y p

    work page

  37. [37]

    For every 1 ≤ i ≤ p and every 1 ≤ j ≤ k, we add edges between yi and every vertex of Vj if and only if ui and vj are adjacent in P

    For every 1 ≤ i < j ≤ p, there is an edge between yi and yj if and only if ui and uj are adjacent in P . For every 1 ≤ i ≤ p and every 1 ≤ j ≤ k, we add edges between yi and every vertex of Vj if and only if ui and vj are adjacent in P . 30 G. Ducoffe, L. Feuilloley, M. Habib, F. Pitois

    work page

  38. [38]

    For every 1 ≤ i < j ≤ p, τP (yi) < τ P (yj)

    We equip GP with a total ordering τP whose restriction to GQ equals τQ. For every 1 ≤ i < j ≤ p, τP (yi) < τ P (yj). For every 1 ≤ i ≤ p and every 1 ≤ j ≤ k, yi must be ordered before (after, resp.) every vertex of Vj if and only if ui is ordered before (after, resp.) vj in P . Recall that if G has a k-clique, then there is an ordered subgraph of GQ that ...

    work page

  39. [39]

    For every v ∈ V , we denote by vi its copy in Vi

    V (G′) = {u} ∪ V1 ∪ V2 ∪ V3, such that each Vi is a disjoint copy of V . For every v ∈ V , we denote by vi its copy in Vi

    work page

  40. [40]

    V1 is a clique and V2, V 3 are independent sets

    work page

  41. [41]

    For every edge vw ∈ E, we add an edge v2w3

    work page

  42. [42]

    For every w ∈ V \ {v} such that v, w are nonadjacent, we also add edges v1w2, v 1w3

    For every vertex v ∈ V we add edges v1v2, v 1v3. For every w ∈ V \ {v} such that v, w are nonadjacent, we also add edges v1w2, v 1w3

    work page

  43. [43]

    This construction can be done in O(n2) time

    Finally, we equip G′ with a total ordering τ′ such that: vertex u appears first, followed by all vertices of V1, all vertices of V2, then all vertices of V3. This construction can be done in O(n2) time. Assume first the existence of some triangle xyz in G. Then, the ordered subgraph of G′ induced by u, x 1, y 2, z 3 realizes Q1(2K2). Conversely, assume the ...

    work page

  44. [44]

    For every v ∈ V , we denote by vi its copy in Vi

    V (G′) = V1 ∪ V2 ∪ V3 ∪ V4, such that each Vi is a disjoint copy of V . For every v ∈ V , we denote by vi its copy in Vi

    work page

  45. [45]

    V1, V 4 are cliques and V2, V 3 are independent sets

    work page

  46. [46]

    For every vertex w ∈ V \ {v}, we add an edge v1w4 if v, w are adjacent, and we add edges v1w2, v 3w4 if v, w are nonadjacent

    For every vertex v ∈ V , we add the edges v1v2, v 2v3, v 3v4. For every vertex w ∈ V \ {v}, we add an edge v1w4 if v, w are adjacent, and we add edges v1w2, v 3w4 if v, w are nonadjacent

    work page

  47. [47]

    We equip G′ with a total ordering τ′, which is just the concatenation of τ1, τ 2, τ 3, τ 4

    Finally, let τ be an arbitrary total ordering of V , and let τ1, τ 2, τ 3, τ 4 denote the respective copies of this ordering for V1, V 2, V 3, V 4. We equip G′ with a total ordering τ′, which is just the concatenation of τ1, τ 2, τ 3, τ 4. This construction can be done in O(n2) time. Assume first the existence of some triangle xyz in G. Then, the ordered s...

    work page

  48. [48]

    If the vertices of Q are ordered as v3, v 1, v 4, v 2, then assuming Hypothesis 1 (for k = 4), every Q-Detection algorithm requires nω (2, 1, 1)− o(1) time

    work page

  49. [49]

    Otherwise, assuming Hypothesis 2, every combinatorial a lgorithm for Q- Detection requires at least n3− o(1) time. Proof. In what follows, let G = (V, E ) be an arbitrary graph. There are several cases to be considered. Each case depends on the total ordering vσ (1), v σ (2), v σ (3), v σ (4) of the four vertices in Q. Case 1 : σ = (3 , 1, 4, 2). There ex...

    work page

  50. [51]

    The subsets V3, V 2 are independent sets, while the subsets V4, V 1 are cliques

    work page

  51. [52]

    For every distinct vertices v, w ∈ V , we add the edge v4w1, and we add the edges v3w4, v 3w2, v 1w2 if vw ∈ E

    work page

  52. [53]

    This construction takes O(n2) time

    Finally, we equip G′ with a total ordering τ′ such that: the vertices of V3 appear first, followed by all vertices of V4, all vertices of V1, then all vertices of V2. This construction takes O(n2) time. Furthermore, if xyz is a triangle of G, then the ordered subgraph that is induced by x3, y 4, y 1, z 2 realizes Q. Conversely, as- sume the existence of an...

    work page

  53. [55]

    Pattern detection in ordered graphs 35

    V1, V 4 are cliques, while V2, V 3 are independent sets. Pattern detection in ordered graphs 35

    work page

  54. [56]

    For every vertex v ∈ V , we add an edge v2v3

    work page

  55. [57]

    We add the edge v1w4 if v, w are either equal or nonadjacent

    Then, we consider each pair v, w ∈ V sequentially. We add the edge v1w4 if v, w are either equal or nonadjacent. We add the edges v1v2, v 3v4, if v, w are adjacent

    work page

  56. [58]

    This construction takes O(n2) time

    Finally, we equip G′ with a total ordering τ′ such that: the vertices of V1 appear first, followed by all vertices of V3, all vertices of V2, then all vertices of V4. This construction takes O(n2) time. Furthermore, if xyz is a triangle of G, then the ordered subgraph that is induced by x1, y 3, y 2, z 4 realizes Q. Conversely, assume the existence of an i...

    work page

  57. [59]

    V (G′) = V1 ∪ V2 ∪ V3 ∪ V4, where each Vi is a disjoint copy of V , For every vertex v ∈ V , let vi denote its copy in Vi

    work page

  58. [60]

    The subsets V1, V 2, V 3, V 4 are cliques

    work page

  59. [61]

    For every v ∈ V , we add the edge v3v4

    work page

  60. [62]

    For every vertices v, w ∈ V , we add the edges v1v2, v 3v2 if v, w are adjacent, and we add the edges v1v3, v 1v4 if v, w are either equal or nonadjacent

    work page

  61. [63]

    This construction takes O(n2) time

    Finally, we equip G′ with a total ordering τ′ such that: the vertices of V1 appear first, followed by all vertices of V3, all vertices of V4, then all vertices of V2. This construction takes O(n2) time. Furthermore, if xyz is a triangle of G, then the ordered subgraph that is induced by x1, y 3, y 4, z 2 realizes Q. Conversely, assume the existence of an i...

    work page

  62. [64]

    (b) V1 ∪ V2 = V (c) Any vertex in V1 ∩ V2 is an anchor in both V1 and V2

    (Divide/merge) Given an anchored pattern P = (V, E ), the divide operation consists creating two patterns P1 = (V1, E 1) and P2 = (V2, E 2) such that the following constraints are satisfied: (a) (E1, E 2) is a partition of E (and the vertex sets inherit the endpoints of the edges, that is, for i = 1, 2, ∀(x, y ) ∈ Ei, x, y ∈ Vi). (b) V1 ∪ V2 = V (c) Any ve...

    work page

  63. [65]

    After the operation, the vertex just before and just after (if they exist) must be anchors

    (Vertex deletion/creation) If a vertex is isolated in a pa ttern, the vertex deletion operation removes it. After the operation, the vertex just before and just after (if they exist) must be anchors. The reverse opera tion is a vertex creation

    work page

  64. [66]

    c reating a pattern

    (Edge deletion/creation) If the pattern consists in only one edge, the edge deletion removes it (and both its endpoints). The reverse operation i s an edge creation . (Here we actually need two cases: one for mandatory edges and one for forbidden edges.) For a divide/merge operation, the anchors that are present in bot h patterns are called active anchors...

    work page

  65. [67]

    Every node is labeled with an anchored pattern. 40 G. Ducoffe, L. Feuilloley, M. Habib, F. Pitois

    work page

  66. [68]

    The root is labeled with an anchored version of pattern P

    work page

  67. [69]

    (b) It has a unique child, and it is labeled with a pattern that can be obtained via a vertex creation from its child’s pattern

    Every node is in one of the following cases: (a) It is a leaf, and then it is labeled with a unique edge. (b) It has a unique child, and it is labeled with a pattern that can be obtained via a vertex creation from its child’s pattern. (c) It has two children, and it is labeled by a pattern that can be obtained by a merge of the patterns of its children. W...

    work page

  68. [70]

    See Figure 15

    (Covering edge) It is has an edge (p1, p k), and we denote by P \(p1, p k) the same pattern without this edge. See Figure 15

    work page

  69. [71]

    We denote by P [1, t ] and P [t, k ] the two patterns using the vertex sets (p1, ..., p t) and (pt, ..., p k) respectively

    (Cut vertex) It has a vertex pt with 1 < t < k , and an edge (p1, p t) such that there is no edge of the form (pi, p j) with i < t < j . We denote by P [1, t ] and P [t, k ] the two patterns using the vertex sets (p1, ..., p t) and (pt, ..., p k) respectively. See Figure 16

    work page

  70. [72]

    We denote by P [2, k ] the rest of the pattern

    (Isolated first) The first vertex p1 is isolated. We denote by P [2, k ] the rest of the pattern. See Figure 17. Fig. 15: Covering edge Fig. 16: Cut vertex Proof. Note that we claim that the only pattern that cannot be decompose d is the single vertex pattern. We do a case analysis on the neighborhoo d of p1, if the pattern is not a single vertex. If p1 has...

    work page

  71. [73]

    the same pattern without this edge

    (Covering edge) There is an edge ( p1, p k), and let P ′ = P \ (p1, p k), i.e. the same pattern without this edge. Let T ′ be the merge tree corresponding to P ′, built by induction. Then the root of T ′ is labeled with an anchored version of P ′, with the vertices p1 and pk being anchored. We build the merge tree T corresponding to P as follows: – The ro...

    work page

  72. [74]

    Let P1 = P [1, t ] and P2 = P [t, k ] be the two patterns using the vertex sets ( p1, ..., p t) and (pt, ..., p k) respectively

    (Cut vertex) There is a vertex pt with 1 < t < k , and an edge ( p1, p t) such that there is no edge of the form ( pi, p j) with i < t < j . Let P1 = P [1, t ] and P2 = P [t, k ] be the two patterns using the vertex sets ( p1, ..., p t) and (pt, ..., p k) respectively. Let T1 be the merge tree corresponding to P1, built by induction, and T2 be the merge t...

    work page

  73. [75]

    max e+ < max N +(j)

    (Isolated first) The first vertex p1 is isolated. Let P ′ = P [2, k ] be the rest of the pattern. Let T ′ be the merge tree corresponding to P ′, built by induction. It means that the root of T ′ is labeled with an anchored version of P ′, with the vertices p2 and pk being anchored. We build the merge tree T corresponding to P as followed: – The root is lab...

    work page