The Complexity of Parity Graph Homomorphism: An Initial Investigation

by John Faben and Mark Jerrum

Theory of Computing, Volume 11(2), pp. 35-57, 2015

Bibliography with links to cited articles

[1]   Andrei A. Bulatov: The complexity of the counting constraint satisfaction problem. J. ACM, 60(5):34, 2013. Preliminary version in ICALP’08, also available at ECCC. [doi:10.1145/2528400]

[2]   Andrei A. Bulatov and Martin Grohe: The complexity of partition functions. Theoret. Comput. Sci., 348(2-3):148–186, 2005. Preliminary version in ICALP’04. [doi:10.1016/j.tcs.2005.09.011]

[3]   Jin-Yi Cai and Xi Chen: Complexity of counting CSP with complex weights. In Proc. 44th STOC, pp. 909–920, New York, 2012. ACM Press. [doi:10.1145/2213977.2214059, arXiv:1111.2384]

[4]   Jin-Yi Cai, Xi Chen, and Pinyan Lu: Graph homomorphisms with complex values: A dichotomy theorem. SIAM J. Comput., 42(3):924–1029, 2013. Preliminary versions in ICALP’10 and arXiv. [doi:10.1137/110840194]

[5]   Xi Chen: Guest column: Complexity dichotomies of counting problems. SIGACT News, 42(4):54–76, 2011. [doi:10.1145/2078162.2078177]

[6]   Martin Dyer and Catherine Greenhill: The complexity of counting graph homomorphisms. Random Structures Algorithms, 17(3-4):260–289, 2000. Extended abstract in SODA’00, Corrigendum in Random Struct. Algorithms. [doi:10.1002/1098-2418(200010/12)17:3/4ˇ260::AID-RSA5ż3.0.CO;2-W]

[7]   Martin Dyer and David Richerby: The #CSP dichotomy is decidable. In Proc. 28th Symp. Theoretical Aspects of Comp. Sci. (STACS’11), volume 9 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 261–272. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2011. [doi:10.4230/LIPIcs.STACS.2011.261]

[8]   John Faben: The complexity of counting solutions to generalised satisfiability problems modulo k. In CoRR, 2008. [arXiv:0809.1836]

[9]   John Faben: The Complexity of Modular Counting in Constraint Satisfaction Problems. Ph. D. thesis, School of Mathematics, Queen Mary, University of London, 2012.

[10]   Andreas Göbel, Leslie Ann Goldberg, and David Richerby: The complexity of counting homomorphisms to cactus graphs modulo 2. ACM Trans. Comput. Theory, 6(4):17:1–17:29, 2014. Preliminary version in STACS’14. [doi:10.1145/2635825, arXiv:1307.0556]

[11]   Andreas Göbel, Leslie Ann Goldberg, and David Richerby: Counting homomorphisms to square-free graphs, modulo 2. Jan 2015. [arXiv:1501.07539]

[12]   Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley: A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput., 39(7):3336–3402, 2010. Preliminary versions in STACS’09 and arXiv. [doi:10.1137/090757496]

[13]   Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia: The complexity of weighted boolean #CSP modulo k. In Proc. 28th Symp. Theoretical Aspects of Comp. Sci. (STACS’11), volume 9 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 249–260. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2011. [doi:10.4230/LIPIcs.STACS.2011.249]

[14]   Pavol Hell and Jaroslav Nešetřil: On the complexity of H-coloring. J. Comb. Theory Ser. B, 48(1):92–110, 1990. [doi:10.1016/0095-8956(90)90132-J]

[15]   Pavol Hell and Jaroslav Nešetřil: Graphs and Homomorphisms. Oxford Univ. Press, 2004. Available from Oxford University Press.

[16]   Camille Jordan: Sur les assemblages de lignes. J. Reine Angew. Math., 1869(70):185–190, 1869. [doi:10.1515/crll.1869.70.185]

[17]    László Lovász: On the cancellation law among finite relational structures. Period. Math. Hungar., 1(2):145–156, 1971. [doi:10.1007/BF02029172]

[18]   László Lovász: Combinatorial Problems and Exercises. North-Holland Publishing Co., Amsterdam-New York, 1979.

[19]   Christos H. Papadimitriou and Stathis K. Zachos: Two remarks on the power of counting. In Theoret. Comput. Sci., volume 145, pp. 269–276, London, UK, 1982. Springer. [doi:10.1007/BFb0036487]

[20]   George Pólya: Kombinatorische Anzahlbestimmung für Gruppen, Graphen und chemische Verbindungen. Acta Math., 68(1):145–254, 1937. [doi:10.1007/BF02546665]

[21]    Leslie G. Valiant: The complexity of computing the permanent. Theoret. Comput. Sci., 8(2):189–201, 1979. [doi:10.1016/0304-3975(79)90044-6]

[22]   Leslie G. Valiant: Accidental algorithms. In Proc. 47th FOCS, pp. 509–517, Washington, DC, USA, 2006. IEEE Comp. Soc. Press. [doi:10.1109/FOCS.2006.7]