{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreif5bq22rqikhsvazhaksj6di6wxlrdlfp2m6yaxnzr54pe6b7ljoq",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mp3exlfge252"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.25875v1",
  "publishedAt": "2026-06-25T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Yuanhao Wang",
    "Wei Wang"
  ],
  "textContent": "**Authors:** Yuanhao Wang, Wei Wang\n\nLet $n$ and $p$ denote the numbers of vertices and labels, respectively, in an undirected edge-labeled graph. Previous work showed that, under the Exponential Time Hypothesis (ETH), there is no deterministic algorithm with running time \\\\[ (np)^{o\\left(\\frac{\\log n}{(\\log\\log n)^2}\\right)}. \\\\] In this paper, we give a deterministic reduction that strengthens this conditional running-time lower bound to \\\\[ (np)^{o\\left(\\frac{\\log n}{\\log\\log n}\\right)}. \\\\]",
  "title": "A Stronger Conditional Running-Time Lower Bound for Global Label Min-Cut"
}