Parameterized complexity and kernelizability of max ones and exact ones problems

DOI10.1145/2858787MaRDI QIDQ5890961zbMATH OpenOpenAlexFDO

Authors Stefan Kratsch, Dániel Marx, Magnus Wahlström

Publication date 24 October 2016

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL http://eprints.sztaki.hu/9046/

zbMATH Keywords

complexity characterizationCSPFPT algorithmskernelization

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Parameterized complexity and kernelizability of Max Ones and Exact Ones problems
• Mathematical Foundations of Computer Science 2005
• Preprocessing of min ones problems: a dichotomy
• Solving MAX-\(r\)-SAT above a tight lower bound
• Parameterized constraint satisfaction problems: a survey

Cites work

• A kernelization algorithm for \(d\)-hitting set
• Complexity classifications of Boolean constraint satisfaction problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Incompressibility through Colors and IDs
• Intersection Theorems for Systems of Sets
• Kernel bounds for disjoint cycles and disjoint paths
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• On problems without polynomial kernels
• On the Hamming distance of constraint satisfaction problems.
• On the Structure of Polynomial Time Reducibility
• Parameterized complexity and kernelizability of Max Ones and Exact Ones problems
• Parameterized complexity of constraint satisfaction problems
• Preprocessing of min ones problems: a dichotomy
• Structure identification of Boolean relations and plain bases for co-clones
• The approximability of constraint satisfaction problems
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Vertex packings: Structural properties and algorithms

Cited in

(12)

• The parameterized complexity of maximality and minimality problems
• On the parameterized complexity of the Maximum Exposure Problem
• On the parameterized complexity of clustering problems for incomplete data
• Preprocessing of min ones problems: a dichotomy
• Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
• Optimal polynomial-time compression for Boolean Max CSP
• Parameterized complexity and kernelizability of Max Ones and Exact Ones problems
• Flow-augmentation. III: Complexity dichotomy for Boolean CSPS parameterized by the number of unsatisfied constraints
• Finding a cluster in incomplete data
• Optimal polynomial-time compression for Boolean Max CSP
• Boundaried kernelization
• The role of regularity in (hyper-)clique detection and implications for optimizing Boolean CSPs

This page was built for publication: Parameterized complexity and kernelizability of max ones and exact ones problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890961)