تقرير
Total Matching and Subdeterminants
| العنوان: | Total Matching and Subdeterminants |
|---|---|
| المؤلفون: | Ferrarini, Luca, Fiorini, Samuel, Kober, Stefan, Yuditsky, Yelena |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, Mathematics - 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 $\Delta(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 $\Delta(G) \leq \Delta$ for some constant $\Delta \in \mathbb{Z}_{\ge 1}$. We also show that the problem of computing $\Delta(G)$ admits an FPT algorithm. We also establish further results on $\Delta(G)$ when $G$ is a forest. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2312.17630 |
| رقم الأكسشن: | edsarx.2312.17630 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |