[Mar 13, 2014] 

As correctly pointed out by Stefan Funke, Andre Nusser and 
Sabine Storandt, our proof of Theorem 1 holds for undirected 
graphs only (which our paper focuses on). They have given 
a proof that the corresponding VC dimension for any directed 
graph should be 3.  

The original SIGMOD11 paper contained an unthoughtful remark
in Section 4.1 that our proof for undirected graphs was 
extendible to directed graphs. This remark has been removed 
in the version here.