Skip to main content

New answers tagged

0 votes

MSOL and Courcelle's theorem for maximum clique

Your MSO formula is correct. And it can be used in a proof for FPT-ness. You do not explicitly mention the parameter you want to use. I assume that it is the size $k$ of the presumed clique. Then, the ...
kne's user avatar
  • 2,253
3 votes
Accepted

MSOL and Courcelle's theorem for maximum clique

The formula as stated in the question has to modified before Courcelle's theorem can be applied to prove FPT w.r.t. tree width. Courcelle's theorem allows a cardinality predicate. i.e., you can ...
Sriram's user avatar
  • 402
0 votes

MSOL and Courcelle's theorem for maximum clique

Here, your formula size is $O(k^2)$, which will give you an upper bound on the existence of any FPT algorithms through Courcelle's theorem. See this reference (ยง4.2 on page 17) for more details.
codeR's user avatar
  • 1,435

Top 50 recent answers are included