Almost 2-SAT is Fixed-Parameter Tractable

Details Almost 2-SAT is Fixed-Parameter Tractable Almost 2-SAT is Fixed-Parameter Tractable

2008-01-08

arxiv.org/abs/0801.1300v4

Computer Science

Data Structures and Algorithms

This new version fixes the bug found by Somnath Sikdar in the proof of Claim 8. In the repaired version the modification of th

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Almost 2-SAT is Fixed-Parameter Tractable does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Almost 2-SAT is Fixed-Parameter Tractable, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Almost 2-SAT is Fixed-Parameter Tractable will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-421763