Graph Algorithm Alternatives via Polynomial-Time Transformations: An Empirical Study Using Boolean Satisfiability and Integer Linear Programming

Deciding the satisfiability of Boolean expressions (SAT) and solving integer linear programming (ILP) are among the first combinatorial problems shown to be NP-hard. So too are the graph problems clique, independent set and vertex cover. The research community has produced significant algorithmic improvements for all of these. The three graph problems are so closely related that advances for one can often be applied to the others. SAT and ILP, on the other hand, are different enough from each other, and from graph problems in general, that advances for one may not readily translate into advances for the others. This study is aimed at determining whether highly efficient SAT and ILP algorithms can outperform fast, direct clique algorithms, and if so, under what conditions. Large-scale tests are conducted to compare highly efficient SAT and ILP solvers with a state-of-the-art maximum clique solver. Main results indicate that, in the vast majority of cases, a direct clique solver remains the algorithm of choice. Extreme cases, characterized by unusually high density or contrivance, were nevertheless identified for which SAT and ILP can outperform even the best current direct methods. Thus, a secondary finding suggests that foreknowledge of input graph structure has the potential to aid in proper algorithm selection.