Parameterized complexity of the spanning tree congestion problem. (English) Zbl 1253.68163
Summary: We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most \(k\) can be solved in linear time for every fixed \(k\). We also show that for every fixed \(k\) and \(d\) the problem is solvable in linear time for graphs of degree at most \(d\). In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed \(k\geq 8\). Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for \(k\leq 3\) the problem becomes polynomially time solvable.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305–1317 (1996) · Zbl 0864.68074 · doi:10.1137/S0097539793251219 |
| [2] | Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7, 555–581 (1992) · Zbl 0753.05062 · doi:10.1007/BF01758777 |
| [3] | Brandstädt, A., Dragan, F.F., Le, H.-O., Le, V.B.: Tree spanners on chordal graphs: complexity and algorithms. Theor. Comput. Sci. 310, 329–354 (2004) · Zbl 1049.05075 · doi:10.1016/S0304-3975(03)00424-9 |
| [4] | Brandstädt, A., Dragan, F.F., Le, H.-O., Le, V.B., Uehara, R.: Tree spanners for bipartite graphs and probe interval graphs. Algorithmica 47, 27–51 (2007) · Zbl 1107.68062 · doi:10.1007/s00453-006-1209-y |
| [5] | Cai, L., Corneil, D.G.: Tree spanners. SIAM J. Discrete Math. 8, 359–387 (1995) · Zbl 0832.05037 · doi:10.1137/S0895480192237403 |
| [6] | Castejón, A., Ostrovskii, M.I.: Minimum congestion spanning trees of grids and discrete toruses. Discuss. Math., Graph Theory 29, 511–519 (2009) · Zbl 1193.05058 · doi:10.7151/dmgt.1461 |
| [7] | Cormen, T., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009) · Zbl 1187.68679 |
| [8] | Courcelle, B.: The monadic second-order logic of graphs III: Tree-decompositions, minor and complexity issues. Theor. Inform. Appl. 26, 257–286 (1992) · Zbl 0754.03006 |
| [9] | Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23, 864–894 (1994) · Zbl 0809.68075 · doi:10.1137/S0097539792225297 |
| [10] | Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. J. ACM 52, 866–893 (2005) · doi:10.1145/1101821.1101823 |
| [11] | Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discrete Math. 18(3), 501–511 (2004) · Zbl 1069.05070 · doi:10.1137/S0895480103433410 |
| [12] | Demaine, E.D., Hajiaghayi, M.: Graphs excluding a fixed minor have grids as large as treewidth,with combinatorial and algorithmic applications through bidimensionality. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 682–689. SIAM, Philadelphia (2005) · Zbl 1297.05227 |
| [13] | Demaine, E.D., Hajiaghayi, M.: Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica 28, 19–36 (2008) · Zbl 1174.05115 · doi:10.1007/s00493-008-2140-4 |
| [14] | Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.: Algorithmic graph minor theory: Decomposition, approximation, and coloring. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 637–646. IEEE Computer Society, Los Alamitos (2005) |
| [15] | Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.: Approximation algorithms via structural results for apex-minor-free graphs. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009). Lecture Notes in Computer Science, vol. 5555, pp. 316–327. Springer, Berlin (2009) · Zbl 1248.68555 |
| [16] | Diestel, R.: Graph Theory, 3rd edn. Springer, Berlin (2005) · Zbl 1074.05001 |
| [17] | Dragan, F.F., Fomin, F.V., Golovach, P.A.: Spanners in sparse graphs, Journal of Computer and System Sciences, doi: 10.1016/j.jcss.2010.10.002 · Zbl 1153.68406 |
| [18] | Dragan, F.F., Fomin, F.V., Golovach, P.A.: Approximation of minimum weight spanners for sparse graphs. Theor. Comput. Sci. 412, 846–852 (2011) · Zbl 1206.68232 · doi:10.1016/j.tcs.2010.11.034 |
| [19] | Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999) |
| [20] | Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27, 275–291 (2000) · Zbl 0963.05128 · doi:10.1007/s004530010020 |
| [21] | Fekete, S.P., Kremer, J.: Tree spanners in planar graphs. Discrete Appl. Math. 108, 85–103 (2001) · Zbl 0969.68111 · doi:10.1016/S0166-218X(00)00226-2 |
| [22] | Fomin, F.V., Golovach, P.A., van Leeuwen, E.J.: Spanners of bounded degree graphs. Inf. Process. Lett. 111, 142–144 (2011) · Zbl 1260.68154 · doi:10.1016/j.ipl.2010.10.021 |
| [23] | Geelen, J.F., Richter, R.B., Salazar, G.: Embedding grids in surfaces. Eur. J. Comb. 25, 785–792 (2004) · Zbl 1050.05035 · doi:10.1016/j.ejc.2003.07.007 |
| [24] | Grohe, M.: Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23, 613–632 (2003) · Zbl 1089.05503 · doi:10.1007/s00493-003-0037-9 |
| [25] | Grohe, M., Marx, D.: On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B 99, 218–228 (2009) · Zbl 1205.05049 · doi:10.1016/j.jctb.2008.06.004 |
| [26] | Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM 21, 549–568 (1974) · Zbl 0307.68025 · doi:10.1145/321850.321852 |
| [27] | Hruska, S.W.: On tree congestion of graphs. Discrete Math. 308, 1801–1809 (2008) · Zbl 1151.05014 · doi:10.1016/j.disc.2007.04.030 |
| [28] | Kozawa, K., Otachi, Y., Yamazaki, K.: On spanning tree congestion of graphs. Discrete Math. 309, 4215–4224 (2009) · Zbl 1232.05116 · doi:10.1016/j.disc.2008.12.021 |
| [29] | Kratochvíl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl. Math. 52, 233–252 (1994) · Zbl 0810.68083 · doi:10.1016/0166-218X(94)90143-0 |
| [30] | Law, H.-F.: Spanning tree congestion of the hypercube. Discrete Math. 309, 6644–6648 (2009) · Zbl 1179.05032 · doi:10.1016/j.disc.2009.07.007 |
| [31] | Lawler, E.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976) · Zbl 0413.90040 |
| [32] | Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11, 329–343 (1982) · Zbl 0478.68043 · doi:10.1137/0211025 |
| [33] | Löwenstein, C., Rautenbach, D., Regen, F.: On spanning tree congestion. Discrete Math. 309, 4653–4655 (2009) · Zbl 1213.05093 · doi:10.1016/j.disc.2009.01.012 |
| [34] | MacLane, S.: A combinatorial condition for planar graphs. Fundam. Math. 28, 22–32 (1937) · Zbl 0015.37501 |
| [35] | Mohar, B.: Combinatorial local planarity and the width of graph embeddings. Can. J. Math. 44, 1272–1288 (1992) · Zbl 0777.05052 · doi:10.4153/CJM-1992-076-8 |
| [36] | Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001) · Zbl 0979.05002 |
| [37] | Okamoto, Y., Otachi, Y., Uehara, R., Uno, T.: Hardness results and an exact exponential algorithm for the spanning tree congestion problem. In: Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011). Lecture Notes in Comput. Sci., vol. 6648, pp. 452–462 (2011) · Zbl 1331.68094 |
| [38] | Ostrovskii, M.I.: Minimal congestion trees. Discrete Math. 285, 219–226 (2004) · Zbl 1051.05032 · doi:10.1016/j.disc.2004.02.009 |
| [39] | Ostrovskii, M.I.: Minimum congestion spanning trees in planar graphs. Discrete Math. 310, 1204–1209 (2010) · Zbl 1230.05112 · doi:10.1016/j.disc.2009.11.016 |
| [40] | Otachi, Y., Bodlaender, H.L., van Leeuwen, E.J.: Complexity results for the spanning tree congestion problem. In: Proceedings of the 6th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2010). Lecture Notes in Comput. Sci., vol. 6410, pp. 3–14 (2010) · Zbl 1308.68067 |
| [41] | Peleg, D.: Low stretch spanning trees. In: Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002). Lecture Notes in Comput. Sci., vol. 2420, pp. 68–80 (2002) · Zbl 1014.68116 |
| [42] | Raspaud, A., Sýkora, O., Vrťo, I.: Congestion and dilation, similarities and differences: a survey. In: Proceedings of the 7th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2000), pp. 269–280. Carleton Scientific, Oxford (2000) |
| [43] | Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory, Ser. B 52, 153–190 (1991) · Zbl 0764.05069 · doi:10.1016/0095-8956(91)90061-N |
| [44] | Robertson, N., Seymour, P.D.: Graph minors. XVI. Excluding a non-planar graph. J. Comb. Theory, Ser. B 89, 43–76 (2003) · Zbl 1023.05040 · doi:10.1016/S0095-8956(03)00042-X |
| [45] | Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. J. Comb. Theory, Ser. B 62, 323–348 (1994) · Zbl 0807.05023 · doi:10.1006/jctb.1994.1073 |
| [46] | Simonson, S.: A variation on the min cut linear arrangement problem. Math. Syst. Theory 20, 235–252 (1987) · Zbl 0643.68094 · doi:10.1007/BF01692067 |
| [47] | Thomassen, C.: A simpler proof of the excluded minor theorem for higher surfaces. J. Comb. Theory, Ser. B 70, 306–311 (1997) · Zbl 0882.05053 · doi:10.1006/jctb.1997.1761 |
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.
