Input: Graph $G$ and formula $\varphi_1(\vec x),\varphi_2(\vec x)$

Parameter: $tw(G)+|\varphi_1|+|\varphi_2|$

Problem: Decide if $|\varphi_1(G)|=|\varphi_2(G)|$

where $tw(G)$ is the treewidth of $G$ and $\varphi(G):=\{\vec a|(G,\vec a)\models\varphi\}$.

What is the parametrized complexity of this problem for $\varphi_i\in FO$ or $\varphi_i\in MSO$?

  • $\begingroup$ What is tw(G) ? $\endgroup$ – Sylvain Peyronnet Jan 12 '11 at 9:52
  • $\begingroup$ @Sylvain: maybe the treewidth of a graph? $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 12 '11 at 10:02
  • $\begingroup$ @Sylvain: Sorry, I added the explanation. $\endgroup$ – Regularity Jan 12 '11 at 10:34
  • 1
    $\begingroup$ Pardon my ignorance, but what is the meaning of "the absolute value of a formula applied to a graph" : $\vert \varphi_{1}(G)\vert$ ? $\endgroup$ – gphilip Jan 12 '11 at 12:00
  • 1
    $\begingroup$ I guess it is the number of good assignments. $\endgroup$ – Mathieu Chapelle Jan 12 '11 at 12:05

This problem is $\mathsf{FPT}$ for $\varphi_i \in MSO$ (and hence also for $\varphi_i \in FO$).

More precisely, Courcelle et al. prove in [1] the following:

Theorem [1, Thm. 32]
Let $\mathcal{C}$ be a class of graphs which is of bounded tree-width $k$.
Then any $MSO_2$ definable counting problem, given by $\varphi$, can be solved in time $c_k \cdot \mathcal{O}(|V| + |E|)$, where $c_k$ is a constant which depends only on $\varphi$ and $k$.

$MSO_2$ stands for monadic second-order logic where the universe is $V \cup E$ (vertices and edges), and we are given a binary relation $R(v,e)$ for the incidence between a vertex $u$ and an edge $e$. This is a quite natural representation of graphs, sufficiently powerful to e.g. define Hamiltonicity.

[1]: B.Courcelle, J.A.Makowsky, U.Rotics. On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics 108, pp. 23-52 (2001)

  • $\begingroup$ I am not sure, if I remember well this paper is about bounded tree width structure, which is not the case here. $\endgroup$ – Sylvain Peyronnet Jan 12 '11 at 12:26
  • $\begingroup$ In this paper (and usually in parameterized complexity), "bounded measure" means "as parameter". I should precise that Theorem 32 in this paper precisely states that any $MSO_2$ formula $\varphi$ can be decided on an input graph $G$ in $\mathcal{O}\big(f(tw(G),\varphi) \cdot |G|\big)$ time. $\endgroup$ – Mathieu Chapelle Jan 12 '11 at 15:00
  • $\begingroup$ So, my mistake then, sorry. $\endgroup$ – Sylvain Peyronnet Jan 12 '11 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.