Abstract
We prove \(\mathsf {\#W[1]}\)-hardness of counting (1) trees with k edges in a given graph, (2) forests with k edges in a given graph, and (3) bases of a given matroid of rank (or nullity) k representable over an arbitrary field of characteristic two, where k is the parameter.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
That is, \(\sup \{\tau (H) \mid H \in {\mathcal {H}}\} < \infty \), where \(\tau (H)\) is the size of a minimum vertex cover of H.
- 2.
A slightly weaker version of this result with a simpler proof that still suffices for our application seems to follow along the lines of Snook [14].
- 3.
This terminology stems from the fact that the removal of a leaves v isolated.
References
Brand, C., Dell, H., Roth, M.: Fine-grained dichotomies for the tutte plane and boolean #CSP. In: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), 24–26 August 2016, Aarhus, Denmark, pp. 9:1–9:14 (2016)
Brand, C., Roth, M.: Parameterized counting of trees, forests and matroid bases. CoRR, abs/1611.01823 (2016)
Curticapean, R.: Counting matchings of size k Is \(\sharp \) W[1]-Hard. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 352–363. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39206-1_30
Curticapean, R., Marx, D.: Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts. In: 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2014), Philadelphia, PA, USA, 18–21 October 2014, pp. 130–139 (2014)
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Heidelberg (2015)
Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. In: Graph Algorithms and Applications, p. 283 (2002)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2006)
Gebauer, H., Okamoto, Y.: Fast exponential-time algorithms for the forest counting and the Tutte polynomial computation in graph classes. Int. J. Found. Comput. Sci. 20(1), 25–44 (2009)
Jerrum, M.: Counting trees in a graph is #P-complete. Inf. Process. Lett. 51(3), 111–116 (1994)
Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S.: Deterministic truncation of linear matroids. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 922–934. Springer, Heidelberg (2015). doi:10.1007/978-3-662-47672-7_75
Marx, D.: A parameterized view on matroid optimization problems. Theor. Comput. Sci. 410(44), 4471–4479 (2009)
Maurer, S.B.: Matrix generalizations of some theorems on trees, cycles and cocycles in graphs. SIAM J. Appl. Math. 30(1), 143–148 (1976)
Oxley, J.G.: Matroid Theory. Oxford University Press, New York (1992)
Snook, M.: Counting bases of representable matroids. Electr. J. Comb. 19(4), P41 (2012)
Vertigan, D.: Bicycle dimension and special points of the Tutte polynomial. J. Comb. Theory Ser. B 74(2), 378–396 (1998)
Vertigan, D., Welsh, D.J.A.: The compunational complexity of the Tutte plane. Comb. Probability Comput. 1, 181–187 (1992)
Acknowledgements
The authors wish to thank Markus Bläser, Radu Curticapean, Holger Dell and Petr Hliněný for helpful comments on this work.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Brand, C., Roth, M. (2017). Parameterized Counting of Trees, Forests and Matroid Bases. In: Weil, P. (eds) Computer Science – Theory and Applications. CSR 2017. Lecture Notes in Computer Science(), vol 10304. Springer, Cham. https://doi.org/10.1007/978-3-319-58747-9_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-58747-9_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-58746-2
Online ISBN: 978-3-319-58747-9
eBook Packages: Computer ScienceComputer Science (R0)