The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern

Problem setting

• Pattern Avoidance asks whether a graph admits a linear vertex order avoiding an ordered configuration with forced and forbidden edges, generalizing diverse graph-class characterizations.Three-vertex forbidden-pattern classes already include forests, bipartite, interval, chordal, and comparability graphs, while larger patterns capture layout parameters.Source: §1 · p. 2

Complexity lower bounds

• Pattern Avoidance is Σ_2^P-complete, XNLP-complete parameterized by |V(P)| even on constant-pathwidth trees, and W[1]-hard parameterized by graph treedepth even when |E(P)| = 1.These bounds show that restricting pattern size or graph structure alone does not generally yield tractability.Source: §1 · pp. 2–3

Parameterized algorithms

• The paper gives fixed-parameter algorithms parameterized by vertex integrity of G plus |V(P)|, and by neighborhood diversity of G plus |E(P)|.Treedepth cannot simply replace these structural parameters: that would resolve known hardness or open problems for Bandwidth and Queue Number.Source: §1 · p. 3

Forests

• On forests, Pattern Avoidance has an XP algorithm for almost all constant-sized patterns, except patterns with one forced edge whose endpoints both overlap forbidden edges.For the remaining case, fixing the first and last vertices makes testing bandwidth 2 NP-hard, ruling out XP-tractability parameterized by |V(P)| under the stated techniques.Source: §1 · p. 3

Applications

• The framework explains fixed-parameter tractability results for Queue Number, Bandwidth, Odd Cycle Transversal, and vertex-deletion problems targeting co-comparability graphs.The cited applications use combinations of vertex integrity, neighborhood diversity, solution size, target bandwidth, or target queue number as parameters.Source: §1 · pp. 3–4, Figure 1 · p. 4

• The paper fixes notation for graphs, vertex orders, restrictions, predecessors and successors, spanned vertices, and concatenation of disjoint orders.Source: §2 · pp. 4–5

Vertex Integrity and Neighborhood Diversity

• Vertex integrity bounds component sizes after deleting a small vertex set, while neighborhood diversity partitions vertices into finitely many identical-neighborhood types.Neighborhood types form cliques or independent sets, and neighborhood diversity together with its partition is computable in polynomial time [28].Source: §2 · p. 5

Patterns

• A pattern is an ordered vertex set with disjoint forced-edge and forbidden-edge sets, summarized by n_P, m^+_P, m^-_P, and m_P.Source: §2 · p. 5
• An ordered graph matches a pattern when an order-preserving bijection realizes every forced edge and excludes every forbidden edge.Source: §2 · p. 5
• A graph order avoids P when no induced ordered subgraph matches P; C_P comprises graphs admitting such an order, including disconnected graphs.Source: §2 · p. 5

• Pattern Avoidance asks whether a given graph G has a total vertex order avoiding pattern P, with any such order called a solution.Source: §2 · p. 5

3 Complexity-Theoretic Lower Bounds

• The lower-bound framework exploits the expressive power of simple patterns, which can encode graph properties such as 3-colorability and bandwidth at most k.Source: §3 · p. 6

3.1 Pattern Avoidance is ΣP 2-Complete

• Pattern Avoidance is ΣP_2-complete because guessing an order leaves coNP verification, while Generalized Node Deletion reduces to it via patterns encoding K_t-freeness after at most s deletions.Adding s isolated vertices at the start of a clique pattern simulates deleting at most s vertices before avoiding the original pattern.Source: §3.1 · pp. 6–7

3.2 Parameterized Lower Bounds for Pattern Avoidance

• Pattern Avoidance is XNLP-complete parameterized by pattern size n_P even on trees of constant pathwidth, and W[1]-hard parameterized by graph treedepth; both hold for m_P = 1.The reduction uses a pattern representing Bandwidth with n_P = k + 2 vertices and one edge.Source: §3.2 · p. 7

4.1 A Fixed-Parameter Algorithm w.r.t. the Vertex Integrity

• Pattern Avoidance is fixed-parameter tractable when parameterized by vi(G) + nP, using an extended Ramsey Pruning technique.The technique preserves solvability through structured reconstructions rather than proving each individual deletion safe, and requires a subsolution whose size depends on nP.Source: §4.1 · p. 8

4.2 Parameterization by the Neighborhood Diversity + mP

• Pattern Avoidance is fixed-parameter tractable when parameterized by nd(G) + mP, via pattern compression, solution normalization, branching, and bounded-variable integer linear programming.The pattern is compressed to O(mP) critical vertices, while normalized solutions have a parameter-bounded number of neighborhood-type segments.Source: §4.2 · p. 10

4.3 An Algorithm for Almost All Fixed Patterns on Forests

• For every constant-size non-mixed pattern P, Pattern Avoidance is polynomial-time solvable on forests.The algorithm preprocesses left-separated cases using hydra-vertex structure, a fixed side, leaf compression, and bounded-degree reductions before applying sliding-window dynamic programming.Source: §4.3 · pp. 11–13
• 2-Sides Fixed Pattern Avoidance is NP-hard even when G is a forest and nP = 4.The reduction from strongly NP-hard Bin Packing fixes the first and last vertices and uses a bandwidth-two pattern with mP = m+.Source: §4.3 · pp. 13–14
• The mixed-pattern obstruction also implies that deciding whether a forest admits a bandwidth-two order with prescribed first and last vertex is NP-hard.This lower bound shows that standard separation-based dynamic programming would require tracking exponentially many partitions between processed and unprocessed vertices, although fixed mixed-pattern tractability remains open.Source: §4.3 · p. 14

5 A Fixed-Parameter Algorithm w.r.t. the Vertex Integrity

• Pattern Avoidance is fixed-parameter tractable when parameterized by vi(G) + nP.The algorithm assumes nP ≥ 3; patterns with nP ≤ 2 are solvable in polynomial time.Source: §5 · p. 14
• A polynomial-time kernel has size at most 2 ↑↑(p · 2^(2p^2)) · 2^(nP·p) and preserves both solvability and solution reconstruction.Here p = vi(G), and the kernel is obtained by retaining the deletion set, small component-types, and boundedly many large groups.Source: §5 · pp. 15–17
• For a deletion set S whose remaining components satisfy |V(C)| + |S| ≤ p, canonical twins form an equivalence relation, each component has at most p vertices, and there are at most p · 2^(2p^2) classes.Source: §5 · p. 15
• A reduced graph preserves Pattern Avoidance exactly, and a solution for it can be lifted to the original graph in polynomial time.The reduced graph keeps all small equivalence classes and a parameter-bounded number of large groups, pruning larger classes to the threshold required by the construction.Source: §5 · p. 16

5.1 Proof of Lemma 14

• Ramsey pruning extracts nP large groups with identical pairwise order information, yielding a guiding suborder whose representative vertices form consecutive ascending or descending solution-blocks.A monochromatic clique in the edge-colored auxiliary graph supplies the groups, while the resulting block structure guides reinsertion of all removed vertices.Source: §5.1 · pp. 18–20
• Lemma 24 shows that if (G′, P) has a solution, then any supergraph G+ whose large equivalence classes have equal size also has a solution.The construction inserts large groups into the ordering while preserving pattern avoidance.Source: §5.1 · pp. 20–21
• The extension proof replaces solution blocks with suitably oriented copies of large groups and derives a contradiction by restricting any forbidden pattern to a subgraph isomorphic to G−.At most nP large groups intersect a supposed pattern occurrence, so the remaining structure yields a contradiction with the known solution for (G−, P).Source: §5.1 · p. 21
• Lemma 9 follows from Lemma 15, a known algorithm for computing a vertex-integrity witness, closure of YES-instances under vertex deletion, and Lemma 24.These ingredients combine the structural decomposition with the safe insertion of large groups.Source: §5.1 · p. 21

6 Parameterization by the Neighborhood Diversity + mP

• Pattern Avoidance is FPT parameterized by nd(G) + mP.The section proves Theorem 5 for neighborhood diversity nd(G) of G and the number mP of pattern edges.Source: §6 · p. 21

6.1 Bounding Neighborhood-Type Alternations Within Solutions

• The normalization works by enumerating provoking assignments for critical pattern vertices and partitioning the order into safe intervals that permit type-based reordering.There are at most 2(mP + 1) critical vertices and at most nd(G)2(mP +1) assignment functions; provoking assignments encode possible forced and forbidden-edge realizations.Source: §6.1 · pp. 21–23
• Every positive instance has a solution with O(mP) · nd(G)O(mP) · O(nd(G)) neighborhood-type alternations.The proof bounds safe intervals by O(mP) · nd(G)O(mP), then normalizes vertices within each interval by neighborhood type without changing whether the pattern is avoided.Source: §6.1 · pp. 23–26

6.2 An Integer Linear Program for Determining the Size of Segments

• For a bounded segment sequence, the ILP assigns each segment a positive integer size, covers every vertex of each neighborhood type exactly once, and includes constraints enforcing avoidance of P.The segment sequence length is bounded by nd(G) + mP, and adjacent segments may be assumed to have different neighborhood types.Source: §6.2 · p. 26
• The ILP uses segment-size variables and binary variables x^β_{u,v} to encode whether segment distances can accommodate the pattern intervals between critical vertices.It repeats the constraints over all provoking segment assignments β, ensuring that every possible occurrence of the pattern is prevented.Source: §6.2 · pp. 27, 30
• For a provoking segment assignment β, the pattern is prevented exactly when some pair of critical vertices has D^β_{u,v} < 0.Lemmas 32 and 33 establish sufficiency and necessity: negative distance difference prevents a consistent realization, while nonnegative differences allow one.Source: §6.2 · pp. 28–29
• Pattern Avoidance is fixed-parameter tractable when parameterized by nd(G) + m_P.The algorithm branches over possible segment structures and tests feasibility of an ILP whose variable count is bounded by a function of nd(G) + m_P.Source: §6.2 · p. 30
• Pattern Avoidance is fixed-parameter tractable with respect to the vertex cover number vc(G) and the number of pattern edges m_P.This follows from the bound nd(G) ≤ 2vc(G) + vc(G).Source: §6.2 · p. 30

7 An Algorithm for Almost All Constant-Sized Patterns on Forests

• The algorithm targets almost all constant-sized patterns on forests through a dynamic program for structured instances, with mixed patterns excluded by a later NP-hardness result.Patterns with zero or at least two forced edges are handled separately; the dynamic program is extended to all non-mixed patterns, while mixed patterns resist this approach.Source: §7 · p. 30

7.1 Patterns with Zero or At Least Two Forced Edges

• For P = 0 and G a forest, one can decide whether G can avoid P in 2O(nP · log(nP)) time.Source: §7.1 · p. 32

7.2 Patterns with One Forced Edge

• For one-forced-edge instances, preprocessing exploits order-detection procedures and structural properties of forests before the dynamic program is applied.A minimum prefix containing the pattern can be found in O(nG nP · nP^2) time, and every vertex of degree x induces an edge spanning at least ⌈x/2⌉+1 ordered vertices.Source: §7.2 · pp. 32–33
• In any solution, every vertex is spanned by at most 6nP matching edges, while the cited construction forces either |Lv| ≤ 7nP or |Rv| ≤ 10nP.Source: §7.2 · pp. 33–34
• Every hydra vertex must lie among the rightmost 10nP critical neighbors in any solution.This follows because hydra vertices have sufficient interesting degree for the preceding lemmas to apply.Source: §7.2 · p. 36
• The reduction represents fixed-side orders by sequences of vertex types, whose run-length complexity satisfies |T(S)| > 0 ≤ c(S) ≤ |T(S)|.Vertices of the same type are identical or sibling leaves, so their individual identities do not affect the represented order.Source: §7.2 · pp. 36–37
• A 1FF instance reduces to nG^O(nP) 1S1FF instances, constructible in nG^O(nP) time, with every hydra vertex fixed and c(S(≺U)) = 20nP + 2.The reduction preserves positivity: the original instance is positive exactly when at least one generated instance is positive.Source: §7.2 · pp. 37–38
• Trees disjoint from the fixed side can be removed independently: the full instance is positive exactly when the reduced instance and each removed tree, tested with the restricted pattern M(P), are positive.This gives a decomposition rule for components with no fixed-side vertices when |U| ≥ 2nP.Source: §7.2 · pp. 38–39
• For each hydra vertex, only a set of at most 7nP + c(S(≺U)) hydra attachments needs to remain explicit; every other attachment can be solved separately and removed.The retained set must include attachments intersecting U, while the remaining graph and each focused attachment instance must admit solutions.Source: §7.2 · p. 40
• Interesting degree can be reduced to at most 27nP + 2, eliminating hydra vertices from consideration.This follows by reducing each hydra vertex below the 38nP threshold.Source: §7.2 · p. 42
• Solutions can be transformed so a long leaf-type subsequence has bounded alternation, specifically below 2(nP + 1)nP +1.The transformation cuts the order according to assignments of pattern vertices to at most nP types and reorders between cuts without introducing the pattern.Source: §7.2 · pp. 42–43
• A family of nG^nP O(nP) instances can be enumerated while preserving positivity and ensuring every nP free vertices have an unfixed vertex with no neighbors among them.The construction also bounds the compressed fixed-order complexity by (2(nP + 1)nP +2 + 1) · (d>1 max · nP + 1).Source: §7.2 · p. 43
• After iterating that construction 2nP times, each nP-vertex free set has an independent nP-vertex witness in the fixed part, while solvability remains equivalent across the resulting family.The family still has size nG^nP O(nP), and its fixed-order complexity remains bounded by a function in nP O(nP).Source: §7.2 · pp. 44–45
• There is also a solution in which leaf-type alternation between every edge whose endpoints are unfixed is bounded by a quantity in O(nP^2).This normalization is intended to make every such edge fit within the dynamic program’s sliding window.Source: §7.2 · p. 45
• Normalization bounds interesting degrees, type alternation, matchings, and leaf-type sequences, enabling subsequent dynamic programming on structurally restricted forest instances.The normalized instances have bounded interesting degree and type alternation, while their solutions satisfy bounded matching and leaf-sequence properties.Source: §7.2 · pp. 46–47
• Lemma 64 reduces 1FF Pattern Avoidance to a polynomial-size family of Normalized 1S1FF instances, preserving positivity through an AND/OR condition.The family size and construction time are O(n_G f(n_P)) for a computable function f.Source: §7.2 · p. 47

7.3 A Dynamic Program for Normalized Instances

• The dynamic program slides an O(n_P)-sized active window over the order, representing partial solutions as configurations whose transitions prepend vertex types and discard excess window vertices.A solving order corresponds to a path from the unique starting configuration to a final configuration with no remaining vertices.Source: §7.3 · pp. 47–48
• Validity checking and configuration counts are bounded, with validity testable in O(n_G n_P · n_P^2) time and both remaining sets and active windows having n_G^{O(n_P)} possibilities.The DP is sound and complete: positive instances yield solving paths, while solving paths reconstruct pattern-avoiding vertex orders.Source: §7.3 · pp. 48–50
• Normalized 1S1FF Pattern Avoidance can be solved by dynamic programming in time n_G^{O(n_P)}, placing 1FF Pattern Avoidance in XP parameterized by n_P.Source: §7.3 · p. 51

7.4 An Extension to Left Separated Patterns

• For left-separated patterns, the reduction constructs O(n_G^{2n_P} · (2n_P)!) 1FF instances in O(n_G^{5n_P+2}) time, preserving whether the original instance is positive.It removes the pattern’s left part and relies on the absence of forbidden edges between the left and right parts.Source: §7.4 · pp. 51–52
• For every constant-size non-mixed pattern P, Pattern Avoidance is polynomial-time solvable on forests.The extension handles left-separated patterns by reducing them to 1FF Pattern Avoidance; mixed patterns remain outside the algorithm.Source: §7.4 · pp. 51–52

7.5 Fixing Two Sides of the Solution Makes the Problem NP-hard

• 2-Sides Fixed Pattern Avoidance is NP-hard on forests with n_P = 4 and m_P = m^+, and remains NP-hard on trees with n_P = 5.Consequently, deciding whether a forest has a bandwidth-two order with prescribed first and last vertices is NP-hard.Source: §7.5 · pp. 53, 55

Concluding remarks

• Pattern Avoidance remains challenging: standard graph parameters such as treewidth cannot yield tractability, since hardness already holds for very simple patterns.The paper frames this as a consequence of the problem’s generality.Source: §8 · p. 55

Open questions

• On forests, whether Pattern Avoidance is in XP parameterized by n_P remains open in one non-left-separated case, despite affirmative results for all others.Theorem 7 provides a lower bound indicating likely intractability for the remaining case.Source: §8 · p. 55
• The complexity of Pattern Avoidance parameterized by n_P plus the treedepth of G remains open, including the rainbow-pattern case corresponding to Queue Number [3].Settling Queue Number parameterized by treedepth is identified as a natural first step.Source: §8 · p. 55
• The complexity of Pattern Avoidance parameterized by m_P plus the vertex integrity of G also remains open, with Bandwidth under vertex integrity highlighted as a prerequisite special case [21].The cited recent work explicitly notes the corresponding parameterized complexity of Bandwidth as open.Source: §8 · p. 55