Cover Image

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lokshtanov, Daniel, Pilipczuk, Michał, 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

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
by: Bonnet, Édouard, et al.
Published: (2026)

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

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

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

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

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

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

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

Holey graphs: very large Betti numbers are testable
by: Szabó, Dániel, et al.
Published: (2024)

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

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)

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

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
by: Pilipczuk, Michał, et al.
Published: (2025)

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

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
by: Kumar, Mithilesh, et al.
Published: (2016)

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
by: Kumar, Mithilesh, et al.
Published: (2024)

Dynamic Detours
by: Dadush, Daniel, et al.
Published: (2026)

Sampling Unlabeled Chordal Graphs in Expected Polynomial Time
by: Hébert-Johnson, Úrsula, et al.
Published: (2025)

The problem of computing a $2$-T-connected spanning subgraph with minimum number of edges in directed graphs
by: Jaberi, Raed, et al.
Published: (2024)

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

Elementary first-order model checking for sparse graphs
by: Gajarský, Jakub, et al.
Published: (2024)

Parameterized dynamic data structure for Split Completion
by: Majewski, Konrad, et al.
Published: (2024)

Parameterized and approximation algorithms for coverings points with segments in the plane
by: Kowalska, Katarzyna, et al.
Published: (2024)

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

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

Minor Containment and Disjoint Paths in almost-linear time
by: Korhonen, Tuukka, et al.
Published: (2024)

Parameterized algorithms for block-structured integer programs with large entries
by: Cslovjecsek, Jana, et al.
Published: (2023)

Counting and Sampling Labeled Chordal Graphs in Polynomial Time
by: Hebert-Johnson, Ursula, et al.
Published: (2023)

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

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

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

Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time
by: Agrawal, Akanksha, et al.
Published: (2024)

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

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

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
by: Majewski, Konrad, et al.
Published: (2021)

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

Graph classes through the lens of logic
by: Pilipczuk, Michał
Published: (2025)

Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree framework
by: Sena, Francisco, et al.
Published: (2026)

Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
by: Lokshtanov, Daniel, et al.
Published: (2024)

Subexponential Parameterized Algorithms for Hitting Subgraphs
by: Lokshtanov, Daniel, et al.
Published: (2024)