Cover Image

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kim, Eun Jung, Kratsch, Stefan, Pilipczuk, Marcin, Wahlström, Magnus
Format:	Preprint
Published:	2022
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
by: Jonsson, Peter, et al.
Published: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

Parameterized Complexity of MinCSP over the Point Algebra
by: Osipov, George, et al.
Published: (2023)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
by: Sharma, Amatya, et al.
Published: (2026)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
by: Jansen, Bart M. P., et al.
Published: (2026)

A faster polynomial-space algorithm for Hamiltonian cycle parameterized by treedepth
by: Kratsch, Stefan
Published: (2026)

Efficient parameterized approximation
by: Kratsch, Stefan, et al.
Published: (2025)

A tight quasi-polynomial bound for Global Label Min-Cut
by: Jaffke, Lars, et al.
Published: (2022)

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

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
by: Fei, Yumou, et al.
Published: (2025)

Sketching approximations and LP approximations for finite CSPs are related
by: Singer, Noah G., et al.
Published: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

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

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
by: Fei, Yumou
Published: (2025)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
by: Singer, Noah G.
Published: (2025)

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

On girth and the parameterized complexity of token sliding and token jumping
by: Bartier, Valentin, et al.
Published: (2020)

Bandwidth Parameterized by Cluster Vertex Deletion Number
by: Gima, Tatsuya, et al.
Published: (2023)

Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
by: Hatzel, Meike, et al.
Published: (2022)

Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
by: Hu, Bingbing, et al.
Published: (2024)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
by: Brakensiek, Joshua, et al.
Published: (2026)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Representative set statements for delta-matroids and the Mader delta-matroid
by: Wahlström, Magnus
Published: (2023)

On the parameterized complexity of Broadcast Independence and Broadcast Packing
by: Dumont, Joanne, et al.
Published: (2026)

Learning-Augmented Algorithms for Boolean Satisfiability
by: Attias, Idan, et al.
Published: (2025)

Parameterized Complexity of Vehicle Routing
by: Döring, Michelle, et al.
Published: (2025)

The Complexity of Finding and Counting Subtournaments
by: Döring, Simon, et al.
Published: (2025)

On the Parameterized Complexity of Odd Coloring
by: Bhyravarapu, Sriram, et al.
Published: (2025)

On the Complexity of Signed Roman Domination
by: Reddy, Sangam Balchandar
Published: (2025)

On the Space Complexity of Online Convolution
by: Andersson, Joel Daniel, et al.
Published: (2025)

Computational Complexity in Property Testing
by: Pinto Jr., Renato Ferreira, et al.
Published: (2025)

Hardness of Learning Boolean Functions from Label Proportions
by: Guruswami, Venkatesan, et al.
Published: (2024)

Ideal Membership Problem for Boolean Minority and Dual Discriminator
by: Bharathi, Arpitha P., et al.
Published: (2024)

The Fine-Grained Complexity of Episode Matching
by: Bille, Philip, et al.
Published: (2021)

On the Parameterized Complexity of Min-Sum-Radii
by: Kumar, Pankaj, et al.
Published: (2026)

The Complexity of Counting Small Sub-Hypergraphs
by: Bressan, Marco, et al.
Published: (2025)

The Complexity of Maximal Common Subsequence Enumeration
by: Buzzega, Giovanni, et al.
Published: (2025)

A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
by: Bojikian, Narek, et al.
Published: (2023)