Total Matching and Subdeterminants
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917556940439552 |
|---|---|
| author | Ferrarini, Luca Fiorini, Samuel Kober, Stefan Yuditsky, Yelena |
| author_facet | Ferrarini, Luca Fiorini, Samuel Kober, Stefan Yuditsky, Yelena |
| contents | In the total matching problem, one is given a graph $G$ with weights on the vertices and edges. The goal is to find a maximum weight set of vertices and edges that is the non-incident union of a stable set and a matching.
We consider the natural formulation of the problem as an integer program (IP), with variables corresponding to vertices and edges. Let $M = M(G)$ denote the constraint matrix of this IP. We define $Δ(G)$ as the maximum absolute value of the determinant of a square submatrix of $M$.
We show that the total matching problem can be solved in strongly polynomial time provided $Δ(G) \leq Δ$ for some constant $Δ\in \mathbb{Z}_{\ge 1}$. We also show that the problem of computing $Δ(G)$ admits an FPT algorithm. We also establish further results on $Δ(G)$ when $G$ is a forest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_17630 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Total Matching and Subdeterminants Ferrarini, Luca Fiorini, Samuel Kober, Stefan Yuditsky, Yelena Combinatorics Discrete Mathematics Data Structures and Algorithms Optimization and Control In the total matching problem, one is given a graph $G$ with weights on the vertices and edges. The goal is to find a maximum weight set of vertices and edges that is the non-incident union of a stable set and a matching. We consider the natural formulation of the problem as an integer program (IP), with variables corresponding to vertices and edges. Let $M = M(G)$ denote the constraint matrix of this IP. We define $Δ(G)$ as the maximum absolute value of the determinant of a square submatrix of $M$. We show that the total matching problem can be solved in strongly polynomial time provided $Δ(G) \leq Δ$ for some constant $Δ\in \mathbb{Z}_{\ge 1}$. We also show that the problem of computing $Δ(G)$ admits an FPT algorithm. We also establish further results on $Δ(G)$ when $G$ is a forest. |
| title | Total Matching and Subdeterminants |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2312.17630 |