Cargando…
Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness
We investigate the problem [Formula: see text] of counting all induced subgraphs of size k in a graph G that satisfy a given property [Formula: see text] . This continues the work of Jerrum and Meeks who proved the problem to be [Formula: see text] -hard for some families of properties which include...
| Autores principales: | , |
|---|---|
| Formato: | Online Artículo Texto |
| Lenguaje: | English |
| Publicado: |
Springer US
2020
|
| Materias: | |
| Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7416760/ https://www.ncbi.nlm.nih.gov/pubmed/32801408 http://dx.doi.org/10.1007/s00453-020-00676-9 |