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]