BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T212001Z
UID:Seminar-ACTO-1008@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20220518T140000
DTEND:20220518T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Julian Dörfler: Counting Induced Subgraphs: An Algebraic Approach to #W[1]-Hardness\n\nWe study the problem #IndSub(ϕ) of counting all induced subgraphs of\n\nsize k in a graph G that satisfy the property ϕ. This was known to be\n\n#W[1]-hard for some families of properties ϕ including, among others,\n\nconnectivity, even- or oddness of the number of edges. We refine this\n\ntechnique for graph properties that are non-trivial on edge-transitive\n\ngraphs with a prime power number of edges. In particular, we fully\n\nclassify the case of monotone bipartite graph properties: It is shown\n\nthat, given any graph property ϕ that is closed under the removal of\n\nvertices and edges, and that is non-trivial for bipartite graphs, the\n\nproblem #IndSub(ϕ) is #W[1]-hard and cannot be solved in time f(k) *\n\nn^{o(k)} for any computable function f, unless the Exponential Time\n\nHypothesis fails.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1008
LOCATION:GHOLTH223
END:VEVENT
END:VCALENDAR