This C++11 project provides efficient data structures for small graphs (n ≤ 64). A graph with n vertices is represented as a adjacency matrix of n machine words, which can be efficiently manipulated by bit twiddling. A few examples are provided.
In extremal.cc, the maximum number of a subgraph such as P3 that a graph
on n vertices can have as induced subgraph is determined. Here, a
P3 is a path with 3 vertices. It turns out that the
numbers are
0, 0, 1, 4, 9, 18, 30, 48, 70, 100, 135
The file p5editing.cc examines a conjecture about a data reduction
rule for the P5-Free Editing problem, that is, the
problem of adding and deleting a minimum number of edges in a graph
to make it P5-free, where P5 is the
induced subgraph of a path with 5 vertices. The conjecture is that
vertices that are not in any P5 can be omitted, since
it is not meaningful to delete them. The program finds a
counterexample with 8 vertices.
In ssge-approx.cc, the approximation factor of an approximation
algorithm for Sparse Split Graph Editing is examined. The worst case
found is factor 2.5 for a graph with 6 vertices, and graphs with
more vertices seem to have better factors. The best proven bound for
this algorithm is a factor of 3 (F. Hüffner, C. Komusiewicz, and
A. Nichterlein: Editing graphs into few cliques: complexity,
approximation, and kernelization schemes. WADS
2015.)
The default maximum number of vertices is 32. To change this, edit
wordsize.h and run make clean.
Licensed under the Apache License, Version 2.0; see LICENSE.
Non-legally binding summary:
Enumeration of graphs up to isomorphism is currently handled by nauty, which comes with the same license.