Metraipolis › archive › dc_79eb6f47892f
The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern — arXiv:2608.30667
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.30667
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T10:07:15.935Z
- SHA-256 of the archived text
823d06b7c3a899135b70acfc1fe6cef5bfe65738b2a0f4ee24a82bbf7f896f26- Stable URL of this page
https://metraipolis.com/documento/dc_79eb6f47892f
How to cite
The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern — arXiv:2608.30667 — arXiv (en), https://arxiv.org/abs/2608.30667 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_79eb6f47892f (Metraipolis archive dc_79eb6f47892f, sha256 823d06b7c3a899135b70acfc1fe6cef5bfe65738b2a0f4ee24a82bbf7f896f26)
BibTeX
@misc{dc79eb6f47892f,
title = {The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern — arXiv:2608.30667},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.30667},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_79eb6f47892f; sha256 823d06b7c3a899135b70acfc1fe6cef5bfe65738b2a0f4ee24a82bbf7f896f26},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.30667. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\Sigma_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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-01 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2608.30667 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T10:00:01.290Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).