Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Turbocharging Treewidth Heuristics

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

A widely used class of algorithms for computing tree decompositions of graphs are heuristics that compute an elimination order, i.e., a permutation of the vertex set. In this paper, we propose toturbocharge these heuristics. For atarget treewidthk, suppose the heuristic has already computed a partial elimination order of width at mostk, but extending it by one more vertex exceeds the target widthk. At thismoment of regret, we solve a subproblem which is to recompute the last c positions of the partial elimination order such that it can be extended without exceeding width k. We show that this subproblem is fixed-parameter tractable when parameterized by k and c, but it is para-NP-hard andW[1]-hard when parameterized by onlyk orc, respectively. Our experimental evaluation of the FPT algorithm shows that we can trade a reasonable increase of the running time for the quality of the solution.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

Notes

References

  1. Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in ak-tree. SIAM J. Algebraic Discrete Methods8(2), 277–284 (1987)

    Article MathSciNet MATH  Google Scholar 

  2. Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.25(6), 1305–1317 (1996)

    Article MathSciNet MATH  Google Scholar 

  3. Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations I. Upper bounds. Inf. Comput.208(3), 259–275 (2010)

    Article MathSciNet MATH  Google Scholar 

  4. Downey, R., Egan, J., Fellows, M.R., Rosamond, F., Shaw, P.: Dynamic dominating set and turbo-charging greedy heuristics. Tsinghua Sci. Technol.19, 329–337 (2014)

    Article MathSciNet  Google Scholar 

  5. Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci.141(1&2), 109–131 (1995)

    Article MathSciNet MATH  Google Scholar 

  6. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)

  7. Gaspers, S., Gudmundsson, J., Jones, M., Mestre, J., Rümmele, S.: Turbocharging treewidth heuristics. In: Guo, J., Hermelin, D. (eds.) 11th International Symposium on Parameterized and Exact Computation, IPEC 2016,LIPIcs, vol. 63, pp. 13:1–13:13 (2016)

  8. Gaspers, S., Gudmundsson, J., Jones, M., Mestre, J., Rümmele, S.: Turbocharging treewidth heuristics (2016).https://github.com/mfjones/pace2016. Accessed 4 Aug 2018

  9. Gogate, V., Dechter, R.: A complete anytime algorithm for treewidth. In: Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 201–208. AUAI Press (2004)

  10. Hartung, S., Niedermeier, R.: Incremental list coloring of graphs, parameterized by conservation. Theor. Comput. Sci.494, 86–98 (2013)

    Article MathSciNet MATH  Google Scholar 

  11. Koster, A.M.C.A., Bodlaender, H.L., van Hoesel, S.P.M.: Treewidth: computational experiments. Electron. Notes Discrete Math.8, 54–57 (2001)

    Article MathSciNet MATH  Google Scholar 

Download references

Acknowledgements

We thank Michael R. Fellows for inspiring this line of research.

Author information

Authors and Affiliations

  1. UNSW Sydney, Sydney, Australia

    Serge Gaspers & Stefan Rümmele

  2. Data61, CSIRO, Canberra, Australia

    Serge Gaspers

  3. University of Sydney, Camperdown, Australia

    Joachim Gudmundsson, Julián Mestre & Stefan Rümmele

  4. University of Illinois at Urbana-Champaign, Champaign, USA

    Mitchell Jones

Authors
  1. Serge Gaspers

    You can also search for this author inPubMed Google Scholar

  2. Joachim Gudmundsson

    You can also search for this author inPubMed Google Scholar

  3. Mitchell Jones

    You can also search for this author inPubMed Google Scholar

  4. Julián Mestre

    You can also search for this author inPubMed Google Scholar

  5. Stefan Rümmele

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toStefan Rümmele.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version appeared in the Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) [7]. Serge Gaspers is the recipient of an Australian Research Council (ARC) Future Fellowship (FT140100048). The authors acknowledge support under the ARC’s Discovery Projects funding scheme (DP150101134 and DP180102870).

Experimental Results

Experimental Results

See Tables4,5,6,7,8,9,10 and11.

Table 4 Experimental results on DIMACS Graph coloring networks using\(c=8\)
Table 5 Experimental results on DIMACS Graph coloring networks using\(c=8\)
Table 6 Experimental results on DIMACS Graph coloring networks using\(c=6\)
Table 7 Experimental results on DIMACS Graph coloring networks using\(c=4\)
Table 8 Comparison of average quality and average running time on different instances from the Bayesian network repository, using\(c = 8\)
Table 9 Comparison of average quality and average running time on different instances from PACE 2017 competition instances, using\(c = 8\)
Table 10 Comparison of average quality and average running time on different instances from PACE 2017 competition instances, using\(c = 8\)
Table 11 Comparison of average quality and average running time on different instances from PACE 2017 competition instances, using\(c = 8\)

Rights and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gaspers, S., Gudmundsson, J., Jones, M.et al. Turbocharging Treewidth Heuristics.Algorithmica81, 439–475 (2019). https://doi.org/10.1007/s00453-018-0499-1

Download citation

Keywords

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp