Copertina

Self-referential instances of the dominating set problem are irreducible

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Zhou, Guangyan
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Data Structures and Algorithms Computational Complexity, Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Solution independence and self-referential instances
di: Zhou, Guangyan, et al.
Pubblicazione: (2026)

Constructing self-referential instances for the clique problem
di: Li, Jiaqi, et al.
Pubblicazione: (2026)

Further Explanations on "SAT Requires Exhaustive Search"
di: Dong, Qingxiu, et al.
Pubblicazione: (2024)

On the complexity of global Roman domination problem in graphs
di: Reddy, Sangam Balchandar, et al.
Pubblicazione: (2026)

An alignment problem
di: McDaniel, Emma L., et al.
Pubblicazione: (2024)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
di: Austrin, Per, et al.
Pubblicazione: (2024)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
di: Ducoffe, Guillaume
Pubblicazione: (2026)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
di: Yang, Yang
Pubblicazione: (2025)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
di: Yang, Yang
Pubblicazione: (2024)

A lossless a priori splitting rule for split-delivery routing problems
di: Jones, Bo, et al.
Pubblicazione: (2025)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
di: Dumas, Maël, et al.
Pubblicazione: (2022)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
di: Kluk, Kacper, et al.
Pubblicazione: (2025)

Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems
di: Bendotti, Pascale, et al.
Pubblicazione: (2024)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
di: Scheder, Dominik, et al.
Pubblicazione: (2025)

On the instance optimality of detecting collisions and subgraphs
di: Ben-Eliezer, Omri, et al.
Pubblicazione: (2023)

The tape reconfiguration problem and its consequences for dominating set reconfiguration
di: Bousquet, Nicolas, et al.
Pubblicazione: (2025)

More Asymmetry Yields Faster Matrix Multiplication
di: Alman, Josh, et al.
Pubblicazione: (2024)

Neighborhood-Aware Graph Labeling Problem
di: Shahverdikondori, Mohammad, et al.
Pubblicazione: (2026)

Lazy Kronecker Product
di: Song, Zhao
Pubblicazione: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
di: Nederlof, Jesper
Pubblicazione: (2026)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
di: Jiang, Cheng, et al.
Pubblicazione: (2026)

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

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
di: Asadi, Vahid R., et al.
Pubblicazione: (2026)

NP-Hardness and a PTAS for the Pinwheel Problem
di: Kleinberg, Robert, et al.
Pubblicazione: (2026)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
di: Bodlaender, Hans L., et al.
Pubblicazione: (2026)

Online Orthogonal Vectors Revisited
di: Gajulapalli, Karthik, et al.
Pubblicazione: (2026)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
di: Sharma, Amatya, et al.
Pubblicazione: (2026)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
di: Chen, Xi, et al.
Pubblicazione: (2026)

Sublinear-query relative-error testing of halfspaces
di: Chen, Xi, et al.
Pubblicazione: (2026)

Quadratic Speedup for Computing Contraction Fixed Points
di: Chen, Xi, et al.
Pubblicazione: (2026)

A Space-space Trade-off for Directed st-Connectivity
di: Edenhofer, Roman
Pubblicazione: (2026)

Asymptotic Rank Speedup Theorems, Revisited
di: Alman, Josh, et al.
Pubblicazione: (2026)

Bilateral Treewidth for QBF: Where Strategies and Resolution Meet
di: Ganian, Robert, et al.
Pubblicazione: (2026)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
di: Khanna, Sanjeev, et al.
Pubblicazione: (2026)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
di: Singer, Noah G., et al.
Pubblicazione: (2026)

Kernelization Bounds for Constrained Coloring
di: Haviv, Ishay
Pubblicazione: (2026)

On the Advantage of Adaptivity for Sampling with Cell Probes
di: Byramji, Farzan, et al.
Pubblicazione: (2026)

Clustering with Locally Bounded Ignorance
di: Garvardt, Jaroslav, et al.
Pubblicazione: (2026)

Submodular Maximization under Supermodular Constraint: Greedy Guarantees
di: Srivastava, Ajitesh, et al.
Pubblicazione: (2026)

Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers
di: Oka, Keigo, et al.
Pubblicazione: (2026)