Abstract
We define the notion of diversity for families of finite functions, and express the limitations of a simple class of holographic algorithms in terms of limitations on diversity. We go on to describe polynomial time holographic algorithms for computing the parity of the following quantities for degree three planar undirected graphs: the number of 3-colorings up to permutation of colors, the number of connected vertex covers, and the number of induced forests or feedback vertex sets. In each case the parity can be computed for any slice of the problem, in particular for colorings where the first color is used a certain number of times, or where the connected vertex cover, feedback set or induced forest has a certain number of nodes. These holographic algorithms use bases of three components, rather than two.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barbanchon, R.: Reductions fines entre problèmes NP-complets, PhD Thesis, Université de Caen Basse-Normandie (2003)
Barbanchon, R.: On unique graph 3-colorability and parsimonious reductions in the plane. Theoretical Computer Science 319(1-3), 455–482 (2004)
Bubley, R., Dyer, M., Greenhill, C., Jerrum, M.: On approximately counting colourings of small degree graphs. SIAM J. Comput. 29, 387–400 (1999)
Cai, J.-Y., Choudhary, V.: Some Results on Matchgates and Holographic Algorithms. International Journal of Software and Informatics 1(1), 3–36 (2007)
Cai, J.-Y., Choudhary, V., Lu, P.: On the Theory of Matchgate Computations. Theory of Computing Systems 45(1), 108–132 (2009)
Cai, J.-Y., Lu, P.: Holographic algorithms: from art to science. In: STOC 2007, pp. 401–410 (2007)
Cai, J.-Y., Lu, P.: Holographic algorithms: The power of dimensionality resolved. Theor. Comput. Sci. 410(18), 1618–1628 (2009)
Cai, J.-Y., Lu, P., Xia, M.: Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. In: FOCS, pp. 644–653 (2008)
Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the 3rd ACM STOC, pp. 151–158 (1971)
Escoffier, B., Gourves, L., Monnot, J.: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. Journal of Discrete Algorithms (2009)
Fernau, H., Manlove, D.: Vertex and edge covers with clustering properties: Complexity and algorithms. Journal of Discrete Algorithms (2009)
Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem is NP complete. SIAM Journal of Applied Mathematics 32, 826–834 (1977)
Garey, M.R., Johnson, D.S.: Computer and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)
Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Stearns, R.E.: The Complexity of Planar Counting Problems. SIAM J. Comput. 27(4), 1142–1167 (1998)
Jerrum, M.R.: Two-dimensional monomer-dimer systems are computationally intractable. J. Statist. Phys. 48(1-2), 121–134 (1987)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–104. Plenum Press, New York (1972)
Ladner, R.E.: The Circuit Value Problem is Log Space Complete for P. SIGACT NEWS 7(1), 18–20 (1975)
Li, D.M., Liu, Y.P.: A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph. Acta Math. Sci. 19(4), 375–381 (1999)
Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11, 329–343 (1982)
Lupanov, O.B.: A method of circuit synthesis. Izv. VUZ Radiofiz 1, 120–140 (1958)
Neciporuk, E.I.: A Boolean Function. Sov. Math. Dokl. 7, 999–1000 (1966)
Speckenmeyer, E.: Untersuchungen zum Feedback Vertex Set Problem in ungerichteten Graphen. PhD Thesis, Universität Paderborn (1983)
Speckenmeyer, E.: On feedback vertex sets and nonseparating independent sets in cubic graphs. Journal of Graph Theory 12(3), 405–412 (1988)
Ueno, S., Kajitani, Y., Gotoh, S.: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Mathematics 72, 355–360 (1988)
Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science 8, 189–201 (1979)
Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Computing 8(3), 410–421 (1979)
Valiant, L.G.: Holographic algorithms (extended abstract). In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, October 17-19, pp. 306–315. IEEE Press, Los Alamitos (2004)
Valiant, L.G.: Completeness for parity problems. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 1–9. Springer, Heidelberg (2005)
Valiant, L.G.: Accidental algorithms. In: Proc. 47th Annual IEEE Symposium on Foundations of Computer Science, October 22-24, pp. 509–517. IEEE Press, Los Alamitos (2006)
Valiant, L.G.: Holographic algorithms. SIAM J. on Computing 37(5), 1565–1594 (2008); Earlier version: Electronic Colloquium on Computational Complexity, Report TR05-099 (2005)
Xia, M., Zhang, P., Zhao, W.: Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci. 384(1), 111–125 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Valiant, L.G. (2010). Some Observations on Holographic Algorithms. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_50
Download citation
DOI: https://doi.org/10.1007/978-3-642-12200-2_50
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12199-9
Online ISBN: 978-3-642-12200-2
eBook Packages: Computer ScienceComputer Science (R0)