Parameterized algorithms for $k$-Inversion
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908942035058688 |
|---|---|
| author | Antony, Dhanyamol Chandran, L. Sunil Jacob, Dalu Sandeep, R. B. |
| author_facet | Antony, Dhanyamol Chandran, L. Sunil Jacob, Dalu Sandeep, R. B. |
| contents | Inversion of a directed graph $D$ with respect to a vertex subset $Y$ is the directed graph obtained from $D$ by reversing the direction of every arc whose endpoints both lie in $Y$. More generally, the inversion of $D$ with respect to a tuple $(Y_1, Y_2, \ldots, Y_\ell)$ of vertex subsets is defined as the directed graph obtained by successively applying inversions with respect to $Y_1, Y_2, \ldots, Y_\ell$. Such a tuple is called a \emph{decycling family} of $D$ if the resulting graph is acyclic.
In the \textsc{$k$-Inversion} problem, the input consists of a directed graph $D$ and an integer $k$, and the task is to decide whether $D$ admits a decycling family of size at most $k$. Alon et al.\ (SIAM J.\ Discrete Math., 2024) proved that the problem is NP-complete for every fixed value of $k$, thereby ruling out XP algorithms, and presented a fixed-parameter tractable (FPT) algorithm parameterized by $k$ for tournament inputs.
In this paper, we generalize their algorithm to a broader variant of the problem on tournaments and subsequently use this result to obtain an FPT algorithm for \textsc{$k$-Inversion} when the underlying undirected graph of the input is a block graph. Furthermore, we obtain an algorithm for \textsc{$k$-Inversion} on general directed graphs with running time $2^{O(\mathrm{tw}(k + \mathrm{tw}))} \cdot n^{O(1)}$, where $\mathrm{tw}$ denotes the treewidth of the underlying graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_05528 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Parameterized algorithms for $k$-Inversion Antony, Dhanyamol Chandran, L. Sunil Jacob, Dalu Sandeep, R. B. Data Structures and Algorithms Inversion of a directed graph $D$ with respect to a vertex subset $Y$ is the directed graph obtained from $D$ by reversing the direction of every arc whose endpoints both lie in $Y$. More generally, the inversion of $D$ with respect to a tuple $(Y_1, Y_2, \ldots, Y_\ell)$ of vertex subsets is defined as the directed graph obtained by successively applying inversions with respect to $Y_1, Y_2, \ldots, Y_\ell$. Such a tuple is called a \emph{decycling family} of $D$ if the resulting graph is acyclic. In the \textsc{$k$-Inversion} problem, the input consists of a directed graph $D$ and an integer $k$, and the task is to decide whether $D$ admits a decycling family of size at most $k$. Alon et al.\ (SIAM J.\ Discrete Math., 2024) proved that the problem is NP-complete for every fixed value of $k$, thereby ruling out XP algorithms, and presented a fixed-parameter tractable (FPT) algorithm parameterized by $k$ for tournament inputs. In this paper, we generalize their algorithm to a broader variant of the problem on tournaments and subsequently use this result to obtain an FPT algorithm for \textsc{$k$-Inversion} when the underlying undirected graph of the input is a block graph. Furthermore, we obtain an algorithm for \textsc{$k$-Inversion} on general directed graphs with running time $2^{O(\mathrm{tw}(k + \mathrm{tw}))} \cdot n^{O(1)}$, where $\mathrm{tw}$ denotes the treewidth of the underlying graph. |
| title | Parameterized algorithms for $k$-Inversion |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.05528 |