Which graph motif parameters count?

DOI10.4230/LIPICS.MFCS.2025.23MaRDI QIDQ7310185zbMATH OpenFDO

Authors Markus Bläser, Radu Curticapean, Julian Dörfler, Christian Ikenmeyer

Publication date 5 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2025.23

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A complexity theory for feasible closure properties
• Classes of bounded counting type and their inclusion relations
• Combinatorial Inequalities
• Computational complexity of counting coincidences
• Count on CFI graphs for \#P-hardness
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• Counting small induced subgraphs satisfying monotone properties
• Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders
• Functional closure properties of finite \(\mathbb{N}\)-weighted automata
• Homomorphisms are a good basis for counting small subgraphs
• How easy is local search?
• scientific article; zbMATH DE number 52121 (Why is no real title available?)
• scientific article; zbMATH DE number 1263206 (Why is no real title available?)
• scientific article; zbMATH DE number 1306902 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 1503622 (Why is no real title available?)
• scientific article; zbMATH DE number 863494 (Why is no real title available?)
• La correspondance de Robinson
• On the complexity of the parity argument and other inefficient proofs of existence
• Partitions of finite relational and set systems
• Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
• Ramsey's theorem for a class of categories
• Some hard families of parameterized counting problems
• Some inequalities in hom sets
• The Boolean Hierarchy II: Applications
• The complexity theory companion
• The parameterised complexity of counting connected subgraphs and graph motifs
• The parameterised complexity of counting even and odd induced subgraphs
• Ueber den Zusammenhang zwischen einigen Formen von symmetrischen Functionen.
• What is in \(\#\mathsf{P}\) and what is not?

This page was built for publication: Which graph motif parameters count?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7310185)