User martin vatshelle - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T08:15:43Z http://mathoverflow.net/feeds/user/23539 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/10468/algorithms-on-graphs-of-bounded-degeneracy-arboricity/96327#96327 Answer by Martin Vatshelle for Algorithms on graphs of bounded degeneracy/arboricity Martin Vatshelle 2012-05-08T11:24:49Z 2012-05-08T11:24:49Z <p>There is one more approach to solve problems like Max Clique on graphs of bounded degeneracy. You can look at the complement graph of a graph \$G\$ (i.e. every edge is a non-edge and every non-edge is an edge). Solving Max Clique on \$G\$ is the same as solving Max Independent set on the complement.</p> <p>For the complement of bounded degeneracy graphs algorithms for many problems are known. E.g. Maximum Independent Set, Minimum Dominating Set, Perfect Code, k-Coloring, H- Cover, H-Homomorphism and H-Role Assignment are FPT parameterized by the degeneracy of the complement. See <a href="http://www.ii.uib.no/~martinv/Papers/Logarithmic_booleanwidth.pdf" rel="nofollow">http://www.ii.uib.no/~martinv/Papers/Logarithmic_booleanwidth.pdf</a> (submitted to journal)</p> <p>Some of these problems make sense to translate to the complement graph, such as:</p> <p>Can G be colored with \$k\$ colors -> can the complement be covered by \$k\$ cliques? (fixed \$k\$)</p> <p>Is there an \$3\$-regular induced subgraph of \$G\$ -> is there an induced \$k\$ regular subgraph of the complement on \$k+4\$ vertices?</p>