FPT algorithms over linear delta-matroids with applications
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929720148361216 |
|---|---|
| author | Eiben, Eduard Koana, Tomohiro Wahlström, Magnus |
| author_facet | Eiben, Eduard Koana, Tomohiro Wahlström, Magnus |
| contents | Matroids, particularly linear ones, have been a powerful tool in parameterized complexity for algorithms and kernelization. They have sped up or replaced dynamic programming. Delta-matroids generalize matroids by encapsulating structures such as non-maximum matchings in general graphs and various path-packing and topological configurations. Linear delta-matroids (represented by skew-symmetric matrices) offer significant expressive power and enable powerful algorithms. We investigate parameterized complexity aspects of problems defined over linear delta-matroids or with delta-matroid constraints. Our analysis of basic intersection and packing problems reveals a different complexity landscape compared to the familiar matroid case. In particular, there is a stark contrast between the cardinality parameter $k$ and the rank parameter $r$. For example, finding an intersection of size $k$ of three linear delta-matroids is W[1]-hard when parameterized by $k$, while more general problems (e.g., finding a set packing of size $k$ feasible in a linear delta-matroid) are FPT when parameterized by $r$. We extend the recent determinantal sieving procedure of Eiben, Koana and Wahlström (SODA 2024) to sieve a polynomial for a monomial whose support is feasible in a linear delta-matroid by $r$.
Second, we investigate a class of problems that remains FPT when parameterized by $k$, even on delta-matroids of unbounded rank. We begin with Delta-matroid Triangle Cover - finding a feasible set of size $k$ that can be covered by a vertex-disjoint packing of triangles (sets of size 3) from a given collection. This approach allows us to find a packing of $K_3$'s and $K_2$'s in a graph with a maximum number of edges, parameterized above the matching number. As applications, we settle questions on the FPT status of Cluster Subgraph and Strong Triadic Closure parameterized above the matching number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13654 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | FPT algorithms over linear delta-matroids with applications Eiben, Eduard Koana, Tomohiro Wahlström, Magnus Data Structures and Algorithms Matroids, particularly linear ones, have been a powerful tool in parameterized complexity for algorithms and kernelization. They have sped up or replaced dynamic programming. Delta-matroids generalize matroids by encapsulating structures such as non-maximum matchings in general graphs and various path-packing and topological configurations. Linear delta-matroids (represented by skew-symmetric matrices) offer significant expressive power and enable powerful algorithms. We investigate parameterized complexity aspects of problems defined over linear delta-matroids or with delta-matroid constraints. Our analysis of basic intersection and packing problems reveals a different complexity landscape compared to the familiar matroid case. In particular, there is a stark contrast between the cardinality parameter $k$ and the rank parameter $r$. For example, finding an intersection of size $k$ of three linear delta-matroids is W[1]-hard when parameterized by $k$, while more general problems (e.g., finding a set packing of size $k$ feasible in a linear delta-matroid) are FPT when parameterized by $r$. We extend the recent determinantal sieving procedure of Eiben, Koana and Wahlström (SODA 2024) to sieve a polynomial for a monomial whose support is feasible in a linear delta-matroid by $r$. Second, we investigate a class of problems that remains FPT when parameterized by $k$, even on delta-matroids of unbounded rank. We begin with Delta-matroid Triangle Cover - finding a feasible set of size $k$ that can be covered by a vertex-disjoint packing of triangles (sets of size 3) from a given collection. This approach allows us to find a packing of $K_3$'s and $K_2$'s in a graph with a maximum number of edges, parameterized above the matching number. As applications, we settle questions on the FPT status of Cluster Subgraph and Strong Triadic Closure parameterized above the matching number. |
| title | FPT algorithms over linear delta-matroids with applications |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.13654 |