4 papers
Counting Small Induced Subgraphs: Hardness of Symmetry-Based Properties
Radu Curticapean, Mingjun Liu
Jerrum and Meeks (TOCT, JCSS 2015) introduced the counting problems for fixed graph properties : Given an input graph and , count the -v…
Retrieving Minimal and Sufficient Reasoning Subgraphs with Graph Foundation Models for Path-aware GraphRAG
Haonan Yuan, Qingyun Sun, Junhua Shi +5
Graph-based retrieval-augmented generation (GraphRAG) exploits structured knowledge to support knowledge-intensive reasoning. However, most existing methods treat graphs as interme…
Some remarks on the uncolored versions of the original CFI-graphs
Yijia Chen, Jörg Flum, Mingjun Liu
The CFI-graphs, named after Cai, Fürer, and Immerman, are central to the study of the graph isomorphism testing and of first-order logic with counting. They are colored graphs, and…
On Algorithms Based on Finitely Many Homomorphism Counts
Yijia Chen, Jörg Flum, Mingjun Liu +1
It is well known [Lovász, 67] that up to isomorphism a graph~ is determined by the homomorphism counts , i.e., the number of homomorphisms from to , where …