On the descriptive complexity of color coding
From MaRDI portal
Abstract: Color coding is an algorithmic technique used in parameterized complexity theory to detect "small" structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color pattern. We transfer color coding to the world of descriptive complexity theory by characterizing -- purely in terms of the syntactic structure of describing formulas -- when the powerful second-order quantifiers representing a random coloring can be replaced by equivalent, simple first-order formulas. Building on this result, we identify syntactic properties of first-order quantifiers that can be eliminated from formulas describing parameterized problems. The result applies to many packing and embedding problems, but also to the long path problem. Together with a new result on the parameterized complexity of formula families involving only a fixed number of variables, we get that many problems lie in FPT just because of the way they are commonly described using logical formulas.
Recommendations
Cites work
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Color-coding
- Computing Hitting Set Kernels By AC^0-Circuits
- Describing parameterized complexity classes
- Fast parallel fixed-parameter algorithms via color coding
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 1161568 (Why is no real title available?)
- On the parallel parameterized complexity of the graph isomorphism problem
- Parallel Multivariate Meta-Theorems
- Parameterized circuit complexity of model-checking on sparse structures
- Parametrized complexity theory.
- Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
- The fine classification of conjunctive queries and parameterized logarithmic space
- Tree-depth, quantifier elimination, and quantifier rank
Cited in
(5)- Counting Colours in Compressed Strings
- Parameterized Parallel Computing and First-Order Logic
- Fast parallel fixed-parameter algorithms via color coding
- scientific article; zbMATH DE number 3238640 (Why is no real title available?)
- Algorithm engineering for color-coding with applications to signaling pathway detection
This page was built for publication: On the descriptive complexity of color coding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090457)
