Almost 2-SAT is fixed-parameter tractable

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

Barry O'Sullivan, Igor Razgon

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

Unnamed Item, Multi-Budgeted Directed Cuts, New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition, Rank Vertex Cover as a Natural Problem for Algebraic Compression, Hitting Selected (Odd) Cycles, Unnamed Item, Unnamed Item, A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems, Disentangling the computational complexity of network untangling, Efficiently recognizing graphs with equal independence and annihilation numbers, On Weighted Graph Separation Problems and Flow Augmentation, 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, Multi-budgeted directed cuts, Parameterizing edge modification problems above lower bounds, A kernel of order \(2k-c\log k\) for vertex cover, Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity, List-coloring -- parameterizing from triviality, Alternative parameterizations of \textsc{Metric Dimension}, Faster graph bipartization, Tractability of König edge deletion problems, 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