New answers tagged reference-request
1
There is no formal answer for that question, as the notion of "embarrassingly parallel" is not a formal one; it is an informal and imprecise notion. I understand it to basically mean that if you do the trivial and obvious thing to parallelize (whatever that may be), it works, and there's no need for sophisticated solutions.
8
Maximum clique in graphs with degree $d$ can be reduced to $n$ instances of maximum clique in a graph with at most $d$ vertices: for each vertex, compute maximum clique in the induced subgraph of the neighborhood of the vertex.
Therefore, if we omit polynomial factors, the time complexity of maximum clique in graphs with degree at most $d$ is the same as ...
2
Your bound is correct, for exactly the reasons you give. It is also unimprovable in general. Suppose that each function is multiplication by a large constant, where both constants are subwords of some infinite incomprehensible sequence. If you could compress the composition, you would be able to compress at least one of the constants—a contradiction.
Edit: ...
2
Parameterized complexity
It might worth adding an answer since no one mentioned this area.
A comprehensible, well written quite recent book is
Parameterized Algorithms, M. Cygan et al., 2015
Another book is
Parameterized complexity, R. Downey and M. Fellows, 1999
Meanwhile the former presents a comprehensible text about most of the used methods and ...
16
The desired property holds for Independent Set (and probably other problems) in graphs of suitably bounded tree width.
Fix any constant $\epsilon>0$ and consider the Independent Set problem restricted to graphs of tree width at most $n \log_2(1+\epsilon) = \Theta(\epsilon n)$, where $n$ is the number of vertices. Call this problem $\Pi_\epsilon$.
Lemma ...
Top 50 recent answers are included
