Given a network modeled by a probabilistic graph G = (V,E) with bounds on the operation probabilities of edges and of pairs of edges, the second order two-terminal reliability problem is to find best possible bounds on the probability of an operating path between two given nodes s and t without assuming independence of failures. An exact column generation method is proposed to solve this problem as well as several variants of it. The auxiliary problem is to find an optimum (s - t)-connected (or (s - t)-disconnected) subgraph and is strongly NP-hard. This is also the case for the quadratic shortest path problem and for the quadratic minimum cut problem considered by Assous (1986) in heuristics for the second order two-terminal reliability problem. Tabu search heuristics and row generation integer programming algorithms are proposed for solving the auxiliary problem. Computational results are provided for examples from the literature.