Imagen de Portada

Feedback Set Problems on Bounded-Degree (Planar) Graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bai, Tian, Cao, Yixin, Xiao, Mingyu
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
por: Liu, Brian, et al.
Publicado: (2024)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
por: Hörsch, Florian, et al.
Publicado: (2025)

Structural Parameterizations for Two Bounded Degree Problems Revisited
por: Lampis, Michael, et al.
Publicado: (2023)

On the Dynamics of Bounded-Degree Automata Networks
por: Aracena, Julio, et al.
Publicado: (2025)

On Factorization of Sparse Polynomials of Bounded Individual Degree
por: Chuyoon, Aminadav, et al.
Publicado: (2026)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
por: Tale, Prafullkumar
Publicado: (2025)

Property Testing in Bounded Degree Hypergraphs
por: Aaronson, Hugo, et al.
Publicado: (2025)

Quantum Property Testing for Bounded-Degree Directed Graphs
por: Peng, Pan, et al.
Publicado: (2026)

Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
por: MIT Hardness Group, et al.
Publicado: (2026)

Lower Bounds for Set-Multilinear Branching Programs
por: Chatterjee, Prerona, et al.
Publicado: (2023)

Lower Bounds from Succinct Hitting Sets
por: Chatterjee, Prerona, et al.
Publicado: (2023)

$m$-Eternal Dominating Set Problem on Subclasses of Chordal Graphs
por: Rai, Ashutosh, et al.
Publicado: (2026)

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
por: Cai, Jin-Yi, et al.
Publicado: (2026)

Dynamic Planar Graph Isomorphism is in DynFO
por: Datta, Samir, et al.
Publicado: (2026)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
por: MIT Hardness Group, et al.
Publicado: (2024)

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

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

Geometry Matters in Planar Storyplans
por: Dobler, Alexander, et al.
Publicado: (2025)

XALP-completeness of Parameterized Problems on Planar Graphs
por: Bodlaender, Hans L., et al.
Publicado: (2024)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
por: Herrmann, Anton, et al.
Publicado: (2025)

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

On the Complexity of Problems on Tree-structured Graphs
por: Bodlaender, Hans L., et al.
Publicado: (2022)

On the Exact Matching Problem in Dense Graphs
por: Maalouly, Nicolas El, et al.
Publicado: (2024)

Bounds on Eventually Universal Quantum Gate Sets
por: Karamchedu, Chaitanya, et al.
Publicado: (2025)

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
por: Dikstein, Yotam, et al.
Publicado: (2024)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
por: Komarath, Balagopal, et al.
Publicado: (2025)

Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
por: Xu, Jeff
Publicado: (2024)

Parameterized Max Min Feedback Vertex Set
por: Lampis, Michael, et al.
Publicado: (2023)

Approximate Degree Composition for Recursive Functions
por: Chakraborty, Sourav, et al.
Publicado: (2024)

Low-Degree Testing Over Grids
por: Amireddy, Prashanth, et al.
Publicado: (2023)

Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
por: Li, Shuangle, et al.
Publicado: (2024)

Recognizing 2-Layer and Outer $k$-Planar Graphs
por: Kobayashi, Yasuaki, et al.
Publicado: (2024)

Linear Planar 3-SAT and Its Applications in Planning
por: Desbois, Victorien, et al.
Publicado: (2025)

Hilbert Functions and Low-Degree Randomness Extractors
por: Golovnev, Alexander, et al.
Publicado: (2024)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
por: Chakraborty, Dipayan, et al.
Publicado: (2024)

The Parameterized Complexity of Geometric 1-Planarity
por: Firbas, Alexander
Publicado: (2026)

Low Degree Local Correction Over the Boolean Cube
por: Amireddy, Prashanth, et al.
Publicado: (2024)

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
por: Dutta, Pranjal, et al.
Publicado: (2024)

Tight Bounds for Quantum Phase Estimation and Related Problems
por: Mande, Nikhil S., et al.
Publicado: (2023)

Graph Homomorphism, Monotone Classes and Bounded Pathwidth
por: Eagling-Vose, Tala, et al.
Publicado: (2024)