TY - JOUR A1 - Göbel, Andreas A1 - Lagodzinski, Gregor J. A. A1 - Seidel, Karen T1 - Counting homomorphisms to trees modulo a prime JF - ACM transactions on computation theory : TOCT / Association for Computing Machinery N2 - Many important graph-theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article, we study the complexity of #(p) HOMSTOH, the problem of counting graph homomorphisms from an input graph to a graph H modulo a prime number p. Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo 2, however, the influence of the structure of H on the tractability was shown to persist, which yields similar dichotomies.
Our main result states that for every tree H and every prime p the problem #pHOMSTOH is either polynomial time computable or #P-p-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph H when counting modulo 2. In contrast to previous results on modular counting, the tractable cases of #pHOMSTOH are essentially the same for all values of the modulo when H is a tree. To prove this result, we study the structural properties of a homomorphism. As an important interim result, our study yields a dichotomy for the problem of counting weighted independent sets in a bipartite graph modulo some prime p. These results are the first suggesting that such dichotomies hold not only for the modulo 2 case but also for the modular counting functions of all primes p. KW - Graph homomorphisms KW - modular counting KW - complexity dichotomy Y1 - 2021 U6 - https://doi.org/10.1145/3460958 SN - 1942-3454 SN - 1942-3462 VL - 13 IS - 3 SP - 1 EP - 33 PB - Association for Computing Machinery CY - New York ER - TY - JOUR A1 - Schubarth, Wilfried A1 - Schulze-Reichelt, Friederike A1 - Mauermeister, Sylvi A1 - Seidel, Andreas A1 - Apostolow, Benjamin T1 - Studieneingang optimieren! BT - Empfehlungen zur Weiterentwicklung der Studieneingangsphase an Hochschulen JF - Alles auf Anfang! Befunde und Perspektiven zum Studieneingang Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-428605 SN - 978-3-86956-452-4 SN - 2192-1075 SN - 2192-1083 SP - 355 EP - 369 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Schubarth, Wilfried A1 - Schulze-Reichelt, Friederike A1 - Mauermeister, Sylvi A1 - Seidel, Andreas A1 - Hartmann, Nina T1 - Einführung in den Band JF - Alles auf Anfang! Befunde und Perspektiven zum Studieneingang Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-428342 SN - 978-3-86956-452-4 SN - 2192-1075 SN - 2192-1083 SP - 13 EP - 22 PB - Universtitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Seidel, Andreas T1 - (Weiter-)Entwicklung der Lehrerbildung im Land Brandenburg BT - Der Beitrag der Bildungswissenschaften in der Potsdamer Sekundarstufenlehrerausbildung JF - Potsdamer Beiträge zur Hochschulforschung Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-399709 SN - 978-3-86956-399-2 SN - 2192-1075 SN - 2192-1083 IS - 3 SP - 137 EP - 167 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Schubarth, Wilfried A1 - Mauermeister, Sylvi A1 - Seidel, Andreas T1 - Einführung: Debatten und Positionen zur Hochschulentwicklung JF - Potsdamer Beiträge zur Hochschulforschung Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-399372 SN - 978-3-86956-399-2 SN - 2192-1075 SN - 2192-1083 IS - 3 SP - 9 EP - 15 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Seidel, Andreas A1 - Gröger, Ulli A1 - Zylla, Birgitta T1 - Nachhaltige Prävention als Herausforderung BT - ein Tagungsbericht JF - Nachhaltige Prävention von Kriminalität, Gewalt und Rechtsextremismus : Beiträge aus Wissenschaft und Praxis N2 - 1. Das Besondere der Veranstaltung 2. Nachhaltige Kriminalprävention – Erkenntnisseaus den Vorträgen und Workshops 3. Fazit und Ausblick Literatur KW - Prävention KW - Nachhaltigkeit KW - Gewalt KW - Kriminalität KW - Rechtsextremismus KW - prevention KW - sustainability KW - violence KW - crime KW - right-wing extremism Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-71455 SP - 407 EP - 425 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Schubarth, Wilfried A1 - Speck, Karsten A1 - Seidel, Andreas A1 - Kamm, Caroline A1 - Kleinfeld, Merle A1 - Sarrar, Lea T1 - Evidenzbasierte Professionalisierung der Praxisphasen in außeruniversitären Lernorten BT - Erste Ergebnisse des Forschungsprojektes ProPrax JF - Potsdamer Beiträge zur Hochschulforschung Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-52687 SN - 2192-1075 SN - 2192-1083 IS - 1 SP - 79 EP - 212 ER - TY - JOUR A1 - Kopp, Andrea A1 - Schubarth, Wilfried A1 - Speck, Karsten A1 - Seidel, Andreas A1 - Kleinfeld, Merle A1 - Sarrar, Lea T1 - Vom Erkenntnisgewinn eines ExpertInnen-Workshops für die Hochschulpraxis JF - Potsdamer Beiträge zur Hochschulforschung Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-52782 SN - 2192-1075 SN - 2192-1083 IS - 1 SP - 319 EP - 335 ER - TY - JOUR A1 - Schubarth, Wilfried A1 - Speck, Karsten A1 - Seidel, Andreas T1 - Einführung in den Band JF - Potsdamer Beiträge zur Hochschulforschung Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-52650 SN - 2192-1075 SN - 2192-1083 IS - 1 SP - 3 EP - 4 ER - TY - JOUR A1 - Seidel, Andreas A1 - Schubarth, Wilfried A1 - Speck, Karsten T1 - Vereint in unsicheren Zeiten? : Eine Pilotstudie unter Jugendlichen in Ostdeutschland, Polen und Russland Y1 - 2011 SN - 978-3-86956-124-0 ER -