Delphi.science

Single-Vertex Metropolis on Minor-Free Graphs: A General EPTAS

Source: arxiv.org/abs/2611.22023

Daniel Skachkov, Yuriy Dorn

arXivarxiv/2611.22023Nov 17, 2026cs.DSscore 0

We consider a class of combinatorial optimization problems where the goal is to find a largest induced subgraph with a prescribed property. We assume that the property is preserved by taking induced subgraphs and disjoint unions, holds for all edgeless graphs, and can be tested in polynomial time. We study the single-vertex Metropolis process for this class of problems. We show that on graphs excluding an arbitrary fixed minor $H$, this process is a randomized efficient polynomial-time approximation scheme. Starting from any feasible solution on a graph with $n$ vertices, it finds a…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.22023
curl -X POST /api/v1/records/arxiv/2611.22023/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.22023/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'