An efficient algorithm for finding a two-pair, and its applications (Q1814097)

A two-pair in an undirected graph \(G\) is a pair of vertices \(u\) and \(v\) such that every chordless path between \(u\) and \(v\) has length 2. This note presents an efficient \(O(| V|| E|)\) algorithm to decide if a given graph \(G\) has a two-pair and output one if it exists. The authors discuss applications of this algorithm and mention that this implies new and faster algorithms for the following four problems on weakly triangulated graphs: minimum clique cover, maximum clique, maximum independent set, and minimum colouring. Each of these problems can be solved in time \(O(| V| T)\), where \(T\) is the time required to find a two-pair. Previous algorithms for these problems had complexity \(O(| V|^ 5)\). Hence this new algorithm implies an improvement by a factor \(| V|\). Applications to computational geometry are also discussed.