Copertina

A Note on the Complexity of Directed Clique

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Gutowski, Grzegorz, Rams, Mikołaj
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Combinatorics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

A Note on the Complexity of Defensive Domination
di: Chaplick, Steven, et al.
Pubblicazione: (2025)

Clique-Width: Harnessing the Power of Atoms
di: Dabrowski, Konrad K., et al.
Pubblicazione: (2020)

Monotone Circuit Complexity of Matching
di: Cavalar, Bruno, et al.
Pubblicazione: (2025)

Direct Product Primality Testing of Graphs is GI-hard
di: Calderoni, Luca, et al.
Pubblicazione: (2020)

Constant Degree Direct Product Testers with Small Soundness
di: Bafna, Mitali, et al.
Pubblicazione: (2024)

Communication Complexity of Disjointness under Product Distributions
di: Hunter, Zach, et al.
Pubblicazione: (2026)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
di: Li, Xin, et al.
Pubblicazione: (2023)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
di: Grüne, Christoph
Pubblicazione: (2022)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2025)

On the Nature and Complexity of an Impartial Two-Player Variant of the Game Lights-Out
di: Fiorini, Eugene, et al.
Pubblicazione: (2024)

Modelling Network Resilience: The Complexity of Some Graph Division Games
di: Gutowski, Grzegorz, et al.
Pubblicazione: (2026)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
di: Baril, Ambroise, et al.
Pubblicazione: (2024)

Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection
di: Chen, Yu-Zhen Janice, et al.
Pubblicazione: (2025)

Hunting for Directed 2-Spiders
di: Gutowski, Grzegorz, et al.
Pubblicazione: (2026)

Complexity Aspects of Homomorphisms of Ordered Graphs
di: Čertík, Michal, et al.
Pubblicazione: (2025)

Structural Origins of Cubic Complexity in Pebble Motion
di: Nakamigawa, Tomoki, et al.
Pubblicazione: (2025)

Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464
di: Minevich, Igor, et al.
Pubblicazione: (2024)

A near-optimal Quadratic Goldreich-Levin algorithm
di: Briët, Jop, et al.
Pubblicazione: (2025)

A combinatorial view of Holant problems on higher domains
di: Liu, Yin
Pubblicazione: (2024)

Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
di: Bok, Jan, et al.
Pubblicazione: (2021)

Complexity results for a cops and robber game on directed graphs
di: Ben-Ameur, Walid, et al.
Pubblicazione: (2024)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
di: Han, Zicheng, et al.
Pubblicazione: (2026)

A Subexponential Reduction from Product Partition to Subset Sum
di: Costandin, Marius
Pubblicazione: (2024)

A criterion for Andrásfai--Erdős--Sós type theorems and applications
di: Hou, Jianfeng, et al.
Pubblicazione: (2024)

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
di: Gan, Luyining, et al.
Pubblicazione: (2023)

Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2025)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
di: Hellmuth, Marc, et al.
Pubblicazione: (2023)

Computational Complexity of Swish
di: Horiyama, Takashi, et al.
Pubblicazione: (2026)

Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
di: Le, Hoang-Oanh, et al.
Pubblicazione: (2023)

Lions and Contamination: Trees and General Graphs
di: Kim, Dohoon, et al.
Pubblicazione: (2026)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
di: Grüne, Christoph, et al.
Pubblicazione: (2026)

Classification of Non-redundancy of Boolean Predicates of Arity 4
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)

King Chasing Problem in Chinese Chess is NP-hard
di: Li, Chao, et al.
Pubblicazione: (2026)

Between proper and square coloring of planar graphs, hardness and extremal graphs
di: Delépine, Thomas
Pubblicazione: (2026)

The Lens of Abelian Embeddings
di: Minzer, Dor
Pubblicazione: (2026)

Low-Degree Polynomials Are Good Extractors
di: Alrabiah, Omar, et al.
Pubblicazione: (2024)

Refuting Perfect Matchings in Spectral Expanders is Hard
di: Biswas, Ari, et al.
Pubblicazione: (2025)

Hunting a rabbit: complexity, approximability and some characterizations
di: Ben-Ameur, Walid, et al.
Pubblicazione: (2025)

On the Keevash-Knox-Mycroft Conjecture
di: Gan, Luyining, et al.
Pubblicazione: (2022)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
di: Borzechowski, Michaela, et al.
Pubblicazione: (2023)