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

Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström

Research output: Contribution to journal › Article › peer-review

13 Downloads (Pure)

Access to Document

@article{aafab9c3ce4d4f3db6de5a212ccc42c9,

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

author = "Kim, \{Eun Jung\} and Stefan Kratsch and Marcin Pilipczuk and Magnus Wahlstr{\"o}m",

year = "2025",

month = aug,

day = "13",

doi = "10.1137/23M1553698",

language = "English",

volume = "54",

pages = "1065--1137",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - Flow-augmentation III

T2 - Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints

AU - Kim, Eun Jung

AU - Kratsch, Stefan

AU - Pilipczuk, Marcin

AU - Wahlström, Magnus

PY - 2025/8/13

Y1 - 2025/8/13

U2 - 10.1137/23M1553698

DO - 10.1137/23M1553698

M3 - Article

SN - 0097-5397

VL - 54

SP - 1065

EP - 1137

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 4

ER -