QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators

arXiv:2610.16025 · cs.DS, cs.DM, cs.LO, math.CO · Submitted 2026-10-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators".

Jane: Here's the gist of the paper. A hereditary graph class has strongly edge-sublinear separators if, for some constant 0 ⩽ b < 1, its m-edge graphs admit balanced separators of size O(mb) <ref:2610.16025.

Tom: We show that Max Weight Independent Set admits a deterministic quasipolynomial-time approximation scheme (QPTAS) on every such class.<ref:2610.16025#pg6>.

Jane: The Core Theorem Theorem 2 states that if a hereditary graph class C has strongly edge-sublinear separators, then Max Weight Independent Set admits a QPTAS on C<ref:2610.16025#pg11>.

Tom: This means for any graph G in such a class and rational 0 < ε < 1, the algorithm deterministically computes an independent set I of G with w(I) ⩾ (1 − ε)αw(G)<ref:2pg2.

Title and authors: Tom: So we're looking at this paper today, "QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators." It’s tackling a really fundamental question about how fast we can approximate the maximum weight independent set problem on certain types of graphs.

Jane: That sounds complex because it deals with these graph classes that have what they call strongly edge-sublinear separators. What does that actually mean for us when we're trying to solve these optimization problems in practice?

Lu: Essentially, if a class of graphs has these separators, it means we can divide the graph into smaller pieces pretty efficiently, where the size of those pieces is controlled by some constant b less than one. That structure lets us build an approximation scheme that runs in quasipolynomial time.

Meng: Quasipolynomial time is good for theory, but when I'm shipping models to production, I need something faster than that for real-world graphs because the input size can be huge. What exactly does a quasipolynomial time approximation scheme mean in practical terms?

Tom: It means that for any graph G in this class and any rational number epsilon between zero and one, we can deterministically find an independent set whose weight is at least one minus epsilon times the maximum possible weight of the graph, and this happens in time that is quasipolynomial.

Jane: That’s a big improvement over just getting an approximation that runs in polynomial time because it gives us a guarantee on how close we can get to the optimum, depending on how small we want our error to be.

Lu: The paper shows this QPTAS works even without needing any separator or specific algorithm for finding those separators as part of the input. That’s a key piece of information because it means the approximation scheme itself is self-contained and doesn't rely on knowing the graph's internal structure beforehand.

Meng: I hate having to pre-process the graph structure just to get an approximation, so if we don't need a separator algorithm for this, that makes sense from a deployment standpoint. But what’s the actual complexity of this QPTAS?

Tom: The running time analysis shows that for fixed epsilon and some constant C, the time required is quasipolynomial. Specifically, the unweighted call takes time proportional to two to epsilon minus one log n times a constant C, which means it's manageable for reasonably large graphs if we can keep epsilon fixed.

Title and authors: Jane: That reliance on keeping epsilon fixed is something I need to think about when applying this in a real-world scenario where we might want very high precision. But the paper also talks about extending these ideas to slightly different settings, which is important.

Lu: The authors show that this QPTAS generalizes results for axis-parallel rectangles and polygons, or even packing connected subgraphs of a planar graph, which shows the generality of this approach across different geometric constraints.

Meng: Generalizing over shapes is cool, but what about the harder problems? Like if we move from independent sets to something trickier like minimum dominating set? Does this QPTAS still hold for those other types of problems?

Tom: The paper is careful with that, and it points out some limitations. They say that the QPTAS guarantee does not extend to all graph optimization problems. For instance, Minimum Dominating Set admits no QPTAS even on P5-free graphs unless NP equals QP.

Jane: That’s a significant caveat because it tells us this specific structural property—having strongly edge-sublinear separators—isn't sufficient to guarantee a QPTAS for every single optimization problem we care about. It only works for problems where the underlying complexity isn't too high relative to NP itself.

Lu: They also mention that Maximum Clique doesn't admit a QPTAS on 2K2-induced-minor-free graphs by using complementation from the fact that MIS on C4-free graphs is hard to approximate APXly <ref:2610.16025#pg2>. This shows how these structural constraints interact with different problems, and it highlights where the complexity gets harder.

Meng: So, what's the main problem they are trying to solve here? Is it just proving an approximation exists, or are they trying to prove something stronger about the structure of these graphs?

Tom: They are focusing on resolving some structural conjectures. Specifically, they positively resolve Conjecture one in much greater generality than before <ref:2610.16025#pg1>. That conjecture deals with planar graphs H and whether excluding H as an induced minor gives us a QPTAS for the maximum independent set problem.

Jane: Resolving that conjecture means that if we can find a graph H, then every graph avoiding that specific structure is guaranteed to have a QPTAS for MIS, which is much stronger than just saying *some* structural property implies *some* approximation.

Title and authors: Lu: The paper shows that their result generalizes the QPTAS for Maximum Weight Independent Set on hereditary classes with strongly sublinear separators measured in vertices, as well as the results from Dvořák and Lahiri on those same classes. This connects this work to a broader body of research on graph structure and approximation guarantees.

Meng: Connecting it to other related work is good context, but what does this mean for deployment? If we have a graph that fits this description, can we actually use these results to design better algorithms for our real systems?

Tom: The implication is that if your data structure or the constraints on your input graph fall into this class defined by strongly edge-sublinear separators, you don't have to settle for slower approximation methods; you get a deterministic quasipolynomial time scheme.

Jane: It means the choice of graph class for your problem becomes a much more powerful lever when designing algorithms because we can trade off approximation quality against the structural properties of the input data.

Lu: The paper points out that this result is different from another route proposed by Gartland and Lokshtanov, which they say cannot hold in general H-induced-minor-free classes. This suggests that proving that structural conjecture remains an open question for broader classes of graphs.

Meng: So, the main thing we need to watch is whether this result holds when we move beyond these specific graph constraints to more general families of inputs we encounter at scale.

Tom: Exactly, and the paper highlights that while this result is powerful, it's not a universal answer for all induced minor-free classes without further structural assumptions. This sets a clear boundary on what this technique can solve right now.

Jane: So, to wrap up, the paper "QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators" shows that if you have graphs with these separators, you get a deterministic quasipolynomial approximation scheme for the maximum weight independent set problem.

Lu: And that this result resolves Conjecture one in a much broader context than before, showing it holds for many different graph structures <ref:2610.16025#pg1>.

Meng: It’s useful because it gives us a concrete complexity bound, even if we can't use it everywhere right now. We need to keep building those tools that work on these specific classes.

Tom: Right, so the idea is that structural properties translate directly into guaranteed approximation performance in a controlled time frame for these specific graph structures.

The paper's summary: Tom: So, basically, this paper shows that if your graph class has those strongly edge-sublinear separators—meaning you can split it up really efficiently—then you can get a deterministic quasipolynomial time approximation for the maximum weight independent set problem.

Jane: That’s a big jump from just saying an approximation exists to getting one that's guaranteed to be good, and the time it takes grows in a manageable way for fixed error settings. It means if you can't afford exponential time, this gives you something concrete based on the graph structure itself.

Lu: What’s interesting is how they get around needing an actual separator algorithm as input. The whole scheme is built to find that separator using flow-cut theorems and some clever conditioning techniques, so the approximation comes from the relaxation and rounding steps rather than you having to manually find a cut first.

Meng: From a production standpoint, that’s actually pretty cool because it means we don't need a separate pre-processing step just to get an estimate of how big our solution is; the algorithm handles finding the structure needed for approximation on the fly.

Tom: Exactly. And they show this works for both unweighted and weighted versions of the independent set problem, which is important because in real data, we almost always deal with weights or costs associated with vertices.

Jane: But there are some guardrails, you know? The paper shows that while this holds for classes defined by these separators, it doesn't apply to every optimization problem out there. For instance, they point out that minimum dominating set doesn't get this same kind of QPTAS guarantee on graphs without even a P5-free constraint.

Lu: That’s the caveat; the structural property of having those separators isn't a universal magic key for every hard problem in graph theory. It shows where the limitations are.

Meng: So, if I'm working on a specific type of network data that fits these structural constraints, this gives me a solid complexity bound to work with, rather than just hoping some approximation algorithm will work on my noisy traffic models.

Tom: Right. And they also connect this finding back to some open questions about graph structure, specifically addressing conjecture one in a way that applies to much wider families of graphs than before.

Jane: It’s a step forward because it provides a deterministic bound where before there was just some theoretical possibility based on the class definition alone. But we still have those bigger questions about whether this holds for every induced minor-free family, which they admit is still open territory.

Lu: That's the bridge to future work; proving that conjecture in its full generality is what the next big structural challenge looks like here.

The paper's improvements: Tom: So, moving beyond just getting an approximation for one class of graphs, this paper actually suggests ways to make the scheme even more robust across different types of vertex weights in those same classes.

Jane: That’s interesting because we talked about how they handle weights by reducing it to the unweighted case first, and now they show that this reduction preserves that strong structural property for weighted versions too.

Lu: What they are doing is showing that even when you introduce vertex costs, say alpha and lambda variables for every set of vertices of size up to r plus two, you can still find the necessary structure to guide the approximation.

Meng: So, if we're dealing with real-world scenarios where nodes have different values—like in a routing problem where some paths are more expensive than others—this method still has that strong theoretical backbone.

Tom: Right. And they show that this preservation of strongly edge-sublinear separators even when weights are added means the approximation quality holds up, though the running time analysis gets a bit more complex with those weight variables.

Jane: It’s important because it means we don't lose that quasipolynomial time guarantee just because we start putting numbers on our vertices. The complexity just scales differently with those costs, but it stays within that manageable category.

Lu: They also touch on how this works with the reduction to minimum weight vertex cover, showing that if you can get a QPTAS for one problem in this class, you can likely get one for the other too by just flipping the logic.

Meng: That’s useful for deployment because it means we can apply similar structural techniques across different optimization goals without needing entirely separate approximation schemes tailored to each one.

Tom: It connects back to how we use these methods in practice, showing that the underlying graph structure dictates a certain level of performance guarantee regardless of the specific cost function you're optimizing for.

Jane: And they also hint at how this relates to other results, like those on string graphs or region intersection graphs, suggesting this structural approach is a common thread in approximation theory for many different graph families.

Lu: The paper doesn't just solve one problem; it establishes a more general framework where the structural separators are the key ingredient for achieving these strong approximation guarantees.

Conclusion: Tom: So we’ve looked at "QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators," and the main thing is that if your graph has those specific separators, you get a deterministic quasipolynomial time approximation for the maximum weight independent set problem.

Jane: That means for a huge class of graphs, we can get a result that's guaranteed to be within some epsilon of the true optimum in time that scales reasonably well with the size of your graph.

Lu: It’s pretty neat how they handle vertex weights too, showing that you can maintain this strong structural property even when you introduce costs on the vertices, which is a key part of real-world modeling.

Meng: For me, what matters is that it gives us a concrete complexity bound; I don't just want a theoretical guarantee about an approximation factor, I want to know how many operations it actually takes to run that scheme on my production data.

Tom: Exactly. And they did show how this connects back to other problems like minimum weight vertex cover, which is good because it means the structural insight has broader applicability in graph optimization.

Jane: It really solidifies the idea that graph structure isn't just about connectivity; it’s about how efficiently you can partition those structures and use that partitioning to control error.

Lu: The paper also points out that while this is powerful for certain classes, we still have open questions about extending these results to every possible induced minor-free family, which is where the next research push will likely go.

Meng: I’m still worried about deployment costs; if the constant C in that quasipolynomial time bound is huge, it might just be too slow for really massive inputs without more refinement.

Tom: That's a valid concern about the constant factor, Meng, but for now, this gives us a solid framework to build algorithms on when we know our input graph belongs to these strongly edge-sublinear separator classes.

Jane: So, it’s less about finding the absolute best approximation and more about knowing exactly what kind of error we can expect and in what time frame.

Lu: This paper really connects a lot of dots between structural decomposition theorems and approximation guarantees for NP-hard problems. It’s a good piece for understanding how to leverage graph theory to tame hard computation.

Tom: Yeah, it’s interesting because it shows that sometimes the way a graph is built—its fundamental structure—is more important than just the number of vertices itself when we're talking about approximation schemes.

Jane: For anyone looking at this, remember that if your data fits these separator constraints, you can aim for a deterministic bound in quasipolynomial time for problems like maximum weight independent set.

Meng: I'm going to keep an eye on how they refine those running times; we need complexity that actually runs fast on real traffic logs.

Lu: And the next big thing is definitely figuring out those deeper structural conjectures they mentioned, which will define the next wave of research in this area.

CNRS · ENS de Lyon, University Claude Bernard Lyon 1 · Department of Mathematics, Hanyang University

cs.DS, cs.DM, cs.LO, math.CO

Submitted: 2026-10-12

Updated: 2026-11-02

Comments: 23 pages

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: A hereditary graph class has strongly edge-sublinear separators if, for some constant 0 ⩽ b < 1, its m-edge graphs admit balanced separators of size O(mb) <ref:2610.16025.

Key concepts

Strongly Edge-Sublinear Separators
This property means that for a given constant $b < 1$, the graph class allows for balanced separators whose size is bounded by $O(mb)$ times the number of edges. This structural constraint is crucial because it enables the efficient recursive decomposition necessary for the approximation algorithm.
QPTAS
A Quasipolynomial Time Approximation Scheme means an algorithm that can find a solution within a factor $(1-\epsilon)$ of the optimal value in time that is quasipolynomial in the input size. This type of scheme is much faster than exponential time but slower than polynomial time, making it highly effective for hard optimization problems.
Max Weight Independent Set (MWIS)
MWIS is an optimization problem where you select a subset of vertices such that no two selected vertices are connected by an edge, and the sum of the weights of these selected vertices is maximized. The paper focuses on finding a near-optimal solution for this problem in specific graph classes.
Separator Finding Mechanism
The algorithm relies on finding a 'light balanced separator' when vertex costs are high. This search is achieved using flow-cut theorems and probabilistic methods, allowing the recursive process to break down the large graph into smaller, manageable pieces that can be solved independently.

Terminology

Summary

A hereditary graph class has strongly edge-sublinear separators if, for some constant 0 ⩽ b < 1, its m-edge graphs admit balanced separators of size O(mb) <ref:2610. p. 016025. We show that Max Weight Independent Set admits a deterministic quasipolynomial-time approximation scheme (QPTAS) on every such class. p. 0<ref:2610.16025#pg6>.

The Core Theorem

Theorem 2 states that if a hereditary graph class C has strongly edge-sublinear separators, then Max Weight Independent Set admits a QPTAS on C<ref:2610.16025#pg11>. This means for any graph G in such a class and rational 0 < ε < 1, the algorithm deterministically computes an independent set I of G with w(I) ⩾ (1 − ε)αw(G)<ref:2pg2. p. 1 The QPTAS is achieved without requiring any separator or algorithm for finding separators as part of the input<ref:2610. p. 116025#pg4>. Corollary 3 further extends this to H-induced-minor-free graphs, stating that Max Weight Independent Set admits a QPTAS on H-induced-minor-free graphs for every fixed graph H<ref:2610. p. 116025#pg6>.

Separator Finding Mechanism

The algorithm relies on finding a (δ, x)-light balanced separator when vertex costs x(V (G)) is sufficiently large and eG(x) is relatively small<ref:2610.16025#pg7>. Lemma 6 guarantees the existence of such a separator for an integer n ⩾ 2 and rational vector x with k:= x(V (G)) ⩾ p, where p = OC((δ−1)/log n)<ref:7pg7. p. 5 This is achieved by repeatedly applying Lemma 7, which uses a vertex-capacitated Leighton–Rao flow–cut theorem to find either the required balanced separator or an induced subgraph with a probability distribution on the ordered simple paths<ref:2610. p. 516025#pg9>.

Approximation via Relaxation and Rounding

The QPTAS is constructed using a linear relaxation and conditioning<ref:2610.16025#pg13>. This involves introducing variables yA for every set A ⊆ V (G) with A ⩽ r + 2, defining the polytope Rr(G, k)<ref:2610. p. 316025#pg15>. Lemma 12 provides a deterministic algorithm to find a vector x in [0, 1]V (G) satisfying x(V (G)) = k and eG(x) ≤ k 2/p<ref:2610. p. 516025#pg14>. This is done by conditioning on a small set of variables and using an entropy-decrease argument to bound the number of choices needed<ref:2610. p. 316025#pg15>.

Recursive Structure and Termination

The overall algorithm employs a recursive structure based on deleting a balanced separator<ref:2610.16025#pg6>. The procedure Solve(G) recursively calls itself on components C of G − S, where C ⩽ 2n'/3<ref:2610.16025#pg19>. The termination is guaranteed by Lemma 14, which shows that the size guarantee (24) holds for each recursive step<ref:2610. p. 316025#pg19>. This leads to a total running time of nO(rλ) = 2O(rλ 2) = 2OC(pλ 3)<ref:2610. p. 316025#pg20>.

Generalization to Weights

The QPTAS for Max Weight Independent Set (MWIS) is obtained by reducing it to the unweighted MIS problem<ref:2610.16025#pg7>. This reduction involves scaling and rounding the vertex weights and replacing each vertex by an independent set whose size is determined by its rounded weight<ref:2610. p. 316025#pg21>. Lemma 16 proves that this operation preserves strongly edge-sublinear separators, meaning the resulting class Cbl has strongly edge-sublinear separators<ref:2610. p. 416025#pg21>. This allows the unweighted QPTAS to yield a (1 − ε/2)-approximation for MWIS<ref:2610. p. 4 p. 4 p. 416025#pg21>. The running time analysis shows that the unweighted call takes time 2OC(ε−(8a−2)(log n+log ε−1)16a−1)<ref:2610. p. 516025#pg6>.

The Role of Structural Conjectures

The paper notes that the QPTAS obtained through Theorem 2 is different from the route proposed by [26, Conjecture 1.4.1], which cannot hold in general H-induced-minor-free classes<ref:2610. p. 116025#pg4>. This suggests that proving the structural induced grid minor conjecture remains an open question<ref:2610. p. 016025#pg2>. The authors also mention related work on strongly sublinear separators and PTASes for MWIS in efficiently fractionally treewidth-fragile classes<ref:2610. p. 216025#pg6> and string graphs<ref:2610. p. 016025#pg21>.

Hardness Results

The paper discusses the hardness of approximating MIS, noting that Håstad’s hardness result shows that for every fixed ε > 0, approximating MIS within a factor n(1-ε) on n-vertex graphs is NP-hard<ref:2610.16025#pg2>. Furthermore, it mentions that Minimum Dominating Set admits no QPTAS even on P5-free graphs unless NP ⊆ QP<ref:2610. p. 2 p. 216025#pg4>. Maximum Clique also lacks a QPTAS on 2K2(-induced-minor)-free graphs by complementation from the APXhardness of MIS on C4-free graphs<ref:2610. p. 2 p. 216025#pg4>.

Related Open Questions

Conjecture 4 poses that for every graph H, Max Independent Set admits a PTAS in H-induced-minor-free graphs<ref:2610.16025#pg4>. A natural strengthening is to ask Conjecture 4 for classes with strongly edge-sublinear separators, and a natural weakening is to ask the question for planar graphs H only<ref:2610. p. 216025#pg4>. Conjecture 4 is even open in the particular case of represented intersection graphs of axis-parallel rectangles<ref:2610. p. 216025#pg4>. The authors also note that the stronger conjecture posed by Bonnet and Hickingbotham—that MIS admits a PTAS when excluding any graph as an induced minor—remains open<ref:2610. p. 216025#pg4>.

Final Conclusion

Theorem 15 concludes that every graph class with strongly edge-sublinear separators admits a deterministic QPTAS for Max Independent Set<ref:2610.16025#pg19>. This result is significant because it unifies the QPTAS guarantee for all the classes listed in the second paragraph, including those admitting faster approximation schemes or exact algorithms, as each excludes a fixed graph as an induced minor<ref:2610. p. 1 p. 116025#pg4>. The running time analysis confirms that for fixed ε and C, (26) is quasipolynomial<ref:2610. p. 3 p. 316025#pg20>. The final result is that the unweighted call takes time 2(ε−1 log n)OC(1)<ref:2610. p. 5 p. 516025#pg6>.

Vertex Weights in MWIS

The reduction from MWIS to MIS preserves strongly edge-sublinear separators, possibly with a larger exponent<ref:2610.16025#pg21>. The resulting class Cbl has strongly edge-sublinear separators<ref:2610. p. 4 p. 416025#pg21>. This allows the unweighted QPTAS to yield a (1 − ε/2)-approximation for MWIS<ref:2610.16025#pg6>. The time complexity for the weighted call is 2OC(ε−(8a−2)(log n+log ε−1)16a−1)<ref:2610. p. 116025#pg6>.

The Proof Outline

The proof outline starts by treating unweighted MIS on an n-vertex graph G<ref:2610.16025#pg4>. The starting point is to delete a balanced separator, recursively find independent sets in the remaining components, and take their union<ref:2610. p. 216025#pg7>. The difficulty is controlling the loss relative to the optimum<ref:2610. p. 216025#pg7>. A linear relaxation is used to guide the separator choice, and recursive computations either produce the required approximation or yield additional valid constraints<ref:2610. p. 216025#pg6>.

Separator Algorithm Details

Section 3 provides a separator algorithm for vertex costs x ∈ [0, 1]V (G)<ref:2610.16025#pg4>. This involves finding a (δ, x)-light balanced separator when k:= x(V (G)) is sufficiently large and eG(x) is relatively small<ref:2610. p. 516025#pg7>. The proof uses a vertex-capacitated Leighton–Rao multicommodity flow–cut theorem to find the separator or an all-pairs flow in an induced subgraph<ref:7pg7. p. 5 Lemma 8 provides a probabilistic method to find either the separator or a distribution on the ordered simple paths<ref:2610. p. 716025#pg9>.

Feasibility and Search Strategy

Section 5 details the procedure Solve(G) which considers targets k = V (G), V (G) − 1,..., 1. The search strategy for targets k > p involves running the ellipsoid algorithm with queries handled by RoundOrCut<ref:2610. p. 316025#pg18>.

Running Time Analysis

The total running time is nO(rλ) = 2O(rλ 2) = 2OC(pλ 3)<ref:2610.16025#pg20>. This complexity is quasipolynomial for fixed ε and C<ref:2610. p. 016025#pg6>. The final result for the unweighted call is 2(ε−1 log n)OC(1)<ref:2610. p. 716025#pg6>. For the weighted call, it is 2OC(ε−(8a−2)(log n+log ε−1)16a-1)<ref:2610.16025#pg6>.

The reduction from MWIS to MIS preserves strongly edge-sublinear separators, possibly with a larger exponent<ref:2610.16025#pg21>. The resulting class Cbl has strongly edge-sublinear separators<ref:2610.16025#pg21>. This allows the unweighted QPTAS to yield a (1 − ε/2)-approximation for MWIS<ref:2610.16025#pg6>. The time complexity for the weighted call is 2OC(ε−(8a−2)(log n+log ε−1)16a-1)<ref:2610. p. 116025#pg6>.

The hardness of approximating MIS is established by Håstad’s result showing that for every fixed ε > 0, approximating MIS within a factor n(1-ε) on n-vertex graphs is NP-hard<ref:2610.16025#pg2>. Furthermore, it mentions that Minimum Dominating Set admits no QPTAS even on P5-free graphs unless NP ⊆ QP<ref:2610.16025#pg4>. Maximum Clique also lacks a QPTAS on 2K2(-induced-minor)-free graphs by complementation from the APXhardness of MIS on C4-free graphs<ref:2610.16025#pg4>.

Related Work

The paper cites related work covering classes with strongly sublinear separators, where MIS admits a PTAS [35] and MWIS a QPTAS [22, 23]<ref:2610.16025#pg6>. It also references results on string graphs having strongly edge-sublinear separators and region intersection graphs over Kt-minor-free hosts. p. 2

Final Summary

Theorem 15 states that every graph class with strongly edge-sublinear separators admits a deterministic QPTAS for Max Independent Set<ref:2610.16025#pg19>. This result is significant because it unifies the QPTAS guarantee for all the classes listed in the second paragraph, including those admitting faster approximation schemes or exact algorithms, as each excludes a fixed graph as an induced minor<ref:2610.16025#pg4>. The running time analysis confirms that for fixed ε and C, (26) is quasipolynomial<ref:2610.16025#pg20>. The final result is that the unweighted call takes time 2(ε−1 log n)OC(1)<ref:2610.16025#pg6>.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Deterministic Quasipolynomial Time Approximation Scheme for Max Weight Independent Set (MWIS) on graphs with strongly edge-sublinear separators. This allows AI systems to find a set of vertices whose total weight is at least one minus an epsilon fraction of the maximum possible weight in time exp(epsilon-1/log V(G)), which is quasipolynomial.

  2. Application of the algorithm to Max Weight Independent Set (MWIS) on graphs defined by excluding a fixed graph as an induced minor. This provides a deterministic QPTAS for MWIS on such classes, unifying approximation guarantees across various structural graph constraints.

  3. A reduction from MWIS to Minimum Weight Vertex Cover that preserves strongly edge-sublinear separators, allowing the determination of a deterministic QPTAS for Minimum Weight Vertex Cover on these graph classes.

Sources

Related papers