{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiferdg6hxm2rd5hr2hilu7o4emxvhc4bpbtzpzl3f3ioky4k633oi",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mf3zv7qsr6t2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.15015v1",
  "publishedAt": "2026-02-17T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Nikhil Bansal",
    "Arun Jambulapati",
    "Thatchaphol Saranurak"
  ],
  "textContent": "**Authors:** Nikhil Bansal, Arun Jambulapati, Thatchaphol Saranurak\n\nWe present the first polynomial-time algorithm for computing a near-optimal \\emph{flow}-expander decomposition. Given a graph $G$ and a parameter $φ$, our algorithm removes at most a $φ\\log^{1+o(1)}n$ fraction of edges so that every remaining connected component is a $φ$-\\emph{flow}-expander (a stronger guarantee than being a $φ$-\\emph{cut}-expander). This achieves overhead $\\log^{1+o(1)}n$, nearly matching the $Ω(\\log n)$ graph-theoretic lower bound that already holds for cut-expander decompositions, up to a $\\log^{o(1)}n$ factor. Prior polynomial-time algorithms required removing $O(φ\\log^{1.5}n)$ and $O(φ\\log^{2}n)$ fractions of edges to guarantee $φ$-cut-expander and $φ$-flow-expander components, respectively.",
  "title": "Expander Decomposition with Almost Optimal Overhead"
}