Parameterized counting and Cayley graph expanders
Given a graph property Φ, we consider the problem # EdgeSub (Φ), where the input is a pair of a graph G and a positive integer k, and the task is to compute the number of k-edge subgraphs in G that satisfy Φ. Specifically, we study the parameterized complexity of # EdgeSub (Φ) with respect to both a...
| Main Authors: | , , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2023
|