On computing graph minor obstruction sets Export

@article{citeulike:566298, abstract = {The Graph Minor Theorem of Robertson and Seymour establishes nonconstructively that many natural graph properties are characterized by a finite set of forbidden substructures, the obstructions for the property. We prove several general theorems regarding the computation of obstruction sets from other information about a family of graphs. The methods can be adapted to other partial orders on graphs, such as the immersion and topological orders. The algorithms are in some cases practical and have been implemented. Two new technical ideas are introduced. The first is a method of computing a stopping signal for search spaces of increasing pathwidth. This allows obstruction sets to be computed without the necessity of a prior bound on maximum obstruction width. The second idea is that of a second order congruence for a graph property. This is an equivalence relation defined on finite sets of graphs that generalizes the recognizability congruence that is defined on single graphs. It is shown that the obstructions for a graph ideal can be effectively computed from an oracle for the canonical second-order congruence for the ideal and a membership oracle for the ideal. It is shown that the obstruction set for a union of minor ideals can be computed from the obstruction sets for and if there is at least one tree that does not belong to the intersection of and . As a corollary, it is shown that the set of intertwines of an arbitrary graph and a tree are effectively computable.}, author = {Cattell, Kevin and Dinneen, Michael J. and Downey, Rodney G. and Fellows, Michael R. and Langston, Michael A.}, citeulike-article-id = {566298}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0304-3975(97)00300-9}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6V1G-40M56FP-7/2/8762b0e6cb1efd307314fd6632fd12fb}, day = {28}, doi = {10.1016/S0304-3975(97)00300-9}, journal = {Theoretical Computer Science}, month = {February}, number = {1-2}, pages = {107--127}, posted-at = {2006-03-27 23:25:17}, priority = {0}, title = {On computing graph minor obstruction sets}, url = {http://dx.doi.org/10.1016/S0304-3975(97)00300-9}, volume = {233}, year = {2000} }

TY - JOUR ID - citeulike:566298 L3 - citeulike-article-id:566298 N2 - The Graph Minor Theorem of Robertson and Seymour establishes nonconstructively that many natural graph properties are characterized by a finite set of forbidden substructures, the obstructions for the property. We prove several general theorems regarding the computation of obstruction sets from other information about a family of graphs. The methods can be adapted to other partial orders on graphs, such as the immersion and topological orders. The algorithms are in some cases practical and have been implemented. Two new technical ideas are introduced. The first is a method of computing a stopping signal for search spaces of increasing pathwidth. This allows obstruction sets to be computed without the necessity of a prior bound on maximum obstruction width. The second idea is that of a second order congruence for a graph property. This is an equivalence relation defined on finite sets of graphs that generalizes the recognizability congruence that is defined on single graphs. It is shown that the obstructions for a graph ideal can be effectively computed from an oracle for the canonical second-order congruence for the ideal and a membership oracle for the ideal. It is shown that the obstruction set for a union of minor ideals can be computed from the obstruction sets for and if there is at least one tree that does not belong to the intersection of and . As a corollary, it is shown that the set of intertwines of an arbitrary graph and a tree are effectively computable. IS - 1-2 JF - Theoretical Computer Science EP - 127 TI - On computing graph minor obstruction sets VL - 233 SP - 107 AU - Cattell, Kevin AU - Dinneen, Michael AU - Downey, Rodney AU - Fellows, Michael AU - Langston, Michael PY - 2000/02/28/ UR - http://dx.doi.org/10.1016/S0304-3975(97)00300-9 ER -