Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth. (English) Zbl 1115.68114
Summary: The subgraph isomorphism problem, that of finding a copy of one graph in another, has proved to be intractable except when certain restrictions are placed on the inputs. In this paper, we introduce a new property for graphs along with an associated graph class (a generalization on bounded degree graphs) and extend the known classes of inputs for which polynomial-time subgraph isomorphism algorithms are attainable. In particular, if the removal of any set of at most \(k\) vertices from an \(n\)-vertex graph results in \(O(k \log n)\) connected components, we say that the graph is a log-bounded fragmentation graph. We present a polynomial-time algorithm for finding a subgraph of \(H\) isomorphic to a graph \(G\) when \(G\) is a log-bounded fragmentation graph and \(H\) has bounded treewidth; these results are extended to handle graphs of locally bounded treewidth (a generalization of treewidth) when \(G\) is a log-bounded fragmentation graph and has constant diameter.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Arnborg, Stefan; Lagergren, Jens; Seese, Detlef, Easy problems for tree-decomposable graphs, J. Algorithms, 12, 2, 308-340 (1991) · Zbl 0734.68073 |
| [2] | Arnborg, Stefan; Proskurowski, Andrzej, Characterization and recognition of partial 3-trees, SIAM J. Algebraic Discrete Methods, 7, 2, 305-314 (1986) · Zbl 0597.05027 |
| [3] | Arnborg, Stefan; Proskurowski, Andrzej, Linear time algorithms for NP-hard problems restricted to partial \(k\)-trees, Discrete Appl. Math., 23, 1, 11-24 (1989) · Zbl 0666.68067 |
| [4] | Baker, Brenda S., Approximation algorithms for NP-complete problems on planar graphs, J. Assoc. Comput. Mach., 41, 1, 153-180 (1994) · Zbl 0807.68067 |
| [5] | Bern, Marshall W.; Lawler, Eugene L.; Wong, Alice L., Linear time computation of optimal subgraphs of decomposable graphs, J. Algorithms, 8, 216-235 (1987) · Zbl 0618.68058 |
| [6] | Bodlaender, Hans L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 6, 1305-1317 (1996) · Zbl 0864.68074 |
| [7] | Hans L. Bodlaender, Treewidth: Algorithmic techniques and results, in: Proc. 22nd Internat. Symposium on Mathematical Foundations of Computer Science, 1997, pp. 29-36; Hans L. Bodlaender, Treewidth: Algorithmic techniques and results, in: Proc. 22nd Internat. Symposium on Mathematical Foundations of Computer Science, 1997, pp. 29-36 · Zbl 0941.05057 |
| [8] | Bodlaender, Hans L., A partial \(k\)-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1-2, 1-45 (1998) · Zbl 0912.68148 |
| [9] | Bondy, John A.; Murty, U. S.R., Graph Theory with Applications (1976), American Elsevier Publishing Co., Inc.: American Elsevier Publishing Co., Inc. New York · Zbl 1226.05083 |
| [10] | Franz J. Brandenburg, Pattern matching problems in graphs, manuscript, 2001; Franz J. Brandenburg, Pattern matching problems in graphs, manuscript, 2001 |
| [11] | Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Nishimura, Naomi; Ragde, Prabhakar; Thilikos, Dimitrios M., Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, J. Comput. System Sci., 42, 69-108 (2002) · Zbl 0990.68100 |
| [12] | Dessmark, Anders; Lingas, Andrzej; Proskurowski, Andrzej, Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees, Algorithmica, 27, 3-4, 337-347 (2000) · Zbl 0960.05098 |
| [13] | Dessmark, Anders; Lingas, Andrzej; Proskurowski, Andrzej, Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time, Theoret. Comput. Sci., 236, 1-2, 179-191 (2000) · Zbl 0938.68143 |
| [14] | Eppstein, David, Subgraph isomorphism in planar graphs and related problems, J. Graph Algorithms Appl., 3, 3 (1999), 27 pp. (electronic) · Zbl 0949.05055 |
| [15] | Eppstein, David, Diameter and treewidth in minor-closed graph families, Algorithmica, 27, 3-4, 275-291 (2000) · Zbl 0963.05128 |
| [16] | Frick, Markus; Grohe, Martin, Deciding first-order properties of locally tree-decomposable structures, J. Assoc. Comput. Mach., 48, 1184-1206 (2001) · Zbl 1323.03014 |
| [17] | Garey, Michael R.; Johnson, David 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 |
| [18] | Garey, Michael R.; Johnson, David S.; Tarjan, Robert E., The planar hamiltonian circuit problem is NP-complete, SIAM J. Comput., 5, 6, 704-714 (1976) · Zbl 0346.05110 |
| [19] | Grohe, Martin, Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 23, 4, 613-632 (2003) · Zbl 1089.05503 |
| [20] | Gupta, Arvind; Nishimura, Naomi, The complexity of subgraph isomorphism for classes of partial \(k\)-trees, Theoret. Comput. Sci., 164, 1-2, 287-298 (1996) · Zbl 0871.68139 |
| [21] | Arvind Gupta, Naomi Nishimura, Sequential and parallel algorithms for embedding problems on classes of partial \(k\); Arvind Gupta, Naomi Nishimura, Sequential and parallel algorithms for embedding problems on classes of partial \(k\) |
| [22] | Hajiaghayi, MohammadTaghi, Algorithms for Graphs of (Locally) Bounded Treewidth (September 2001), Master’s thesis, University of Waterloo |
| [23] | Hajiaghayi, MohammadTaghi; Hajiaghayi, Mahdi, A note on the bounded fragmentation property and its applications in network reliability, European J. Combin., 24, 7, 891-896 (2003) · Zbl 1026.05068 |
| [24] | van Leeuwen, Jan, Graph algorithms, (Handbook of Theoretical Computer Science, vol. A (1990), Elsevier: Elsevier Amsterdam), 525-631 · Zbl 0900.68258 |
| [25] | Lingas, Andrzej, Subgraph isomorphism for biconnected outerplanar graphs in cubic time, Theoret. Comput. Sci., 63, 3, 295-302 (1989) · Zbl 0681.68090 |
| [26] | Lingas, Andrzej; Sysło, Maciej M., A polynomial-time algorithm for subgraph isomorphism of two-connected series-parallel graphs, (Automata, Languages and Programming. Automata, Languages and Programming, Tampere, 1988 (1988), Springer: Springer Berlin), 394-409 · Zbl 0656.68046 |
| [27] | Matoušek, Jiří; Thomas, Robin, On the complexity of finding iso- and other morphisms for partial \(k\)-trees, Discrete Math., 108, 1-3, 343-364 (1992) · Zbl 0764.68128 |
| [28] | Matula, David W., Subtree isomorphism in \(O(n^{5 / 2})\), (Algorithmic Aspects of Combinatorics. Algorithmic Aspects of Combinatorics, Conf., Vancouver Island, B.C., 1976. Algorithmic Aspects of Combinatorics. Algorithmic Aspects of Combinatorics, Conf., Vancouver Island, B.C., 1976, Ann. Discrete Math., vol. 2 (1978)), 91-106 · Zbl 0391.05022 |
| [29] | Robertson, Neil; Seymour, Paul D., Graph minors II. Algorithmic aspects of tree-width, J. Algorithms, 7, 3, 309-322 (1986) · Zbl 0611.05017 |
| [30] | Sanders, Daniel P., On linear recognition of tree-width at most four, SIAM J. Discrete Math., 9, 1, 101-117 (1996) · Zbl 0847.05087 |
| [31] | Sysło, Maciej M., The subgraph isomorphism problem for outerplanar graphs, Theoret. Comput. Sci., 17, 1, 91-97 (1982) · Zbl 0522.68061 |
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.
