Optimize Edge Deletion Analysis

[john-boyer-phd]

Edge deletion analysis (EDA) has proven to be a valuable tool for helping to find whether the null result of a subgraph homeomorphism search is valid. After the bug fix in #105 (a specific error identified as part of Epic #42), we are seeing no more invalid null results for all graphs generated by geng up to N=10 vertices. However, the way we are having to invoke the planarity executable for edge deletion analysis is resulting in hundreds of millions of process invocations, which is very time consuming and may even crash the Windows OS (apparently due to a small Windows OS memory leak for each process invocation).

Aside from the current EDA approach being very time consuming (a few days for N=10) and possibly crashing the OS, this problem means we are not at all able to successfully perform EDA for N=11. We selected the current approach because it was the least complex approach, and we wanted to see if we could get to N=11 without a more complex optimization. Now we have the reasons why an optimization is required to enable performing of EDA for all graphs of order N=11 generated by geng. We also believe that the optimization described below will reduce the EDA processing time to a few days for N=11. This is the largest order on which we can reasonably perform EDA, as EDA for N=12 would take close to a year of constant computation.

The key to being able to optimize our approach is that a change must be made to the core planarity executable so that it can be invoked far less often by the Python testing code that generates the test tables and performs EDA. The following are the steps:

• Make the planarity test-all-graphs feature output a trace of results for every graph. The test-all-graphs feature should receive an optional parameter of a second output file that, if given, will cause the named second output file to receive a 0 or 1 corresponding to an embeddable or non-embeddable result for each graph from the algorithm being tested. For subgraph homeomorphism search, an embeddable result (OK) means no homeomorphic subgraph was found, and a non-embeddable result means that a desired homeomorphic subgraph was found. The format for the second output file should be beneficial to input in Python, such as textual 0 and 1 values (i.e., ASCII 48 and 49), one per line to match the lines of the g6 file.
• Amend the first subgraph homeomorphism search step of EDA to use the test-all-graphs trace feature . Invoke planarity test all graphs with the trace feature on each whole file per edge size M for the given vertex order N. Then, use the trace results to generate a filtered file containing only those graphs for which an embeddable result (OK) was obtained, i.e., a null search result.
• Amend the second major step of EDA, which invokes planar or outerplanar embedding, to use the test-all-graphs trace feature on the null search result graphs from the preceding step. Then, use the second trace result to generate a second filtered file containing only those graphs from the first filtered file that also got a non-embeddable result in the second trace file. This eliminates graphs on which the subgraph homeomorphism search is surely correct in returning a null result because the graph is embeddable.
• For each graph G in the second filtered file, generate a single file F containing all subgraphs of G formed by deleting one edge of G. Then, invoke the planarity test-all-graphs trace feature on F to test all graphs in F with the original subgraph homeomorphism search algorithm from two steps previous. Last, check the trace result to see whether every result is a 0, i.e., a null result. Since every graph G in the second filtered file got a null result, every graph in F must also get a 0/OK/null result (Otherwise, the result on G would be an invalid OK/invalid null result).