Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability

DOI10.1016/j.artint.2009.06.005zbMath1194.68208OpenAlexW2105786826MaRDI QIDQ840834

Yong Gao

Publication date: 14 September 2009

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2009.06.005

zbMATH Keywords

phase transitionsdata reductionprobabilistic analysisfixed parameter tractabilityrandom instancesresolution complexityweighted CNF satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (2)

Parameterized Bounded-Depth Frege Is Not Optimal ⋮ Parameterized Complexity of DPLL Search Procedures

Uses Software

• BG-WalkSAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of constraint satisfaction problems
• Statistical regimes across constrainedness regions
• Backdoor sets for DLL subsolvers
• Experiments on data reduction for optimal domination in networks
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Tight lower bounds for certain parameterized NP-hard problems
• The scaling window of the 2-SAT transition
• The Efficiency of Resolution and Davis--Putnam Procedures
• Exact Algorithms for Cluster Editing: Evaluation and Experiments
• Tradeoffs in the Complexity of Backdoor Detection
• Models and thresholds for random constraint satisfaction problems
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Solving random satisfiable 3CNF formulas in expected polynomial time
• General percolation and random graphs
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Short proofs are narrow—resolution made simple
• Coloring bipartite hypergraphs
• Paths in graphs
• Data Reduction, Exact, and Heuristic Algorithms for Clique Cover
• On the solution-space geometry of random constraint satisfaction problems
• Frozen development in graph coloring

This page was built for publication: Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability