Source-linked AI summary
The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern
Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Martin Nöllenburg, Marie Diana Sieper
TL;DR
Pattern Avoidance asks whether a graph admits a vertex order avoiding a specified forced-and-forbidden edge pattern, a framework encompassing several graph problems. The paper proves strong classical and parameterized lower bounds, then gives structural fixed-parameter algorithms and an XP algorithm for almost all fixed patterns on forests.
Problem
Pattern Avoidance studies whether a graph admits a linear vertex order avoiding a given ordered pattern, generalizing several graph-ordering and vertex-deletion problems.
Method
The paper combines complexity reductions with algorithms parameterized by vertex integrity plus |V(P)|, neighborhood diversity plus |E(P)|, and forest-restricted pattern structure.
Results
Pattern Avoidance is Σ_2^P-complete, remains hard under strong parameter and graph restrictions, and admits the stated fixed-parameter and forest XP algorithms.
Takeaways & Limitations
Recognizing graph classes defined by a single forbidden ordered pattern has a unified tractability framework based on structural graph parameters and pattern size.
Takeaways & Limitations
The complexity of Pattern Avoidance parameterized by m_P plus vertex integrity remains open, as does the treedepth-plus-pattern-vertex parameterization.
Abstract
from arXiv · showhide
In this paper, we study the Pattern Avoidance problem of determining whether a given graph $G$ admits a linear vertex order which avoids a given pattern $P$, i.e., a vertex sequence with some forced and forbidden edges, on every suborder. Such patterns form a natural ordered counterpart to induced subgraphs in the order-invariant setting, and it is known that Pattern Avoidance captures a broad variety of graph problems including Bandwidth, Vertex Coloring, Queue Number, and extends to vertex-deletion problems such as Odd Cycle Transversal. We show that Pattern Avoidance is $Σ_2^{\textsf{P}}$-complete and furthermore remains intractable (in both the classical and parameterized sense) even under a variety of severe restrictions to both the pattern $P$ and the graph $G$. As our main contributions, we complement these lower bounds with the following tractability results, which provide a unifying framework for recognizing pattern-definable graph classes: - a fixed-parameter algorithm w.r.t. the vertex integrity of $G$ plus $|V(P)|$, - a fixed-parameter algorithm w.r.t. the neighborhood diversity of $G$ plus $|E(P)|$, and - a polynomial algorithm for Pattern Avoidance on forests for almost all constant-sized patterns.
1 Introduction
Pattern Avoidance generalizes many graph-ordering and vertex-deletion problems through forbidden ordered patterns. The paper establishes strong lower bounds and identifies tractable parameterizations using structural restrictions on the graph.
- Motivation: Forbidden ordered patterns characterize diverse graph classes and capture problems including queue number, bandwidth, and vertex-deletion variants.Solid and dashed pattern edges encode forced and forbidden adjacencies, respectively.
- Lower bounds: Pattern Avoidance is Σ_2^P-complete, XNLP-complete with respect to |V(P)| on constant-pathwidth trees, and W[1]-hard with respect to graph treedepth even when |E(P)| = 1.These results demonstrate intractability under severe restrictions on both patterns and input graphs.
- Tractability: A fixed-parameter algorithm is provided for Pattern Avoidance parameterized by vertex integrity of G plus |V(P)|.This framework yields, among other consequences, fixed-parameter tractability of Queue Number with respect to vertex integrity.
- Tractability: A fixed-parameter algorithm is also provided parameterized by neighborhood diversity of G plus |E(P)|.The introduction applies this framework to bandwidth and several vertex-deletion problems.
- Forests: On forests, Pattern Avoidance has an XP algorithm for almost all patterns, excluding those with one forced edge whose endpoints both overlap forbidden edges.The remaining case has a hardness result for bandwidth 2 on forests with fixed first and last vertices.
2 Preliminaries
The preliminaries formalize ordered patterns, their realizations, and the Pattern Avoidance decision problem, while introducing vertex integrity and neighborhood diversity as structural parameters.
- Structural parameters: Vertex integrity is the minimum k for which deleting a set S leaves components whose sizes plus |S| are at most k.The witnessing deletion set can be computed using a fixed-parameter algorithm.
- Structural parameters: Neighborhood diversity partitions vertices into neighborhood types, with every type inducing either a clique or an independent set.The number of types and their partition are computable in polynomial time.
- Patterns: A pattern is a totally ordered vertex set with disjoint forced-edge and forbidden-edge sets.The notation distinguishes the pattern’s vertices, forced edges, forbidden edges, and total number of constrained pairs.
- Patterns: An ordered graph matches a pattern when an order-preserving bijection satisfies every forced and forbidden edge constraint.The bijection maps pattern vertices to graph vertices while preserving order and adjacency requirements.
- Pattern Avoidance: Pattern Avoidance asks whether a graph has a total vertex order containing no realization of the specified pattern.Such an order is called a solution, and the corresponding graph class is denoted C_P.
3 Complexity-Theoretic Lower Bounds
The paper proves that Pattern Avoidance has high classical and parameterized complexity by combining a coNP verification view with reductions from deletion and bandwidth problems.
- Σ_2^P-hardness: Pattern Avoidance is Σ_2^P-hard via a reduction from Generalized Node Deletion Problem.The reduction uses a pattern formed by adding isolated leading vertices to a clique pattern.
- Deletion reductions: Adding d isolated vertices at the beginning of a pattern represents allowing deletion of at most d vertices before avoiding the original pattern.This lemma transfers vertex-deletion complexity into Pattern Avoidance.
- Membership: Pattern Avoidance belongs to Σ_2^P because one can guess an order and verify its pattern avoidance using a coNP predicate.For a fixed order, a realization of the pattern certifies non-avoidance and can be checked in polynomial time.
- Parameterized hardness: Bandwidth supplies parameterized lower bounds because it is a special case of Pattern Avoidance with one constrained edge.Known hardness of Bandwidth transfers to Pattern Avoidance under restricted graph classes and parameters.
- Parameterized hardness: Pattern Avoidance is XNLP-complete with respect to n_P on constant-pathwidth trees and W[1]-hard with respect to graph treedepth, even when m_P = 1.These are stated jointly in Theorem 3.
4 Technical Overview of Algorithmic Results
The paper develops three algorithmic approaches for Pattern Avoidance: Ramsey pruning under vertex integrity, ILP under neighborhood diversity, and dynamic programming on forests for almost all fixed patterns.
- Vertex integrity: Theorem 4 gives an FPT algorithm parameterized by vertex integrity vi(G) plus pattern size nP.The approach extends Ramsey Pruning to preserve a well-structured solution while removing repeated components.
- Vertex integrity: Ramsey Pruning uses repeated components and a guiding subsolution to reconstruct solutions after pruning copies of subgraphs.Unlike direct kernelization, it does not prove each deletion safe independently; instead, it preserves solvability across the pruning sequence.
- Neighborhood diversity: Theorem 5 gives an FPT algorithm parameterized by neighborhood diversity nd(G) plus the number of pattern edges mP.Vertices within neighborhood types are interchangeable for representing forced and forbidden edges, while relevant pattern structure is reduced to edges and incident vertices.
- Neighborhood diversity: The neighborhood-diversity algorithm bounds alternations between segments of each type, then uses integer linear programming to distribute vertices among those segments.The pattern is compressed to O(mP) critical vertices, retaining first and last vertices, edge endpoints, and interval lengths.
- Forests: For every constant-size non-mixed pattern P, Pattern Avoidance is polynomial-time solvable on forests.The forest algorithm first handles patterns with zero or at least two forced edges, reducing the remaining nontrivial case to one forced edge and distinguishing left-separated patterns.
- Forests: The mixed-pattern boundary is hard: Pattern Avoidance is NP-hard on forests even when the first and last ordering vertices are fixed, yielding NP-hardness for bandwidth two with prescribed endpoints.This rules out the proposed two-sided fixed-end dynamic-programming route and leads to Corollary 8.
5 A Fixed-Parameter Algorithm w.r.t. the Vertex Integrity
The section develops a kernelization framework based on vertex integrity, reducing Pattern Avoidance to a bounded reduced graph while preserving solutions, and derives fixed-parameter tractability.
- Algorithmic consequence: Pattern Avoidance is fixed-parameter tractable when parameterized by vi(G)+nP.The theorem follows from the reduced-graph construction and the safeness lemma.
- Kernel construction: The algorithm groups components of G−S into twin equivalence classes according to canonical isomorphisms and outside connections.Each component has at most p vertices, and the number of equivalence classes is bounded by p·2^(2p^2)/p! in the supplied bound.
- Kernel construction: Reduced graphs retain S, all components in small equivalence classes, and a bounded number of large groups representing frequent component types.Classes exceeding the threshold are pruned to the threshold size, while small classes are included in S′.
- Safeness: A reduced graph is equivalent to the original instance: (G,P) has a solution if and only if (G′,P) does, and solutions can be reconstructed in polynomial time.This is the safeness guarantee underlying the kernel.
- Safeness: Ramsey pruning extracts nP large groups with identical pairwise information, providing the repeated structure needed to reinsert removed components.The proof obtains these groups from a monochromatic clique of size at least nP.
6 Parameterization by the Neighborhood Diversity + mP
The section normalizes candidate solutions by neighborhood types, bounds the resulting alternations through safe intervals, and uses integer linear programming to decide segment sizes.
- Setup: Vertices are partitioned into neighborhood types, with two vertices equivalent when their neighborhoods agree after excluding each other.This parameterization uses nd(G), the number of neighborhood types, together with mP, the number of pattern edges.
- Pattern compression: The pattern is compressed by replacing maximal consecutive runs of non-critical vertices with their lengths, yielding a representation linear in mP.There are at most 2(mP+1) critical vertices.
- Safe intervals: Provoking assignment functions map critical pattern vertices to neighborhood types and encode potential ways of realizing the pattern.They preserve adjacency requirements for forced and forbidden pattern edges.
- Safe intervals: Cuts induced by all provoking assignments partition a solution into safe intervals, within which vertices can be reordered without creating the pattern.The number of safe intervals is at most O(mP)·nd(G)^(O(mP)).
- Normalization: Every positive instance has a solution with O(mP)·nd(G)^(O(mP))·O(nd(G)) neighborhood-type alternations.This permits decomposition into boundedly many segments, whose internal vertex order is irrelevant within a type.
- Integer linear programming: An ILP assigns vertex counts to boundedly many neighborhood-type segments and adds constraints preventing every provoking segment assignment from realizing the pattern.Feasibility over all branches is equivalent to positivity, and ILP feasibility is FPT in the number of variables.
- Algorithmic consequence: Pattern Avoidance is fixed-parameter tractable parameterized by nd(G)+mP, and consequently by vc(G)+mP.The latter follows from the neighborhood-diversity result and the stated corollary.
7 An Algorithm for Almost All Constant-Sized Patterns on Forests
The paper develops polynomial-time recognition for Pattern Avoidance on forests for every constant-size non-mixed pattern, using reductions, normalization, and dynamic programming, while identifying a remaining NP-hard fixed-endpoint case.
- Normalization: A family reduction transforms 1S1FF instances into equivalent instances with fixed vertices and bounded sequence complexity.The construction preserves positivity and fixes every hydra vertex while setting the sequence complexity to 20nP + 2.
- Dynamic programming: The dynamic program uses a right-to-left active window of O(nP) vertices to construct a solution for normalized instances.A solution exists exactly when the corresponding decomposition graph contains a solving path, and Theorem 72 finds one in nG^nP · O(nP) time.
- Complexity consequence: Consequently, 1FF Pattern Avoidance parameterized by pattern size is in XP, yielding polynomial time for every fixed applicable pattern.The result applies when the pattern has no or at least two forced edges, or when its single forced edge satisfies the stated left-separation conditions.
- Theorem 6 gives a polynomial-time algorithm on forests for every constant-size non-mixed pattern.
- Boundary: The approach excludes mixed patterns in one remaining case, and two-sides fixed Pattern Avoidance is NP-hard even on forests with a four-vertex pattern.The hardness result is stated for the two-sides fixed problem, not for unrestricted Pattern Avoidance on all forests.
8 Concluding Remarks
Pattern Avoidance remains challenging despite the paper’s parameterized results, with open questions concerning forests and treedepth-based parameterizations.
- Standard graph parameters such as treewidth do not yield tractability, because intractability already arises for very simple patterns.
- On forests, Pattern Avoidance is in XP with respect to nP for all but one remaining non-left-separated case.Theorem 7 provides a lower bound suggesting intractability for that remaining case.
- The complexity of Pattern Avoidance parameterized by nP plus the treedepth of G remains open.A proposed first step is resolving the complexity for rainbow patterns, including Queue Number.