|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
An algorithm, which for any easily recognizable input, A, finds either an easily recognizable B or an easily recognizable C, is sometimes called a "robust algorithm" -- to be distinguished from a non-robust algorithm, which, for any A without a B, finds a C. Either provides a proof of the "existentially polytime (EP) theorem": For any A, there exists a B or a C. In other words: For any A without a B, there is a C. In the paper "Existentially Polytime Theorems", 1989, Kathie Cameron and I advocated seeking a robust algorithm which, for any graph G, finds either a clique and colouring the same size or else finds an easily recognizable combinatorial obstruction to G being perfect. In view of the Strong Perfect Graph Theorem (SPGT), the obstruction might be specified to be an odd hole or odd antihole. In view of the precedents which I will describe here, and since what it would do is incomparable with Berge-graph recognition, such an algorithm might be simpler than an algorithm for recognizing whether or not a graph is a Berge graph (i.e., has no odd hole or odd antihole). For an input instance G to such an algorithm, the algorithm could end by giving a clique and colouring the same size even though G is non-Berge. Here are two examples of similar problems which have been solved: (a) A simple robust algorithm which, for any graph G, either finds an odd cycle with at most one chord (a defining obstruction to G being a Meyniel graph) or else finds a clique and colouring the same size. This algorithm is an improvement on the non-robust algorithms of Hoang and Hertz which, assuming a graph is a Meyniel graph, find a clique and colouring the same size. This algorithm is much simpler than the Burlet-Fonlupt decomposition algorithm for recognizing Meyniel graphs, which was motivated by an interest in efficiently colouring Meyniel graphs, and which is used by Hoang and Hertz to do that. (b) Conforti-Cornuejols-Rao give a complicated decomposition algorithm for recognizing whether or not a matrix is balanced. Correspondingly, in "EPT", 1989, there is a simple algorithm which, for any 0-1 matrix M, either finds, where x is the largest number of ones in any row, an x-colouring of the columns so that the 1's of any row are in different coloured columns, or else finds "an odd hole" in M (the defining obstruction to M being balanced). This introduced the "EP theorem - robust algorithm" paradigm which is followed in (a). It is related to the Conforti-Cornuejols-Rao treatment of balanced matrices in the same way that (a) is related to the Burlet-Fonlupt treatment of Meyniel graphs. Following the same paradigm we expect there to be a robust algorithm proving the SPGT, corresponding to the recent decomposition algorithms of Chudnovsky-Seymour and Cornuejols-Liu-Vuskovich for recognizing Berge graphs. We know the SPGT, an EP theorem: For any graph, there is either a clique and a colouring of the same size, or there is a odd hole or odd antihole (or both). And so, the remaining problem is to give a combinatorial polytime algorithm to find what the EP theorem asserts to exist. Hosts: Jørgen Bang-Jensen and Bjarne Toft
SDU HOME | IMADA HOME | Previous Page Last modified: August 15, 2003. Joan Boyar (joan@imada.sdu.dk) |