An implementation of an algorithm described in [1] for counting the number of times that one graph appears as a subgraph of the other.
The algorithm is expected to be efficient when the first graph is small, and the second graph has only a small proportion of high-degree vertices.
More formally, the algorithm is an FPT algorithm for labelled subgraph counting in classes of host graphs from the class of graphs with almost-bounded degree parameterised by the order of the pattern graph.
The algorithm takes two inputs: a file containing the pattern graph data, and a file containing the host graph data.
The file for each graph must be a .txt file written in LAD format where the first line states the number of vertices in the graph, and the next $n$ lines state, for each vertex, its number of successor nodes, followed by the list of its successor nodes.
For example, the complete graph $K_4$ would be written as
4
3 1 2 3
3 0 2 3
3 0 1 3
3 0 1 2
The result is printed to the screen and contains the following information:
Datetime: the date/time on which the code was run
Graph Statistics: includes the following properties of each of the host and the pattern graph:
Number of high-degree vertices: the value of this parameter is optimised within the code
Maximum degree of remaining vertices: the maximum degree of the host graph after the 'removal' of the high-degree vertices
Run status: PASS if the number of copies of the graph is $>0$, FAIL if there are no copies, and INTERRUPTED if the program fails to complete for whatever reason
Count the number of labelled copies of the first graph in the second (null if interrupted)
Total runtime in milliseconds
Parameter value optimisation runtime in milliseconds time taken to determine best values of parameters
Algorithm runtime in milliseconds time for the algorithm to run after the parameter values have been optimised
[1] Ryan, Jessica Laurette, Parameterised Algorithms for Counting Subgraphs, Matchings, and Monochromatic Partitions, PhD Thesis, 2023