2026-07-23T08:35:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24369 2025-12-12T15:01:06Z ddc:004 open_access

Maximum And- vs. Even-SAT Nakajima, Tamio-Vesa Živný, Stanislav approximation promise constraint satisfaction max and max even max cut max dicut max acyclic A multiset of literals, called a clause, is strongly satisfied by an assignment if no literal evaluates to false. Finding an assignment that maximises the number of strongly satisfied clauses is NP-hard. We present a simple algorithm that finds, given a multiset of clauses that admits an assignment that strongly satisfies ρ of the clauses, an assignment in which at least ρ of the clauses are weakly satisfied, in the sense that an even number of literals evaluate to false. In particular, this implies an efficient algorithm for finding an undirected cut of value ρ in a graph G given that a directed cut of value ρ in G is promised to exist. A similar argument also gives an efficient algorithm for finding an acyclic subgraph of G with ρ edges under the same promise. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tamio-Vesa Nakajima and Stanislav Živný 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.3 urn:nbn:de:0030-drops-243696 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.3 eng https://creativecommons.org/licenses/by/4.0/legalcode