2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ In general, you can define every size measure you want. Whether it's interesting is another question. If the number is irrelevant for the performance of your algorithms, use |V|; if it's not, you better use |V| + |E| or, outside of complexity theory, express your costs in both quantities. $\endgroup$ – Raphael Jul 31 '15 at 11:26
  • $\begingroup$ In some obscure cases, it might refer to bit complexity also. In that case, $|G| \approx n \log n + m \log m$. $\endgroup$ – HdM Jul 31 '15 at 12:19
  • $\begingroup$ Usually $|G|$ denotes the order of the graph, namely the number of vertices. See for instance Diestel. $\endgroup$ – Pål GD Jul 31 '15 at 12:47
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is exactly the kind of nuance I worried I might be missing, thanks for taking the trouble of looking it up and for the reverse-engineering, much appreciated. $\endgroup$ – Fasermaler Jul 31 '15 at 13:13

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.