5
$\begingroup$

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$?

$\endgroup$
5
  • $\begingroup$ What is tw(G) ? $\endgroup$ Jan 12, 2011 at 9:52
  • $\begingroup$ @Sylvain: maybe the treewidth of a graph? $\endgroup$ Jan 12, 2011 at 10:02
  • $\begingroup$ @Sylvain: Sorry, I added the explanation. $\endgroup$
    – Regularity
    Jan 12, 2011 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, 2011 at 12:00
  • 1
    $\begingroup$ I guess it is the number of good assignments. $\endgroup$ Jan 12, 2011 at 12:05

1 Answer 1

10
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ I am not sure, if I remember well this paper is about bounded tree width structure, which is not the case here. $\endgroup$ Jan 12, 2011 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$ Jan 12, 2011 at 15:00
  • $\begingroup$ So, my mistake then, sorry. $\endgroup$ Jan 12, 2011 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.