Almost 2-SAT is Fixed-Parameter Tractable
| dc.creator | Razgon, Igor | |
| dc.creator | O'Sullivan, Barry | |
| dc.date | 2008-01-08 | |
| dc.date | 2008-04-18 | |
| dc.date.accessioned | 2026-07-07T09:33:05Z | |
| dc.date.available | 2026-07-07T09:33:05Z | |
| dc.description | We consider the following problem. Given a 2-CNF formula, is it possible to remove at most $k$ clauses so that the resulting 2-CNF formula is satisfiable? This problem is known to different research communities in Theoretical Computer Science under the names 'Almost 2-SAT', 'All-but-$k$ 2-SAT', '2-CNF deletion', '2-SAT deletion'. The status of fixed-parameter tractability of this problem is a long-standing open question in the area of Parameterized Complexity. We resolve this open question by proposing an algorithm which solves this problem in $O(15^k*k*m^3)$ and thus we show that this problem is fixed-parameter tractable. | |
| dc.description | This new version fixes the bug found by Somnath Sikdar in the proof of Claim 8. In the repaired version the modification of the Almost 2-SAT problem called 2-SLASAT is no longer needed and only the modification called 2-ASLASAT remains relevant. Hence the whole manuscript is updated so that the 2-SLASAT problem is not mentioned there anymore | |
| dc.identifier | https://arxiv.org/abs/0801.1300 | |
| dc.identifier | http://arxiv.org/abs/0801.1300 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/159011 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Geometry | |
| dc.subject | Logic in Computer Science | |
| dc.title | Almost 2-SAT is Fixed-Parameter Tractable | |
| dc.type | text |