Hostname: page-component-74656f9884-g96k6 Total loading time: 0 Render date: 2026-11-10T02:52:42.589Z Has data issue: false hasContentIssue false
  • English
  • Français

A Graph Polynomial for Independent Sets of Bipartite Graphs

Published online by Cambridge University Press:  10 July 2012

Q. GE  and
D. ŠTEFANKOVIČ
Q. GE
Affiliation:
Department of Computer Science, University of Rochester, Rochester, NY 14627–0226, USA (e-mail: qge@cs.rochester.edu and stefanko@cs.rochester.edu)
D. ŠTEFANKOVIČ
Affiliation:
Department of Computer Science, University of Rochester, Rochester, NY 14627–0226, USA (e-mail: qge@cs.rochester.edu and stefanko@cs.rochester.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We introduce a new graph polynomial that encodes interesting properties of graphs, for example, the number of matchings, the number of perfect matchings, and, for bipartite graphs, the number of independent sets (#BIS).

We analyse the complexity of exact evaluation of the polynomial at rational points and show a dichotomy result: for most points exact evaluation is #P-hard (assuming the generalized Riemann hypothesis) and for the rest of the points exact evaluation is trivial.

Keywords

Primary 05C31Secondary 03D15

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 5 , September 2012 , pp. 695 - 714
Copyright
Copyright © Cambridge University Press 2012

References

[1]Arratia, R., Bollobás, B. and Sorkin, G. B. (2004) A two-variable interlace polynomial. Combinatorica 24 567–584.Google Scholar
[2]Bach, E. and Shallit, J. (1996) Algorithmic Number Theory, Vol. 1, Efficient Algorithms, Foundations of Computing Series, MIT Press.Google Scholar
[3]Baxter, R. J. (1989) Exactly Solved Models in Statistical Mechanics, Academic Press. Reprint of the 1982 original.Google Scholar
[4]Bläser, M. and Hoffmann, C. (2008) On the complexity of the interlace polynomial. In STACS (Albers, S. and Weil, P., eds), Vol. 1 of LIPIcs, Leibniz-Zentrum für Informatik, pp. 97–108.Google Scholar
[5]Bläser, M. and Hoffmann, C. (2011) Fast evaluation of interlace polynomials on graphs of bounded treewidth. Algorithmica 61 3–35.Google Scholar
[6]Bordewich, M. and Kang, R. J. (2011) Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width. In ICALP (1), pp. 533–544.Google Scholar
[7]Courcelle, B. (2008) A multivariate interlace polynomial and its computation for graphs of bounded clique-width. Electron. J. Combin. 15 #R69.Google Scholar
[8]Courcelle, B., Makowsky, J. A. and Rotics, U. (2001) On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Appl. Math. 108 23–52.CrossRefGoogle Scholar
[9]Dyer, M. E., Frieze, A. M. and Jerrum, M. R. (2002) On counting independent sets in sparse graphs. SIAM J. Comput. 31 1527–1541.CrossRefGoogle Scholar
[10]Dyer, M. E., Goldberg, L. A., Greenhill, C. and Jerrum, M. R. (2004) The relative complexity of approximate counting problems. Algorithmica 38 471–500.Google Scholar
[11]Dyer, M. E., Goldberg, L. A. and Jerrum, M. R. (2010) An approximation trichotomy for boolean #CSP. Journal of Computer and System Sciences 76 267–277.CrossRefGoogle Scholar
[12]Dyer, M. E. and Greenhill, C. (2000) On Markov chains for independent sets. J. Algorithms 35 17–49.Google Scholar
[13]Ellis-Monaghan, J. and Merino, C. (2011) Graph polynomials and their applications I: The Tutte polynomial. Structural Analysis of Complex Networks (Dehmer, M., ed.), Birkhuser Boston, pp. 219–255.Google Scholar
[14]Ellis-Monaghan, J. and Merino, C. (2011) Graph polynomials and their applications II: Interrelations and interpretations. Structural Analysis of Complex Networks (Dehmer, M., ed.), Birkhuser Boston, pp. 257–292.Google Scholar
[15]Frandsen, G. S. and Frandsen, P. F. (2006) Dynamic matrix rank. In Automata, Languages and Programming, Part I, Vol. 4051 of Lecture Notes in Computer Science, Springer, pp. 395–406.Google Scholar
[16]Ge, Q. and Štefankovič, D. (2010) A graph polynomial for independent sets of bipartite graphs. In FSTTCS, pp. 240–250.Google Scholar
[17]Goldberg, L. A. and Jerrum, M. R. (2007) The complexity of ferromagnetic Ising with local fields. Combin. Probab. Comput. 16 43–61.CrossRefGoogle Scholar
[18]Goldberg, L. A. and Jerrum, M. R. (2010) Personal communication.Google Scholar
[19]Goldberg, L. A., Jerrum, M. R. and Paterson, M. (2003) The computational complexity of two-state spin systems. Random Struct. Alg. 23 133–154.CrossRefGoogle Scholar
[20]Jaeger, F., Vertigan, D. and Welsh, D. J. A. (1990) On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc. 108 35–53.Google Scholar
[21]Jerrum, M. R. and Sinclair, A. (1993) Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput. 22 1087–1116.Google Scholar
[22]Jerrum, M. R., Valiant, L. G. and Vazirani, V. V. (1986) Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43 169–188.CrossRefGoogle Scholar
[23]Luby, M. and Vigoda, E. (1999) Fast convergence of the Glauber dynamics for sampling independent sets. Random Struct. Alg. 15 229–241.Google Scholar
[24]Makowsky, J. A. (2008) From a zoo to a zoology: Towards a general theory of graph polynomials. Theory Comput. Syst. 43 542–562.Google Scholar
[25]Moree, P. and Stevenhagen, P. (2000) A two-variable Artin conjecture. J. Number Theory 85 291–304.Google Scholar
[26]Moree, P. and Stevenhagen, P. (2001) Prime divisors of the Lagarias sequence. J. Théor. Nombres Bordeaux 13 241–251.Google Scholar
[27]Provan, J. S. and Ball, M. O. (1983) The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12 777–788.CrossRefGoogle Scholar
[28]Sly, A. (2010) Computational transition at the uniqueness threshold. In Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 287–296.CrossRefGoogle Scholar
[29]Stevenhagen, P. (2000) Prime densities for second order torsion sequences. Preprint.Google Scholar
[30]Tutte, W. T. (1947) A ring in graph theory. Proc. Cambridge Philos. Soc. 43 26–40.Google Scholar
[31]Tutte, W. T. (1954) A contribution to the theory of chromatic polynomials. Canadian J. Math. 6 80–91.CrossRefGoogle Scholar
[32]Vadhan, S. P. (2001) The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput. 31 398–427.Google Scholar
[33]Weitz, D. (2006) Counting independent sets up to the tree threshold. In STOC'06: Proc. 38th Annual ACM Symposium on Theory of Computing, ACM, pp. 140–149.Google Scholar
[34]Welsh, D. J. A. (1993) Complexity: Knots, Colourings and Counting, Vol. 186 of London Mathematical Society Lecture Note Series, Cambridge University Press.CrossRefGoogle Scholar
[35]Xia, M., Zhang, P. and Zhao, W. (2007) Computational complexity of counting problems on 3-regular planar graphs. Theoret. Comput. Sci. 384 111–125.CrossRefGoogle Scholar