Cover Image

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bonnet, Édouard, Czyżewska, Jadwiga, Masařík, Tomáš, Pilipczuk, Marcin, Rzążewski, Paweł
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
by: Chudnovsky, Maria, et al.
Published: (2024)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
by: Lokshtanov, Daniel, et al.
Published: (2026)

A note on finding long directed cycles above the minimum degree bound in 2-connected digraphs
by: Czyżewska, Jadwiga, et al.
Published: (2025)

Max Weight Independent Set in sparse graphs with no long claws
by: Abrishami, Tara, et al.
Published: (2023)

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
by: Majewski, Konrad, et al.
Published: (2022)

Coarse Balanced Separators in Fat-Minor-Free Graphs
by: Bonnet, Édouard, et al.
Published: (2026)

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
by: Gartland, Peter, et al.
Published: (2023)

Separator Theorem for Minor-Free Graphs in Linear Time
by: Bonnet, Édouard, et al.
Published: (2025)

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
by: Bodlaender, Hans L., et al.
Published: (2025)

Dynamic data structures for twin-ordered matrices
by: Bosek, Bartłomiej, et al.
Published: (2026)

A tight quasi-polynomial bound for Global Label Min-Cut
by: Jaffke, Lars, et al.
Published: (2022)

A QPTAS for Facility Location on Unit Disk graphs
by: Friggstad, Zachary, et al.
Published: (2024)

Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
by: Hatzel, Meike, et al.
Published: (2022)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
by: Dvořák, Pavel, et al.
Published: (2022)

Faster diameter computation in graphs of bounded Euler genus
by: Kluk, Kacper, et al.
Published: (2025)

An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs
by: Bonnet, Édouard, et al.
Published: (2024)

A simpler QPTAS for scheduling jobs with precedence constraints
by: Das, Syamantak, et al.
Published: (2025)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
by: Bieliński, Paweł Rafał, et al.
Published: (2026)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

Kernelization for list $H$-coloring for graphs with small vertex cover
by: Piecyk, Marta, et al.
Published: (2025)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
by: Marx, Dániel, et al.
Published: (2026)

Parameterized Complexity of MinCSP over the Point Algebra
by: Osipov, George, et al.
Published: (2023)

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
by: Bonnet, Édouard, et al.
Published: (2023)

Bounding $\varepsilon$-scatter dimension via metric sparsity
by: Bourneuf, Romain, et al.
Published: (2024)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
by: Esmer, Barış Can, et al.
Published: (2022)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
by: Bonamy, Marthe, et al.
Published: (2022)

Tree-independence number VII. Excluding a star
by: Chudnovsky, Maria, et al.
Published: (2025)

Fair densest subgraph across multiple graphs
by: Arachchi, Chamalee Wickrama, et al.
Published: (2025)

On Integer Programs That Look Like Paths
by: Briański, Marcin, et al.
Published: (2025)

A customizable inexact subgraph matching algorithm for attributed graphs
by: Benko, Tatyana, et al.
Published: (2025)

Enumerating All Directed Spanning Trees in Optimal Time
by: Gawrychowski, Paweł, et al.
Published: (2026)

Compression with wildcards: All induced metric subgraphs
by: Wild, Marcel
Published: (2024)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
by: Enright, Jessica, et al.
Published: (2020)

Optimal Discretization is Fixed-parameter Tractable
by: Kratsch, Stefan, et al.
Published: (2020)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

Treedepth Inapproximability and Exponential ETH Lower Bound
by: Bonnet, Édouard, et al.
Published: (2025)

Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
by: Hušek, Radek, et al.
Published: (2020)

Simple and efficient four-cycle counting on sparse graphs
by: Burkhardt, Paul, et al.
Published: (2023)