Almost 2-SAT is fixed-parameter tractable
From MaRDI portal
Publication:1034100
DOI10.1016/j.jcss.2009.04.002zbMath1184.68477MaRDI 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
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