Almost 2-SAT is fixed-parameter tractable

DOI10.1016/j.jcss.2009.04.002zbMath1184.68477MaRDI QIDQ1034100

Igor Razgon, Barry O'Sullivan

Publication date: 10 November 2009

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2009.04.002

zbMATH Keywords

satisfiability problems; fixed-parameter algorithms; separation problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

Hitting Selected (Odd) Cycles, A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems, Backdoors to q-Horn, On group feedback vertex set parameterized by the size of the cutset, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search, Confronting intractability via parameters, List H-coloring a graph by removing few vertices, The complexity of König subgraph problems and above-guarantee vertex cover, Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems, Parameterizing edge modification problems above lower bounds, A kernel of order \(2k-c\log k\) for vertex cover, Backdoors to tractable answer set programming, Linear kernels for separating a graph into components of bounded size, Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\), On Multiway Cut Parameterized above Lower Bounds, Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, Backdoors to Satisfaction, What’s Next? Future Directions in Parameterized Complexity, Clique Cover and Graph Separation, A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter, Designing FPT Algorithms for Cut Problems Using Randomized Contractions, Linear Time Parameterized Algorithms for Subset Feedback Vertex Set, Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Parameterized graph separation problems
• Parameterized complexity of finding subgraphs with hereditary properties.
• Improved exact algorithms for MAX-SAT
• Improved Algorithms for the Feedback Vertex Set Problems
• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
• Parameterized Approximability of the Disjoint Cycle Problem
• Experimental and Efficient Algorithms
• Algorithms - ESA 2003
• SOFSEM 2006: Theory and Practice of Computer Science