Metraipolis › archive › dc_ff042f7443a1
Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth-$η$ Deletion — arXiv:2608.09800
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.09800
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T09:16:43.087Z
- SHA-256 of the archived text
91aa23e4fba07b51bf7f781c6f6d4decceb64475fffaa108301fa5ed4c54003b- Stable URL of this page
https://metraipolis.com/documento/dc_ff042f7443a1
How to cite
Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth-$η$ Deletion — arXiv:2608.09800 — arXiv (en), https://arxiv.org/abs/2608.09800 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ff042f7443a1 (Metraipolis archive dc_ff042f7443a1, sha256 91aa23e4fba07b51bf7f781c6f6d4decceb64475fffaa108301fa5ed4c54003b)
BibTeX
@misc{dcff042f7443a1,
title = {Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth-$η$ Deletion — arXiv:2608.09800},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.09800},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ff042f7443a1; sha256 91aa23e4fba07b51bf7f781c6f6d4decceb64475fffaa108301fa5ed4c54003b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.09800. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For a constant $\eta \geq 0$, Pathwidth-$\eta$ Deletion is the problem of deciding whether, for a given graph $G$ and integer $k$, there is a set $S \subseteq V(G)$ of size at most $k$ such that the pathwidth of $G - S$ is at most $\eta$. The problems Treewidth-$\eta$ Deletion and Treedepth-$\eta$ Deletion are defined similarly for the parameters treewidth and treedepth, respectively. A landmark result of Fomin et al. [FOCS, 2012] shows that, for any constant $\eta$, all three problems admit a kernel on $O(k^{c(\eta)})$ vertices, where $c(\eta)$ is a constant depending on $\eta$. Giannopoulou et al. [ACM TALG, 2017] show that, in some sense, this result is optimal for Treewidth-$\eta$ Deletion: for $\eta \geq 2$ and even when parameterizing by the size of a vertex cover $M$ of the input graph, there is no kernel of size $O(|M|^{\frac{\eta+1}{2}-\varepsilon})$, for any $\varepsilon > 0$. Contrasting this result, they prove that Treedepth-$\eta$ Deletion admits a uniform polynomial kernel, that is, a kernel of size $O(k^c)$ for a constant $c$ that is independent of $\eta$. In comparison, the question whether Pathwidth-$\eta$ Deletion admits a uniform polynomial kernel has been neglected in the literature. As treewidth and pathwidth tend to behave similarly, it is natural to expect that no uniform kernel exists when parameterizing by the size of a vertex cover. Surprisingly, we show this not to be the case. More concretely, we prove the existence of a uniform polynomial kernel for Pathwidth-$\eta$ Deletion when parameterizing by (1) the solution size $k$ plus the size of a set $M$ such that $G - M$ has bounded treedepth; (2) the (vertex-deletion) distance to pathwidth-$1$ graphs; (3) the distance to the class of graphs with treedepth at most $\eta + 1$. This leads us to conjecture that Pathwidth-$\eta$ Deletion admits a uniform kernel when parameterizing by the solution size $k$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2608.09800 — 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-19T09:13:57.846Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).