{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigj5jrwhh6urur5hpt4j7am7p4g2iy7mh4yywq4fp4ufc57l6fvpq",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mpledzhoo2j2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.31803v1",
  "publishedAt": "2026-07-01T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Radu Curticapean",
    "Mingjun Liu"
  ],
  "textContent": "**Authors:** Radu Curticapean, Mingjun Liu\n\nJerrum and Meeks (TOCT, JCSS 2015) introduced the counting problems $\\text{IndSub}(Φ)$ for fixed graph properties $Φ$: Given an input graph $G$ and $k\\in\\mathbb N$, count the $k$-vertex subsets $S \\subseteq V(G)$ such that the induced subgraph $G[S]$ satisfies $Φ$. For recursively enumerable $Φ$, it is known that $\\text{IndSub}(Φ)$ is either #W[1]-hard or fixed-parameter tractable. A direct classification depending on $Φ$ however still remains open. In particular, the status was open for the property of graphs without nontrivial automorphisms, also mentioned in a very recent survey on parameterized counting by Roth (Comput.~Sci.~Rev.~2026). This is a natural property that evades all currently known techniques for proving #W[1]-hardness, including a general toolkit based on Fourier analysis that was very recently introduced by Curticapean and Neuen (SODA~2025). In this paper, we show that counting induced $k$-vertex graphs without nontrivial automorphisms is #W[1]-hard by constructing ``clique scaffolds'', i.e., problem-specific restrictions of the property that enable a reduction from the $k$-clique problem. More generally, we show that for every finite group $Q$, counting $k$-vertex induced subgraphs with automorphism group $Q$ is #W[1]-hard.",
  "title": "Counting Small Induced Subgraphs: Hardness of Symmetry-Based Properties"
}