Counting Subgraphs in Somewhere Dense Graphs
summary
Classifies parameterized complexity of counting homomorphisms, (induced) subgraphs when both pattern and host classes are structured: FPT occurs exactly when pattern treewidth is bounded or hosts are nowhere dense (and induced-subgraph FPT only for finite pattern classes), otherwise sharp-W[1]-hard with ETH lower bounds. Hardness proofs reduce via the complexity monotonicity framework and a new edge-colored tensor product on subdivided graphs, and imply counting k-matchings is hard for every monotone somewhere-dense host class.
AI-written summary · about
chapters (10)
- 0:00Problem definitions
- 1:31Parameterization goals
- 3:53Existing dichotomies
- 6:18Restricting hosts and patterns
- 8:11Nowhere and somewhere density
- 13:04Main contributions
- 15:26Concrete case: k-matchings
- 17:02Hereditary class results
- 19:13Proof techniques
- 24:35Open problems
related talks
01h 05mHomomorphism Counts: Expressive Power and Query Algorithms
52mVariety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
01h 02mCounting Subgraphs in Sublinear Time
39mModel Counting Meets Distinct Estimation
53mData Deduplication For Redundant Graph Structures Files
33mLinear and sublinear algorithms for graphlet sampling
47mService Rates Of Mds Codes & Fractional Matchings In Quasi-Uniform Hypergraphs
29mFactorized Graph Neural Networks (With Some Algebraic Cheating)