Skip to main content

2014 | OriginalPaper | Buchkapitel

The Firefighter Problem: A Structural Analysis

verfasst von : Janka Chlebíková, Morgan Chopin

Erschienen in: Parameterized and Exact Computation

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We consider the complexity of the firefighter problem where a budget of \({b \ge 1}\) firefighters are available at each time step. This problem is proved to be NP-complete even on trees of degree at most three and \({b = 1}\) [10] and on trees of bounded degree \(b+3\) for any fixed \(b \ge 2\) [3]. In this paper, we provide further insight into the complexity landscape of the problem by showing a complexity dichotomy result with respect to the parameters pathwidth and maximum degree of the input graph. More precisely, we first prove that the problem is NP-complete even on trees of pathwidth at most three for any \(b \ge 1\). Then we show that the problem turns out to be fixed parameter-tractable with respect to the combined parameter “pathwidth” and “maximum degree” of the input graph. Finally, we show that the problem remains NP-complete on very dense graphs, namely co-bipartite graphs, but is fixed-parameter tractable with respect to the parameter “cluster vertex deletion”.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Anshelevich, E., Chakrabarty, D., Hate, A., Swamy, C.: Approximability of the firefighter problem. Algorithmica 62(1–2), 520–536 (2012)CrossRefMATHMathSciNet Anshelevich, E., Chakrabarty, D., Hate, A., Swamy, C.: Approximability of the firefighter problem. Algorithmica 62(1–2), 520–536 (2012)CrossRefMATHMathSciNet
2.
Zurück zum Zitat Bazgan, C., Chopin, M., Cygan, M., Fellows, M.R., Fomin, F.V., van Leeuwen, E.J.: Parameterized complexity of firefighting. J. Comput. Syst. Sci. 80(7), 1285–1297 (2014)CrossRefMATH Bazgan, C., Chopin, M., Cygan, M., Fellows, M.R., Fomin, F.V., van Leeuwen, E.J.: Parameterized complexity of firefighting. J. Comput. Syst. Sci. 80(7), 1285–1297 (2014)CrossRefMATH
3.
Zurück zum Zitat Bazgan, C., Chopin, M., Ries, B.: The firefighter problem with more than one firefighter on trees. Discrete Appl. Math. 161(7–8), 899–908 (2013)CrossRefMATHMathSciNet Bazgan, C., Chopin, M., Ries, B.: The firefighter problem with more than one firefighter on trees. Discrete Appl. Math. 161(7–8), 899–908 (2013)CrossRefMATHMathSciNet
4.
Zurück zum Zitat Bodlaender, H.L.: Classes of graphs with bounded tree-width. Bull. EATCS 36, 116–128 (1988)MATH Bodlaender, H.L.: Classes of graphs with bounded tree-width. Bull. EATCS 36, 116–128 (1988)MATH
5.
Zurück zum Zitat Cai, L., Verbin, E., Yang, L.: Firefighting on trees: (1 \(-\) 1/e)–approximation, fixed parameter tractability and a subexponential algorithm. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 258–269. Springer, Heidelberg (2008)CrossRef Cai, L., Verbin, E., Yang, L.: Firefighting on trees: (1 \(-\) 1/e)–approximation, fixed parameter tractability and a subexponential algorithm. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 258–269. Springer, Heidelberg (2008)CrossRef
6.
Zurück zum Zitat Chung, F.R., Seymour, P.D.: Graphs with small bandwidth and cutwidth. In: Graph Theory and combinatorics 1988 Proceedings of the Cambridge Combinatorial Conference in Honour of Paul Erdös, Annals of Discrete Mathematics, vol. 43, pp. 113–119 (1989) Chung, F.R., Seymour, P.D.: Graphs with small bandwidth and cutwidth. In: Graph Theory and combinatorics 1988 Proceedings of the Cambridge Combinatorial Conference in Honour of Paul Erdös, Annals of Discrete Mathematics, vol. 43, pp. 113–119 (1989)
7.
Zurück zum Zitat Costa, V., Dantas, S., Dourado, M.C., Penso, L., Rautenbach, D.: More fires and more fighters. Discrete Appl. Math. 161(16–17), 2410–2419 (2013)CrossRefMATHMathSciNet Costa, V., Dantas, S., Dourado, M.C., Penso, L., Rautenbach, D.: More fires and more fighters. Discrete Appl. Math. 161(16–17), 2410–2419 (2013)CrossRefMATHMathSciNet
8.
Zurück zum Zitat Develin, M., Hartke, S.G.: Fire containment in grids of dimension three and higher. Discrete Appl. Math. 155(17), 2257–2268 (2007)CrossRefMATHMathSciNet Develin, M., Hartke, S.G.: Fire containment in grids of dimension three and higher. Discrete Appl. Math. 155(17), 2257–2268 (2007)CrossRefMATHMathSciNet
9.
Zurück zum Zitat Doucha, M., Kratochvíl, J.: Cluster vertex deletion: a parameterization between vertex cover and clique-width. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 348–359. Springer, Heidelberg (2012)CrossRef Doucha, M., Kratochvíl, J.: Cluster vertex deletion: a parameterization between vertex cover and clique-width. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 348–359. Springer, Heidelberg (2012)CrossRef
10.
Zurück zum Zitat Finbow, S., King, A., MacGillivray, G., Rizzi, R.: The firefighter problem for graphs of maximum degree three. Discrete Math. 307(16), 2094–2105 (2007)CrossRefMATHMathSciNet Finbow, S., King, A., MacGillivray, G., Rizzi, R.: The firefighter problem for graphs of maximum degree three. Discrete Math. 307(16), 2094–2105 (2007)CrossRefMATHMathSciNet
11.
Zurück zum Zitat Fomin, F.V., Heggernes, P., van Leeuwen, E.J.: Making Life Easier for Firefighters. In: Kranakis, E., Krizanc, D., Luccio, F. (eds.) FUN 2012. LNCS, vol. 7288, pp. 177–188. Springer, Heidelberg (2012)CrossRef Fomin, F.V., Heggernes, P., van Leeuwen, E.J.: Making Life Easier for Firefighters. In: Kranakis, E., Krizanc, D., Luccio, F. (eds.) FUN 2012. LNCS, vol. 7288, pp. 177–188. Springer, Heidelberg (2012)CrossRef
12.
Zurück zum Zitat Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H Freeman and Company, New York (1979)MATH Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H Freeman and Company, New York (1979)MATH
13.
Zurück zum Zitat Hartnell, B.: Firefighter! an application of domination, Presentation. In: 10th Conference on Numerical Mathematics and Computing, University of Manitoba in Winnipeg, Canada (1995) Hartnell, B.: Firefighter! an application of domination, Presentation. In: 10th Conference on Numerical Mathematics and Computing, University of Manitoba in Winnipeg, Canada (1995)
14.
Zurück zum Zitat Hartnell, B., Li, Q.: Firefighting on trees: how bad is the greedy algorithm? Congressus Numerantium 145, 187–192 (2000)MATHMathSciNet Hartnell, B., Li, Q.: Firefighting on trees: how bad is the greedy algorithm? Congressus Numerantium 145, 187–192 (2000)MATHMathSciNet
15.
Zurück zum Zitat Iwaikawa, Y., Kamiyama, N., Matsui, T.: Improved approximation algorithms for firefighter problem on trees. IEICE Trans. Inf. Syst. E94.D(2), 196–199 (2011)CrossRef Iwaikawa, Y., Kamiyama, N., Matsui, T.: Improved approximation algorithms for firefighter problem on trees. IEICE Trans. Inf. Syst. E94.D(2), 196–199 (2011)CrossRef
18.
Zurück zum Zitat MacGillivray, G., Wang, P.: On the firefighter problem. J. Comb. Math. Comb. Comput. 47, 83–96 (2003)MATHMathSciNet MacGillivray, G., Wang, P.: On the firefighter problem. J. Comb. Math. Comb. Comput. 47, 83–96 (2003)MATHMathSciNet
19.
Metadaten
Titel
The Firefighter Problem: A Structural Analysis
verfasst von
Janka Chlebíková
Morgan Chopin
Copyright-Jahr
2014
DOI
https://doi.org/10.1007/978-3-319-13524-3_15