Pattern-Sparse Tree Decompositions in H-Minor-Free Graphs

Authors:
Open Access
Publisher website
Google Scholar
Abstract
Given an H-minor-free graph G and an integer k, our main technical contribution is sampling in randomized polynomial time an induced subgraph G′ of G and a tree decomposition of G′ of width O(k) such that for every Z⊆ V(G) of size k, with probability at least (2O(√k)|V(G)|O(1))−1, we have Z ⊆ V(G′) and every bag of the tree decomposition contains at most O(√k) vertices of Z. Having such a tree decomposition allows us to solve a wide range of problems in (randomized) time 2O(√k)nO(1) where the solution is a pattern Z of size k, e.g., Directed k-Path, H-Packing, etc. In particular, our result recovers all the algorithmic applications of the pattern-covering result of Fomin et al. [SIAM J. Computing 2022] (which requires the pattern to be connected) and the planar subgraph-finding algorithms of Nederlof [STOC 2020]. Furthermore, for Kh,3-free graphs (which include bounded-genus graphs) and for a fixed constant d, we signficantly strengthen the result by ensuring that not only Z has intersection O(√k) with each bag, but even the distance-d neighborhood NGd[Z] as well. This extension makes it possible to handle a wider range of problems where the neighborhood of the pattern also plays a role in the solution, such as partial domination problems and problems involving distance constraints.
Funding Information
  • European Research Council (948057)
  • European Research Council (101126229)

This publication has 38 references indexed in Scilit: