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

###### Asked By : Fasermaler

###### Answered By : avsmal

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

Question Source : http://cs.stackexchange.com/questions/44899

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback