Cover Image

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Liu, Brian, Sheffield, Nathan S., Westover, Alek
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

New Direct Sum Tests
by: Westover, Alek, et al.
Published: (2024)

When to Give Up on a Parallel Implementation
by: Sheffield, Nathan S., et al.
Published: (2024)

The Structure of In-Place Space-Bounded Computation
by: Cook, James, et al.
Published: (2025)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
by: Bai, Tian, et al.
Published: (2026)

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

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

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

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

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

Improved Bounds on the Space Complexity of Circuit Evaluation
by: Shalunov, Yakov
Published: (2025)

The Complexity of Logarithmic Space Bounded Counting Classes
by: Vijayaraghavan, T. C.
Published: (2025)

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

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
by: Wang, Chengu
Published: (2026)

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
by: Gajulapalli, Karthik, et al.
Published: (2025)

The Computational Complexity of Factored Graphs
by: Gupta, Shreya, et al.
Published: (2024)

ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
by: MIT Hardness Group, et al.
Published: (2024)

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

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

The Parameterized Complexity of Coloring Mixed Graphs
by: Lauerbach, Antonio, et al.
Published: (2026)

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

Hexasort -- The Complexity of Stacking Colors on Graphs
by: Klocker, Linus, et al.
Published: (2026)

On the Complexity of Vertex-Splitting Into an Interval Graph
by: Abu-Khzam, Faisal N., et al.
Published: (2026)

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

Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide
by: Nkosi, Thami
Published: (2025)

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

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

Multiple Planted Structures Below $\sqrt{n}$: An SoS Integrality Gap and an SQ Lower Bound
by: Mosievskiy, Matvey, et al.
Published: (2026)

The Complexity of Contracting Bipartite Graphs into Small Cycles
by: Krithika, R., et al.
Published: (2022)

On the Parameterized Complexity of Semitotal Domination on Graph Classes
by: Retschmeier, Lukas
Published: (2025)

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

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
by: Chen, Lijie, et al.
Published: (2025)

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

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
by: Bhargav, C. S., et al.
Published: (2025)

On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
by: Li, Xiaoyu, et al.
Published: (2025)

Complex to Rational Fast Matrix Multiplication
by: Moran, Yoav, et al.
Published: (2026)

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

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

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

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

One-way Communication Complexity of Minimum Vertex Cover in General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)