Can I read Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns on EtoBox?

Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns by Lassota, Alexandra; Ligthart, Koen is a scholarly article available to read on EtoBox.

What is Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns about?

We study integer linear programs (ILP) of the form $\min\{c^\top x\ \vert\ Ax=b,l\le x\le u,x\in\mathbb Z^n\}$ and analyze their parameterized complexity with respect to their distance to the generalized matching problem--following the well-established approach of capturing the hardness of a problem by the distance to triviality. The generalized matching problem is an ILP where each column of the constraint matrix has $1$-norm of at most $2$. It captures several well-known polynomial time solvable problems such as matching and flow problems. We parameterize by the size of variable and constraint backdoors, which measure the least number of columns or rows that must be deleted to obtain a generalized matching ILP. We present the following results: (i) a fixed-parameter tractable (FPT) algorithm for ILPs parameterized by the size $p$ of a minimum variable backdoor to generalized matching; (ii) a randomized slice-wise polynomial (XP) time algorithm for ILPs parameterized by the size $h$ of a minimum constraint backdoor to generalized matching as long as $c$ and $A$ are encoded in unary; (iii) we complement (ii) by proving that solving an ILP is W[1]-hard when parameterized by $h$ even

Author

Lassota, Alexandra; Ligthart, Koen

Published

2025

Language

EN