<p>In the following paper the author's claim that almost all graphs can be expressed in first order logic with counting quantifiers and two variables.</p>
<p>I would like to know, is there any algorithm that infers a C<span class="math-container">$^2$</span> representation of a graph ?</p>
<p>If there is then what is its time complexity ?</p>
<p><a href="https://people.cs.umass.edu/%7Eimmerman/pub/canon.pdf" rel="nofollow noreferrer">https://people.cs.umass.edu/~immerman/pub/canon.pdf</a></p>

CC BY-SA 4.0
2020-11-10T19:19:44.473Z
I do not know the answer but maybe you can find it in the Otto's book on two-variable logic: https://doi.org/10.1017/9781316716878. Or maybe it's even here: https://projecteuclid.org/euclid.lnl/1235416501 or here: https://ieeexplore.ieee.org/document/523269
Bartosz Bednarczyk
CC BY-SA 4.0
2020-11-11T01:19:33.127Z
Doesn't vertex refinement, together with the proof that it's equivalent to C_2, do it? See section 1.8 of the paper you linked.
Joshua Grochow
<cc.complexity-theory><graph-theory><first-order-logic>
How and How fast can we infer a logical formula that expresses a given graph in C$^2$( logic with 2 vars and counting quantifiers)?
SagarM
# How and How fast can we infer a logical formula that expresses a given graph in C$^2$( logic with 2 vars and counting quantifiers)?

(Asked by: username_0 on 2020-11-10)

In the following paper the author's claim that almost all graphs can be expressed in first order logic with counting quantifiers and two variables.

I would like to know, is there any algorithm that infers a C$^2$ representation of a graph ?

If there is then what is its time complexity ?

[https://people.cs.umass.edu/~immerman/pub/canon.pdf](https://people.cs.umass.edu/%7Eimmerman/pub/canon.pdf)

**Tags:** cc.complexity-theory, graph-theory, first-order-logic

> **Comments:**
> **username_1**: I do not know the answer but maybe you can find it in the Otto's book on two-variable logic: https://doi.org/10.1017/9781316716878. Or maybe it's even here: https://projecteuclid.org/euclid.lnl/1235416501 or here: https://ieeexplore.ieee.org/document/523269  
> **username_2**: Doesn't vertex refinement, together with the proof that it's equivalent to C_2, do it? See section 1.8 of the paper you linked.  

---

## 0 answers

