{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreieilc65ul5z723hndqxxfsfzvuvmxd6vyenfh5zvviv7qzofofdu4",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mifxldxtt4c2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.29825v1",
  "publishedAt": "2026-04-01T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Dániel Marx",
    "Marcin Pilipczuk",
    "Michał Pilipczuk"
  ],
  "textContent": "**Authors:** Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk\n\nGiven 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 $\\widetilde{O}(k)$ such that for every $Z\\subseteq V(G)$ of size $k$, with probability at least $\\left(2^{\\widetilde{O}(\\sqrt{k})}|V(G)|^{O(1)}\\right)^{-1}$, we have $Z \\subseteq V(G')$ and every bag of the tree decomposition contains at most $\\widetilde{O}(\\sqrt{k})$ vertices of $Z$. Having such a tree decomposition allows us to solve a wide range of problems in (randomized) time $2^{\\widetilde{O}(\\sqrt{k})}n^{O(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 $K_{h,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 $\\widetilde{O}(\\sqrt{k})$ with each bag, but even the distance-$d$ neighborhood $N^d_{G}[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.",
  "title": "Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs"
}