Copertina

A Dichotomy for Maximum PCSPs on Graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Nakajima, Tamio-Vesa, Živný, Stanislav
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Computational Complexity Discrete Mathematics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On the complexity of symmetric vs. functional PCSPs
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2022)

Maximum $k$- vs. $\ell$-colourings of graphs
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2023)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
di: Ciardo, Lorenzo, et al.
Pubblicazione: (2023)

An approximation algorithm for Maximum DiCut vs. Cut
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2024)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
di: Bedert, Benjamin, et al.
Pubblicazione: (2025)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
di: Shao, Shuai, et al.
Pubblicazione: (2023)

The periodic structure of local consistency
di: Ciardo, Lorenzo, et al.
Pubblicazione: (2024)

A logarithmic approximation of linearly ordered colourings
di: Håstad, Johan, et al.
Pubblicazione: (2024)

Semidefinite programming and linear equations vs. homomorphism problems
di: Ciardo, Lorenzo, et al.
Pubblicazione: (2023)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
di: Lucke, Felicia, et al.
Pubblicazione: (2023)

Maximum And- vs. Even-SAT
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2024)

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

Hierarchies of Minion Tests for PCSPs through Tensors
di: Ciardo, Lorenzo, et al.
Pubblicazione: (2022)

Additive Sparsification of CSPs
di: Pelleg, Eden, et al.
Pubblicazione: (2021)

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
di: Hamm, Thekla, et al.
Pubblicazione: (2026)

The Complexity of Transitively Orienting Temporal Graphs
di: Mertzios, George B., et al.
Pubblicazione: (2021)

Randomized Communication and Implicit Graph Representations
di: Harms, Nathaniel, et al.
Pubblicazione: (2021)

On Stable Cutsets in General and Minimum Degree Constrained Graphs
di: Vroon, Mats, et al.
Pubblicazione: (2025)

Combinatorial Parameterized Algorithms for Chemical Descriptors based on Molecular Graph Sparsity
di: Conrado, Giovanna K., et al.
Pubblicazione: (2023)

The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
di: Dreier, Jan, et al.
Pubblicazione: (2026)

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
di: Kratochvíl, Jan, et al.
Pubblicazione: (2020)

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2025)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
di: Lucke, Felicia, et al.
Pubblicazione: (2024)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
di: Beisegel, Jesse, et al.
Pubblicazione: (2025)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths
di: Beisegel, Jesse, et al.
Pubblicazione: (2025)

Finding Minimum Distance Preservers: A Parameterized Study
di: Simonov, Kirill, et al.
Pubblicazione: (2026)

A note on approximating the average degree of bounded arboricity graphs
di: Eden, Talya, et al.
Pubblicazione: (2026)

Graph Search Trees and the Intermezzo Problem
di: Beisegel, Jesse, et al.
Pubblicazione: (2024)

Microscopic Structure of Random 3-SAT: A Discrete Geometric Approach to Phase Transitions and Algorithmic Complexity
di: Zhan, Yongjian
Pubblicazione: (2026)

The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
di: Beisegel, Jesse, et al.
Pubblicazione: (2024)

Graph Classes Closed under Self-intersection
di: Dabrowski, Konrad K., et al.
Pubblicazione: (2025)

Steiner Forest for $H$-Subgraph-Free Graphs
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2026)

Computing Subset Vertex Covers in $H$-Free Graphs
di: Brettell, Nick, et al.
Pubblicazione: (2023)

Finding $d$-Cuts in Probe $H$-Free Graphs
di: Dabrowski, Konrad K., et al.
Pubblicazione: (2025)

Solving Problems on Generalized Convex Graphs via Mim-Width
di: Bonomo-Braberman, Flavia, et al.
Pubblicazione: (2020)

Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
di: Ahn, Jungho, et al.
Pubblicazione: (2026)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers
di: Beisegel, Jesse, et al.
Pubblicazione: (2025)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
di: Hirahara, Shuichi, et al.
Pubblicazione: (2024)

Counting Locally Optimal Tours in the TSP
di: Manthey, Bodo, et al.
Pubblicazione: (2024)

Relative-error monotonicity testing
di: Chen, Xi, et al.
Pubblicazione: (2024)