The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern
2026-08-31 • Data Structures and Algorithms
Data Structures and AlgorithmsComputational Complexity
AI summaryⓘ
The authors study a problem called Pattern Avoidance, which asks if you can order the vertices of a graph to avoid certain forbidden small patterns. This problem relates to many known graph issues like coloring and bandwidth. They show that deciding Pattern Avoidance is generally very hard (specifically Σ₂^P-complete) and remains difficult even with strong limitations on the graph or patterns. However, they also find special cases where it becomes manageable, including algorithms that work well for certain structured graphs and simpler cases like forests.
Pattern AvoidanceGraph theoryΣ₂^P-completenessFixed-parameter tractabilityVertex orderingVertex integrityNeighborhood diversityVertex coloringBandwidthForests (graphs)
Authors
Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Martin Nöllenburg, Marie Diana Sieper
Abstract
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.