betaFeedback

WorksComputer Science

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

Abstract

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 HH, this process is a randomized efficient polynomial-time approximation scheme. Starting from any feasible solution on a graph with nn vertices, it finds a (1−ε)(1-\varepsilon)-approximation within exp⁡(OH(ε−2))n(n+log⁡(1/δ))\exp(O_H(\varepsilon^{-2})) n(n+\log(1/δ)) steps with probability at least 1−δ1-δ. This includes maximum independent set, maximum induced forest, maximum induced bipartite subgraph, and maximum induced subgraph of degree at most one. The proof uses improving exchanges on one fixed division of the input graph into regions. A recursive separator construction performs each exchange inside a region of size rr in at most 2r2r moves, with temporary loss OH(r)O_H(\sqrt r). We count move sequences through each transition and bound the probability of avoiding all near-optimal states. The general theorem bounds the number of Metropolis steps in terms of the temporary loss along improvement paths. We extend the result to bounded weight imbalance and give a weighted-star obstruction for unrestricted weights.

Paper details

vlnc:W_mr7tdn6b
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT

View statement
Looking for related papers…