Almost 2-SAT is fixed-parameter tractable
From MaRDI portal
Publication:1034100
DOI10.1016/j.jcss.2009.04.002zbMath1184.68477OpenAlexW1485150579MaRDI QIDQ1034100
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
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Linear kernels for separating a graph into components of bounded size, On Multiway Cut Parameterized above Lower Bounds, Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity, Linear Time Parameterized Algorithms for Subset Feedback Vertex Set, Parameterizing edge modification problems above lower bounds, A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter, Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, Backdoors to Satisfaction, What’s Next? Future Directions in Parameterized Complexity, Designing FPT Algorithms for Cut Problems Using Randomized Contractions, Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\), List-coloring -- parameterizing from triviality, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, Clique Cover and Graph Separation, Hitting Selected (Odd) Cycles, Unnamed Item, Disentangling the computational complexity of network untangling, Efficiently recognizing graphs with equal independence and annihilation numbers, A kernel of order \(2k-c\log k\) for vertex cover, On Weighted Graph Separation Problems and Flow Augmentation, Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search, The complexity of König subgraph problems and above-guarantee vertex cover, Confronting intractability via parameters, Multi-Budgeted Directed Cuts, List H-coloring a graph by removing few vertices, Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems, Alternative parameterizations of \textsc{Metric Dimension}, A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems, Faster graph bipartization, 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, Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs, Multi-budgeted directed cuts, Tractability of König edge deletion problems, Backdoors to tractable answer set programming, Unnamed Item, Unnamed Item, Backdoors to q-Horn, On group feedback vertex set parameterized by the size of the cutset
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
