Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. (English) Zbl 1073.68063
Summary: Many problems that are intractable for general graphs allow polynomial-time solutions for structured classes of graphs, such as planar graphs and graphs of bounded treewidth. We demonstrate structural properties of larger classes of graphs and show how to exploit the properties to obtain algorithms. The classes considered are those formed by excluding as a minor a graph that can be embedded in the plane with at most one crossing. We show that graphs in these classes can be decomposed into planar graphs and graphs of small treewidth; we use the decomposition to show that all such graphs have locally bounded treewidth (all subgraphs of a certain form are graphs of bounded treewidth). Finally, we make use of the structural properties to derive polynomial-time algorithms for approximating treewidth within a factor of 1.5 and branchwidth within a factor of 2.25 as well as polynomial-time approximation schemes for both minimization and maximization problems and fixed-parameter algorithms for problems such as vertex cover, edge-dominating set, feedback vertex set, and others.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W25 | Approximation algorithms |
References:
| [1] | Alber, J.; Bodlaender, H. L.; Fernau, H.; Kloks, T.; Niedermeier, R., Fixed parameter algorithms for dominating set and related problems on planar graphs, Algorithmica, 33, 461-493 (2002) · Zbl 1016.68055 |
| [2] | J. Alber, H. Fan, M.R. Fellows, H. Fernau, R. Niedermeier, F.A. Rosamond, U. Stege, Refined search tree technique for dominating set on planar graphs, in: Proceedings of 26th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 2136, Springer, Berlin, 2001, pp. 111-122.; J. Alber, H. Fan, M.R. Fellows, H. Fernau, R. Niedermeier, F.A. Rosamond, U. Stege, Refined search tree technique for dominating set on planar graphs, in: Proceedings of 26th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 2136, Springer, Berlin, 2001, pp. 111-122. · Zbl 0999.68158 |
| [3] | J. Alber, H. Fernau, R. Niedermeier, Parameterized complexity: exponential speed-up for planar graph problems, in: Proceedings of the 28th Annual International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 2076, Springer, Berlin, 2001, pp. 261-272.; J. Alber, H. Fernau, R. Niedermeier, Parameterized complexity: exponential speed-up for planar graph problems, in: Proceedings of the 28th Annual International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 2076, Springer, Berlin, 2001, pp. 261-272. · Zbl 0987.68040 |
| [4] | J. Alber, R. Niedermeier, Improved tree decomposition-based algorithms for domination-like problems, in: Proceedings of LATIN 2002, Fifth Latin American Symposium on Theoretical Informatics, Lecture Notes in Computer Science, Vol. 2286, Springer, Berlin, 2002, pp. 613-628.; J. Alber, R. Niedermeier, Improved tree decomposition-based algorithms for domination-like problems, in: Proceedings of LATIN 2002, Fifth Latin American Symposium on Theoretical Informatics, Lecture Notes in Computer Science, Vol. 2286, Springer, Berlin, 2002, pp. 613-628. · Zbl 1059.68598 |
| [5] | N. Alon, P. Seymour, R. Thomas, A separator theorem for graphs with excluded minor and its applications, in: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 293-299.; N. Alon, P. Seymour, R. Thomas, A separator theorem for graphs with excluded minor and its applications, in: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 293-299. |
| [6] | E. Amir, Efficient approximation for triangulation of minimum treewidth, in: Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann, Los Altos, CA, 2001, pp. 7-15.; E. Amir, Efficient approximation for triangulation of minimum treewidth, in: Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann, Los Altos, CA, 2001, pp. 7-15. |
| [7] | Arnborg, S.; Corneil, D. G.; Proskurowski, A., Complexity of finding embeddings in a \(k\)-tree, SIAM J. Algebraic Discrete Methods, 8, 2, 277-284 (1987) · Zbl 0611.05022 |
| [8] | Arnborg, S.; Proskurowski, A., Characterization and recognition of partial 3-trees, SIAM J. Algebraic Discrete Methods, 7, 2, 305-314 (1986) · Zbl 0597.05027 |
| [9] | Asano, T., An approach to the subgraph homeomorphism problem, Theoret. Comput. Sci., 38, 2-3, 249-267 (1985) · Zbl 0572.68052 |
| [10] | Baker, B. S., Approximation algorithms for NP-complete problems on planar graphs, J. Assoc. Comput. Mach., 41, 1, 153-180 (1994) · Zbl 0807.68067 |
| [11] | H.L. Bodlaender, Dynamic programming algorithms on graphs with bounded treewidth, in: Proceedings of the 15th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 317, 1988, pp. 105-118.; H.L. Bodlaender, Dynamic programming algorithms on graphs with bounded treewidth, in: Proceedings of the 15th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 317, 1988, pp. 105-118. · Zbl 0649.68039 |
| [12] | Bodlaender, H. L., A tourist guide through treewidth, Acta Cybernet., 11, 1-23 (1993) · Zbl 0804.68101 |
| [13] | Bodlaender, H. L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 6, 1305-1317 (1996) · Zbl 0864.68074 |
| [14] | H.L. Bodlaender, Treewidth: algorithmic techniques and results, in: Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, 1997, pp. 29-36.; H.L. Bodlaender, Treewidth: algorithmic techniques and results, in: Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, 1997, pp. 29-36. · Zbl 0941.05057 |
| [15] | Bodlaender, H. L., A partial \(k\)-arboretum of graphs of bounded treewidth, Theoret. Comput. Sci., 209, 1-45 (1998) · Zbl 0912.68148 |
| [16] | Bodlaender, H. L.; Gilbert, J. R.; Hafsteinsson, H.; Kloks, T., Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, J. Algorithms, 18, 2, 238-255 (1995) · Zbl 0818.68118 |
| [17] | Bodlaender, H. L.; Kloks, T.; Kratsch, D., Treewidth and pathwidth of permutation graphs, SIAM J. Discrete Math., 8, 4, 606-616 (1995) · Zbl 0840.05087 |
| [18] | Bodlaender, H. L.; Kloks, T., Efficient and constructive algorithms for the pathwidth and treewidth of graphs, J. Algorithms, 21, 2, 358-402 (1996) · Zbl 0861.68036 |
| [19] | Bodlaender, H. L.; Möhring, R. H., The pathwidth and treewidth of cographs, SIAM J. Discrete Math., 6, 2, 181-188 (1993) · Zbl 0773.05091 |
| [20] | Bodlaender, H. L.; Thilikos, D. M., Treewidth for graphs with small chordality, Discrete Appl. Math., 79, 1-3, 45-61 (1997) · Zbl 0895.68113 |
| [21] | Bodlaender, H. L.; van Leeuwen, J.; Tan, R.; Thilikos, D., On interval routing schemes and treewidth, Inform. and Comput., 139, 1, 92-109 (1997) · Zbl 0892.68069 |
| [22] | Bondy, J. A.; Murty, U. S.R, Graph Theory with Applications (1976), American Elsevier Publishing Co., Inc: American Elsevier Publishing Co., Inc New York · Zbl 1134.05001 |
| [23] | V. Bouchitté, D. Kratsch, H. Müller, I. Todinca, On treewidth approximations, in: Proceedings of the First Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Electronic Notes in Discrete Mathematics, Vol. 8, 2001.; V. Bouchitté, D. Kratsch, H. Müller, I. Todinca, On treewidth approximations, in: Proceedings of the First Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Electronic Notes in Discrete Mathematics, Vol. 8, 2001. · Zbl 1412.05055 |
| [24] | Bouchitté, V.; Todinca, I., Treewidth and minimum fill-in: grouping the minimal separators, SIAM J. Comput., 31, 1, 212-232 (2001) · Zbl 0987.05085 |
| [25] | Broersma, H. J.; Dahlhaus, E.; Kloks, T., A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs, Discrete Appl. Math., 99, 1-3, 367-400 (2000) · Zbl 0940.05064 |
| [26] | Bui, T. N.; Peck, A., Partitioning planar graphs, SIAM J. Comput., 21, 2, 203-215 (1992) · Zbl 0759.05089 |
| [27] | M.-S. Chang, T. Kloks, C.-M. Lee, Maximum clique transversals, in: Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, 2001, pp. 300-310.; M.-S. Chang, T. Kloks, C.-M. Lee, Maximum clique transversals, in: Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, 2001, pp. 300-310. · Zbl 1042.68619 |
| [28] | Chen, J.; Kanj, I. A.; Jia, W., Vertex coverfurther observations and further improvements, J. Algorithms, 41, 2, 280-301 (2001) · Zbl 1017.68087 |
| [29] | Chen, Z.-Z, Efficient approximation schemes for maximization problems on \(K_{3,3}\)-free or \(K_5\)-free graphs, J. Algorithms, 26, 1, 166-187 (1998) · Zbl 0891.68070 |
| [30] | Chiba, N.; Nishizeki, T.; Saito, N., An approximation algorithm for the maximum independent set problem on planar graphs, SIAM J. Comput., 11, 4, 663-675 (1982) · Zbl 0492.68051 |
| [31] | E.D. Demaine, M. Hajiaghayi, D.M. Thilikos, Exponential speedup of fixed parameter algorithms on \(K_{3,3}K_5\); E.D. Demaine, M. Hajiaghayi, D.M. Thilikos, Exponential speedup of fixed parameter algorithms on \(K_{3,3}K_5\) · Zbl 1020.05063 |
| [32] | Dı́az, J.; Serna, M. J.; Torán, J., Parallel approximation schemes for problems on planar graphs, Acta Inform., 33, 4, 387-408 (1996) · Zbl 0858.68062 |
| [33] | Diestel, R., Simplicial decompositions of graphs: a survey of applications, Discrete Math., 75, 1-3, 121-144 (1989) · Zbl 0669.05053 |
| [34] | Diestel, R., Decomposing infinite graphs, Discrete Math., 95, 69-89 (1991) · Zbl 0759.05069 |
| [35] | Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer: Springer New York · Zbl 0961.68533 |
| [36] | J. Ellis, H. Fan, M.R. Fellows, The dominating set problem is fixed parameter tractable for graphs of bounded genus, in: Proceedings of the Eighth Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 2368, Springer, Berlin, 2002, pp. 180-189.; J. Ellis, H. Fan, M.R. Fellows, The dominating set problem is fixed parameter tractable for graphs of bounded genus, in: Proceedings of the Eighth Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 2368, Springer, Berlin, 2002, pp. 180-189. · Zbl 1078.68639 |
| [37] | Eppstein, D., Subgraph isomorphism in planar graphs and related problems, J. Graph Algorithms Appl., 3, 3, 1-27 (1999) · Zbl 0949.05055 |
| [38] | Eppstein, D., Diameter and treewidth in minor-closed graph families, Algorithmica, 27, 3-4, 275-291 (2000) · Zbl 0963.05128 |
| [39] | Frick, M.; Grohe, M., Deciding first-order properties of locally tree-decomposable structures, J. ACM, 48, 6, 1184-1206 (2001) · Zbl 1323.03014 |
| [40] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), W. H. Freeman and Co: W. H. Freeman and Co San Francisco, CA · Zbl 0411.68039 |
| [41] | M. Grohe, Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 2001, to appear.; M. Grohe, Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 2001, to appear. |
| [42] | Habib, M.; Möhring, R. H., Treewidth of cocomparability graphs and a new order-theoretic parameter, Order, 11, 47-60 (1994) · Zbl 0811.06001 |
| [43] | Hopcroft, J. E.; Tarjan, R. E., Dividing a graph into triconnected components, SIAM J. Comput., 2, 135-158 (1973) · Zbl 0281.05111 |
| [44] | Kanevsky, A.; Ramachandran, V., Improved algorithms for graph four-connectivity, J. Comput. System Sci., 42, 3, 288-306 (1991) · Zbl 0731.68086 |
| [45] | A. Kézdy, P. McGuinness, Sequential and parallel algorithms to find a \(K_5\); A. Kézdy, P. McGuinness, Sequential and parallel algorithms to find a \(K_5\) · Zbl 0822.05025 |
| [46] | Kloks, T., Treewidth of circle graphs, Internat. J. Found. Comput. Sci., 7, 2, 111-120 (1996) · Zbl 0852.68069 |
| [47] | T. Kloks, C.M. Lee, J. Liu, Feedback vertex sets and disjoint cycles in planar (di)graphs, Optimization Online, 2001.; T. Kloks, C.M. Lee, J. Liu, Feedback vertex sets and disjoint cycles in planar (di)graphs, Optimization Online, 2001. |
| [48] | Lagergren, J., Efficient parallel algorithms for graphs of bounded tree-width, J. Algorithms, 20, 1, 20-44 (1996) · Zbl 0840.68058 |
| [49] | Lipton, R. J.; Tarjan, R. E., Applications of a planar separator theorem, SIAM J. Comput., 9, 3, 615-627 (1980) · Zbl 0456.68077 |
| [50] | Matoušek, J.; Thomas, R., On the complexity of finding iso- and other morphisms for partial \(k\)-trees, Discrete Math., 108, 1-3, 343-364 (1992) · Zbl 0764.68128 |
| [51] | Miller, G. L.; Ramachandran, V., A new graph triconnectivity algorithm and its parallelization, Combinatorica, 12, 1, 53-76 (1992) · Zbl 0753.05064 |
| [52] | Robertson, N.; Seymour, P. D., Graph minors. III, Planar tree-width, J. Combin. Theory Ser. B, 36, 49-64 (1984) · Zbl 0548.05025 |
| [53] | Robertson, N.; Seymour, P. D., Graph minors—a survey, (Anderson, I., Surveys in Combinatorics (1985), Cambridge University Press: Cambridge University Press Cambridge), 153-171 · Zbl 0764.05069 |
| [54] | Robertson, N.; Seymour, P. D., Graph minors. II, Algorithmic aspects of tree-width, J. Algorithms, 7, 3, 309-322 (1986) · Zbl 0611.05017 |
| [55] | Robertson, N.; Seymour, P. D., Graph minors. X, Obstructions to tree-decomposition, J. Combin. Theory Ser. B, 52, 153-190 (1991) · Zbl 0764.05069 |
| [56] | N. Robertson, P. Seymour, Excluding a graph with one crossing, in: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Graph Structure Theory, 1993, pp. 669-675.; N. Robertson, P. Seymour, Excluding a graph with one crossing, in: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Graph Structure Theory, 1993, pp. 669-675. · Zbl 0797.05038 |
| [57] | Rose, D. J., On simple characterizations of \(k\)-trees, Discrete Math., 7, 317-322 (1974) · Zbl 0285.05128 |
| [58] | Sanders, D. P., On linear recognition of tree-width at most four, SIAM J. Discrete Math., 9, 1, 101-117 (1996) · Zbl 0847.05087 |
| [59] | Seymour, P. D.; Thomas, R., Call routing and the ratcatcher, Combinatorica, 14, 2, 217-241 (1994) · Zbl 0799.05057 |
| [60] | Sundaram, R.; Singh, K. S.; Rangan, P. C., Treewidth of circular-arc graphs, SIAM J. Discrete Math., 7, 4, 647-655 (1994) · Zbl 0814.05065 |
| [61] | Tarjan, R., Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 2, 146-160 (1972) · Zbl 0251.05107 |
| [62] | J.A. Telle, A. Proskurowski, Practical algorithms on partial \(k\); J.A. Telle, A. Proskurowski, Practical algorithms on partial \(k\) |
| [63] | Telle, J. A.; Proskurowski, A., Algorithms for vertex partitioning problems on partial \(k\)-trees, SIAM J. Discrete Math., 10, 4, 529-550 (1997) · Zbl 0885.68118 |
| [64] | Thomason, A., The extremal function for complete minors, J. Combin. Theory, Ser. B, 81, 2, 318-338 (2001) · Zbl 1024.05083 |
| [65] | J. van Leeuwen, Graph algorithms, in: Handbook of Theoretical Computer Science, Vol. A, Elsevier, Amsterdam, 1990, pp. 525-631 (Chapter 10).; J. van Leeuwen, Graph algorithms, in: Handbook of Theoretical Computer Science, Vol. A, Elsevier, Amsterdam, 1990, pp. 525-631 (Chapter 10). · Zbl 0900.68258 |
| [66] | Wagner, K., Über eine Eigenschaft der ebenen Komplexe, Math. Ann., 114, 570-590 (1937) · JFM 63.0550.01 |
| [67] | Williamson, S. G., Depth-first search and Kuratowski subgraphs, J. Assoc. Comput. Mach., 31, 4, 681-693 (1984) · Zbl 0632.68063 |
| [68] | M. Yannakakis, Node- and edge-deletion NP-complete problems, in: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, 1978, pp. 253-264.; M. Yannakakis, Node- and edge-deletion NP-complete problems, in: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, 1978, pp. 253-264. · Zbl 1282.68131 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
