On Detecting $H$-Induced Minors for Small $H$
We consider the $H$-Induced Minor problem: for a fixed graph~$H$, decide whether a given graph $G$ contains $H$ as an induced minor. While the problem is known to be NP-complete for some trees~$H$ on more than $2^{300}$ vertices, the complexity for small trees remains unresolved. In particular, the case where $H$ is the $7$-vertex tree consisting of a path on five vertices with a pendant vertex attached to the second and fourth vertex was a long-standing open problem. We show that this case is polynomial-time solvable by developing algorithms that detect a sequence of carefully chosen…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.24216
curl -X POST /api/v1/records/arxiv/2604.24216/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.24216/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'