Preprint and software

    Sam Buss, Vijay Ganesh and Albert Oliveras
    A Linear Time Algorithm for Two-Vertex Bottlenecks
    Preprint and associatedi software. March 2024

    Download preprint version.

    Download zipped software archive.

This TowVertexBottlenecks osftware was developed for finding all Dual Implication Pointss in a CDCL conflict graph.

Abstract: We describe a linear time algorithm that determines all "two-vertex bottlenecks" in a directed graph. This gives all pairs of vertices that disconnect two given nodes $s$ and~$t$ in a directed graph. There may be quadratically many two-vertex bottlenecks, but a compressed representation allows them to all be determined in linear time. Applications include the determination of Dual Implication Points (DIPs) in the CDCL solver conflict graph, as discussed in Buss, Chung, Ganesh, and Oliveras [preprint, 2024]. The algorithm for finding all DIPs is an algorithm for Menger's Theorem on a directed graph that not only verifies that two given vertices are not 3-connected but also finds all possible separating vertex pairs.