I read that the problem of first-order model checking is believed to be not fixed parameter tractable on general graphs.
Why is this the case? Would be happy about some reference
Thanks in advance!
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
For a fixed $k$, existence of a $k$-clique can be represented as a first order model formula: $\exists u_1 \dots u_k, (\bigwedge_{i < j} u_i \neq u_j ) \land (\bigwedge_{i < j} (u_i,u_j) \in E)$.
Because $k$-CLIQUE problem is $\mathrm{W}[1]$-hard, if the first-order model checking problem is $\mathrm{FPT}$ then $\mathrm{W}[1] = \mathrm{FPT}$, contradicting the popular belief that states otherwise.
Of course, such a statement cannot be proved without hypotheses because it implies $\mathrm{P} \neq \mathrm{NP}$.
