New answers tagged fixed-parameter-tractable
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 ...
Top 50 recent answers are included
