Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 6842))
Included in the following conference series:
887Accesses
Abstract
We present new algorithms for exact multilineark-monomial counting which is to compute the sum of coefficients of all degree-k multilinear monomials in a given polynomialP over a ringR described by an arithmetic circuitC. If the polynomial can be represented as a product of two polynomials with degree at mostd < k, our algorithm can solve this problem in\(O^{*}(\binom{n}{\downarrow d})\) time, where\(\binom{n}{\downarrow d}=\sum_{i=0}^d\binom{n}{i}\).O* omits a polynomial factor inn. For the general case, the proposed algorithm takes time\(O^{*}(\binom{n}{\downarrow k})\). In both cases, our results are superior to previous approaches presented in [Koutis, I. and Williams, R.: Limits and applications of group algebras for parameterized problems.ICALP, pages 653-664 (2009)]. We also present a polynomial space algorithm with time bound\(O^{*}(2^k\binom{n}{k})\). By reducing the #k-path problem and the #m-setk-packing problem to the exact multilineark-monomial counting problem, we give algorithms for these two problems that match the fastest known results presented in [2].
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Yuster, R., Zwick, U.: Color coding. Journal of the ACM 42(4), 844–856 (1995)
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Counting paths and packings in halves. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 578–586. Springer, Heidelberg (2009)
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets möbius: fast subset convolution. In: STOC, pp. 67–74 (2007)
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Trimmed moebius inversion and graphs of bounded degree. Theory Comput. Syst. 47(3), 637–654 (2010)
Chen, J., Lu, S., Sze, S.-H., Zhang, F.: Improved algorithms for path, matching, and packing problems. In: SODA, pp. 298–307 (2007)
Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symbolic Computation 9(3), 251–280 (1990)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)
Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput. 33, 892–922 (2004)
Jia, W., Zhang, C., Chen, J.: An efficient parameterized algorithm for m-set packing. J. Algorithms 50, 106–117 (2004)
Kennes, R.: Computational aspects of the Moebius transform of a graph. IEEE Transactions on Systems, Man, and Cybernetics 22, 201–223 (1991)
Kneis, J., Mölle, D., Richter, S., Rossmanith, P.: Divide-and-color. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 58–67. Springer, Heidelberg (2006)
Koutis, I.: Faster algebraic algorithms for path and packing problems. In: ICALP, pp. 575–586 (2009)
Koutis, I., Williams, R.: Limits and applications of group algebras for parameterized problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 653–664. Springer, Heidelberg (2009)
Lokshtanov, D., Nederlof, J.: Saving space by algebraization. In: STOC, pp. 321–330 (2010)
Vassilevska, V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. In: STOC, pp. 455–464 (2009)
Williams, R.: Finding paths of length k inO*(2k) time. Inf. Process. Lett. 109(6), 315–318 (2009)
Yates, F.: The design and analysis of factorial experiments, Technical Communication No. 35, Commonwealth Bureau of Soil Science, Harpenden, UK (1937)
Author information
Authors and Affiliations
Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong
Dongxiao Yu, Qiang-Sheng Hua & Francis C. M. Lau
Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, 100084, P.R. China
Yuexuan Wang & Qiang-Sheng Hua
- Dongxiao Yu
You can also search for this author inPubMed Google Scholar
- Yuexuan Wang
You can also search for this author inPubMed Google Scholar
- Qiang-Sheng Hua
You can also search for this author inPubMed Google Scholar
- Francis C. M. Lau
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Department of Computer Science, University of Texas-Pan American, 78539, Edinburg, TX, USA
Bin Fu
Department of Computer Science, University of Texas at Dallas, 75080, Richardson, TX, USA
Ding-Zhu Du
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yu, D., Wang, Y., Hua, QS., Lau, F.C.M. (2011). Exact Parameterized Multilinear Monomial Counting viak-Layer Subset Convolution andk-Disjoint Sum. In: Fu, B., Du, DZ. (eds) Computing and Combinatorics. COCOON 2011. Lecture Notes in Computer Science, vol 6842. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22685-4_7
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-642-22684-7
Online ISBN:978-3-642-22685-4
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative