{"ID":2834622,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.01900","arxiv_id":"2512.01900","title":"Tight Bounds for Feedback Vertex Set Parameterized by Clique-width","abstract":"We introduce a new notion of acyclicity representation in labeled graphs, and present three applications thereof. Our main result is an algorithm that, given a graph $G$ and a $k$-clique expression of $G$, in time $O(6^kn^c)$ counts modulo $2$ the number of feedback vertex sets of $G$ of each size. We achieve this through an involved subroutine for merging partial solutions at union nodes in the expression. In the usual way this results in a one-sided error Monte-Carlo algorithm for solving the decision problem in the same time. We complement these by a matching lower bound under the Strong Exponential-Time Hypothesis (SETH). This closes an open question that appeared multiple times in the literature [ESA 23, ICALP 24, IPEC 25]. We also present an algorithm that, given a graph $G$ and a tree decomposition of width $k$ of $G$, in time $O(3^kn^c)$ counts modulo $2$ the number of feedback vertex sets of $G$ of each size. This matches the known SETH-tight bound for the decision version, which was obtained using the celebrated cut-and-count technique [FOCS 11, TALG 22]. Unlike other applications of cut-and-count, which use the isolation lemma to reduce a decision problem to counting solutions modulo $2$, this bound was obtained via counting other objects, leaving the complexity of counting solutions modulo $2$ open. Finally, we present a one-sided error Monte-Carlo algorithm that, given a graph $G$ and a $k$-clique expression of $G$, in time $O(18^kn^c)$ decides the existence of a connected feedback vertex set of size $b$ in $G$. We provide a matching lower bound under SETH.","short_abstract":"We introduce a new notion of acyclicity representation in labeled graphs, and present three applications thereof. Our main result is an algorithm that, given a graph $G$ and a $k$-clique expression of $G$, in time $O(6^kn^c)$ counts modulo $2$ the number of feedback vertex sets of $G$ of each size. We achieve this thro...","url_abs":"https://arxiv.org/abs/2512.01900","url_pdf":"https://arxiv.org/pdf/2512.01900v1","authors":"[\"Narek Bojikian\",\"Stefan Kratsch\"]","published":"2025-12-01T17:21:12Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}