World's most popular travel blog for travel bloggers.

# Are there other interpretations of |G| than |V|, that is |V(G)|?

, ,
Problem Detail:

This may be a basic question, but I'm hoping someone can settle this nagging doubt I'm having. I'm reading up on FPT complexity using a book by Downey and Fellows. It has some introductory examples which detail complexity in terms of \$|G|\$, which seems to denote \$|V|\$ as mentioned here.

The sections containing those examples explicitly refer to \$|V(G)|\$ however, so I wonder if there might be other interpretations of \$|G|\$ that convey some nuance in terms of complexity I'm missing, or can I safely assume that it does in fact mean \$|V|\$?

I don't have the book, so I looked through the pages available on Google Scholar. It seems that they use \$|G|\$ to denote the size of a graph description that is \$|V(G)| + |E(G)|\$.

For example on page 24 they say that Vertex Cover is solvable in \$2^k|G|\$ time using bounded search tree method. In fact this method gives \$2^kk|V|\$ time for graphs with at most \$k(|V| - 1)\$ edges (it's easy to show that otherwise graph doesn't have Vertex Cover of size \$k\$). According to this "reverse engineering" \$|G|\$ corresponds to \$k|V|\$ that is essentially \$|V| + |E|\$.