On miniaturized problems in parameterized complexity theory

We introduce a general notion of miniaturization of a problem that comprises the different miniaturizations of concrete problems considered so far. We develop parts of the basic theory of miniaturizations. Using the appropriate logical formalism, we show that the miniaturization of a definable problem in W [ t ] lies in W [ t ], too. In particular, the miniaturization of the dominating set problem is in W [ 2 ]. Furthermore, we investigate the relation between f ( k ) · n o ( k ) time and subexponential time algorithms for the dominating set problem and for the clique problem.

Authors

• Yijia Chen
• Jörg Flum

Keywords

• Parameterized complexity
• Subexponential algorithms
• Fagin-definability