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) <= Delta for some constant Delta is an element of Z(>= 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.
Ferrarini, L., Fiorini, S., Kober, S., Yuditsky, Y. (2024). Total Matching and Subdeterminants. In Combinatorial Optimization 8th International Symposium, ISCO 2024, La Laguna, Tenerife, Spain, May 22–24, 2024, Revised Selected Papers (pp.192-204). SPRINGER INTERNATIONAL PUBLISHING AG [10.1007/978-3-031-60924-4_15].
Total Matching and Subdeterminants
Ferrarini L.;
2024
Abstract
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) <= Delta for some constant Delta is an element of Z(>= 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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
