Buchumschlag

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Greilhuber, Jakob, Sharma, Roohani
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2025)

Residue Domination in Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2024)

The Primal Pathwidth SETH
von: Lampis, Michael
Veröffentlicht: (2024)

First Order Logic on Pathwidth Revisited Again
von: Lampis, Michael
Veröffentlicht: (2022)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
von: Tale, Prafullkumar
Veröffentlicht: (2025)

Kernelization Bounds for Constrained Coloring
von: Haviv, Ishay
Veröffentlicht: (2026)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
von: Foucaud, Florent, et al.
Veröffentlicht: (2023)

The Structure of In-Place Space-Bounded Computation
von: Cook, James, et al.
Veröffentlicht: (2025)

Balanced Substructures in Bicolored Graphs
von: Ardra, P. S., et al.
Veröffentlicht: (2024)

Structural Parameterizations for Two Bounded Degree Problems Revisited
von: Lampis, Michael, et al.
Veröffentlicht: (2023)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
von: Sharma, Amatya, et al.
Veröffentlicht: (2026)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
von: Beisegel, Jesse, et al.
Veröffentlicht: (2025)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
von: Krithika, R., et al.
Veröffentlicht: (2023)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
von: Lokshtanov, Daniel, et al.
Veröffentlicht: (2024)

Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
von: Holtgrefe, Niels, et al.
Veröffentlicht: (2026)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
von: Kothari, Pravesh K., et al.
Veröffentlicht: (2025)

Computational Explorations of Total Variation Distance
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2024)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
von: Foucaud, Florent, et al.
Veröffentlicht: (2024)

Exact Algorithms for Distance to Unique Vertex Cover
von: Fioravantes, Foivos, et al.
Veröffentlicht: (2025)

A Space-space Trade-off for Directed st-Connectivity
von: Edenhofer, Roman
Veröffentlicht: (2026)

Clustering with Locally Bounded Ignorance
von: Garvardt, Jaroslav, et al.
Veröffentlicht: (2026)

Lower Bounds for Convexity Testing
von: Chen, Xi, et al.
Veröffentlicht: (2024)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
von: Kenig, Batya
Veröffentlicht: (2025)

Improved Space Bounds for Subset Sum
von: Belova, Tatiana, et al.
Veröffentlicht: (2024)

Sensitivity Lower Bounds for Approximaiton Algorithms
von: Fleming, Noah, et al.
Veröffentlicht: (2024)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
von: Focke, Jacob, et al.
Veröffentlicht: (2022)

Treedepth Inapproximability and Exponential ETH Lower Bound
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
von: Putterman, Aaron, et al.
Veröffentlicht: (2026)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
von: Wang, Yichuan
Veröffentlicht: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
von: Chou, Chi-Ning, et al.
Veröffentlicht: (2021)

On the complexity and approximability of Bounded access Lempel Ziv coding
von: Cicalese, Ferdinando, et al.
Veröffentlicht: (2024)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
von: Li, Qian, et al.
Veröffentlicht: (2025)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
von: Gu, Yuzhou, et al.
Veröffentlicht: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
von: Grossman, Ofer, et al.
Veröffentlicht: (2023)