Buchumschlag

Analogy between List Coloring Problems and the Interval $k$-$(γ,μ)$-choosability property: theoretical aspects of complexity

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Gama, Simone Ingrid Monteiro, Rodrigues, Rosiane de Freitas
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Trading Determinism for Time: The k-Reach Problem
von: Bhadra, Ronak, et al.
Veröffentlicht: (2024)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
von: Yung, Kingsley
Veröffentlicht: (2024)

Complexity Thresholds for the Constrained Colored Token Swapping Problem
von: Bilò, Davide, et al.
Veröffentlicht: (2026)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
von: Dalirrooyfard, Mina, et al.
Veröffentlicht: (2025)

On the Complexity of Vertex-Splitting Into an Interval Graph
von: Abu-Khzam, Faisal N., et al.
Veröffentlicht: (2026)

Quantum k-SAT Related Hypergraph Problems
von: Kremer, Simon-Luca, et al.
Veröffentlicht: (2025)

$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem
von: Yi, Yongming
Veröffentlicht: (2026)

On connections between k-coloring and Euclidean k-means
von: Aman, Enver, et al.
Veröffentlicht: (2024)

Relations between monotone complexity measures based on decision tree complexity
von: Byramji, Farzan, et al.
Veröffentlicht: (2024)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
von: Çivril, Ali
Veröffentlicht: (2021)

Towards a complexity-theoretic dichotomy for TQFT invariants
von: Bridges, Nicolas, et al.
Veröffentlicht: (2025)

High Rate Efficient Local List Decoding from HDX
von: Dikstein, Yotam, et al.
Veröffentlicht: (2026)

On Saxe's theorems about the complexity of the Distance Geometry Problem
von: Kupperschmitt, Maël, et al.
Veröffentlicht: (2025)

The complexity of computing in continuous time: space complexity is precision
von: Blanc, Manon, et al.
Veröffentlicht: (2024)

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
von: Yao, Penghui, et al.
Veröffentlicht: (2023)

On Approximability of Satisfiable k-CSPs: V
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

Optimal Union Probability Interval Is NP-Hard
von: Kaski, Petteri, et al.
Veröffentlicht: (2026)

Network Satisfaction Problems Solved by k-Consistency
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2023)

On the complexity of Multipacking
von: Das, Sandip, et al.
Veröffentlicht: (2026)

Near Optimal Hardness of Approximating $k$-CSP
von: Minzer, Dor, et al.
Veröffentlicht: (2025)

Width Hierarchy for k-OBDD of Small Width
von: Khadiev, Kamil
Veröffentlicht: (2015)

The complexity of convexity number and percolation time in the cycle convexity
von: Lima, Carlos V. G. C., et al.
Veröffentlicht: (2024)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
von: S., Karthik C., et al.
Veröffentlicht: (2021)

On Extremal Properties of k-CNF: Capturing Threshold Functions
von: Gurumukhani, Mohit, et al.
Veröffentlicht: (2024)

Constant-Cost Communication is not Reducible to k-Hamming Distance
von: Fang, Yuting, et al.
Veröffentlicht: (2024)

On the Hardness of Approximation of the Fair k-Center Problem
von: Thejaswi, Suhas
Veröffentlicht: (2026)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
von: Mu, Ta-Yu, et al.
Veröffentlicht: (2024)

Instance complexity of Boolean functions
von: Liu, Alison Hsiang-Hsuan, et al.
Veröffentlicht: (2023)

Unambiguous parity-query complexity
von: Gavinsky, Dmytro
Veröffentlicht: (2024)

The Parameterized Complexity of Coloring Mixed Graphs
von: Lauerbach, Antonio, et al.
Veröffentlicht: (2026)

Hexasort -- The Complexity of Stacking Colors on Graphs
von: Klocker, Linus, et al.
Veröffentlicht: (2026)

NP-Completeness of Neighborhood Balanced Colorings
von: Asaeedi, Saeed
Veröffentlicht: (2024)

Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version)
von: Antonelli, Melissa, et al.
Veröffentlicht: (2026)

The complexity of strong conflict-free vertex-connection $k$-colorability
von: Hsieh, Sun-Yuan, et al.
Veröffentlicht: (2024)

On complexity of restricted fragments of Decision DNNF
von: Calí, Andrea, et al.
Veröffentlicht: (2025)

Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$
von: Çivril, Ali
Veröffentlicht: (2021)

Computational aspects of the trace norm contraction coefficient
von: Delsol, Idris, et al.
Veröffentlicht: (2025)

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
von: Błasiok, Jarosław, et al.
Veröffentlicht: (2026)

Asymmetric Number Partitioning with Splitting and Interval Targets
von: Bismuth, Samuel, et al.
Veröffentlicht: (2022)