Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs

NEW

Problem: Reconstructed conjecture: for every efficiently fractionally treewidth-fragile class $\mathcal C$ of finite simple graphs, the nonnegative rational weighted Minimum Vertex Cover problem admits a PTAS on $\mathcal C$. Here “efficiently” means that, for each $\eta>0$, one can in polynomial time output a finite $\eta$-thin distribution over sets $X\subseteq V(G)$ such that $\operatorname{tw}(G-X)\le t(\eta)$. This is the natural algorithmic reading of “exists a PTAS.” The broader phrase about all hereditary sublinear-separator classes is more ambiguous; the metadata singles out the fractionally-treewidth-fragile version.

Result: The conjecture is true.

Let $\tau_w(G)$ be the minimum weight of a vertex cover and $\alpha_w(G)$ the maximum weight of an independent set.

First, efficient fractional treewidth-fragility gives a PTAS for maximum weight independent set: for an $\eta$-thin distribution $\{X_i\}$, solve MWIS exactly on each bounded-treewidth graph $G-X_i$, and choose the best solution. If $I^\star$ is optimum in $G$, then

so some $i$ yields an independent set of weight at least $(1-\eta)\alpha_w(G)$. Exact bounded-treewidth dynamic programming is polynomial for fixed $\eta$.

Now apply the weighted Nemhauser–Trotter theorem to $G$. It gives in polynomial time a partition

such that

and $V_0$ has no edges to $V_0\cup H$. The fragility distribution for $G$, restricted to $H$, still leaves bounded treewidth, so run the MWIS PTAS on $G[H]$ with parameter $\varepsilon$, obtaining $I\subseteq H$ with

Output

This is a vertex cover: edges incident with $V_1$ are covered, there are no edges from $V_0$ to $V_0\cup H$, and $H\setminus I$ covers all edges of $G[H]$.

Let $W=w(H)$, $\tau=\tau_w(G[H])$, and $\alpha=\alpha_w(G[H])$. Since complements of vertex covers are independent sets,

Also $\tau\ge W/2$, hence $\alpha\le\tau$. Therefore

Thus weighted Minimum Vertex Cover has a PTAS on efficiently fractionally treewidth-fragile classes. Zero-weight and empty cases are covered by the same inequalities.

Verification audit: the proof uses only finite simple graphs, nonnegative vertex weights, efficient fractional treewidth-fragility, bounded-treewidth exact DP, and the weighted Nemhauser–Trotter theorem. No heredity assumption is needed for the fractionally-fragile version, since the deletion distributions restrict to induced subgraphs.

Citation: The classical structural ingredient is Nemhauser and Trotter, “Vertex packings: structural properties and algorithms,” Mathematical Programming 8 (1975), 232–248. The PTAS corollary above is derived here from that theorem and fractional treewidth-fragility.