This talk focuses on block-structured integer programs, in particular on n-fold IPs (where the constraint matrix has small, independent blocks linked together by few global constraints) and 2-stage stochastic IPs (where the constraint matrix has small, independent blocks linked together by few global variables). I will introduce this field and give an overview on the recent developments, focusing on our latest results: the parameterized tractability results for two-stage stochastic and n-fold programs persist even when one allows large entries in the global part of the program (SODA 24). This is joint work with Jana Cslovjecsek, Martin Koutecký, Alexandra Lassota, Michał Pilipczuk, Adam Polak.

This study introduces a new integer programming game named the edge-weighted budgeted
maximum coverage problem (EBMCP) game and proposes a new algorithm, the Best Response
Plus (BR plus) algorithm, for finding the best Pure Nash Equilibrium (PNE), with application
to aquatic invasive species (AIS) prevention. The EBMCP optimizes the allocation of inspectors
across lake networks to prevent the spread of AIS from infected to uninfected lakes. However,
significant challenges arise from differing objectives between state and county-level decision-makers.
To tackle these, we develop EBMCP games that model the strategic interactions among countylevel
stakeholders with two utility function variations. Furthermore, we demonstrate the existence
of a Pure Nash Equilibrium for both games with and without certain conditions. The Zero-Regret
algorithm has recently been proposed by (Dragotto and Scatamacchia, 2023) for enumerating and
selecting the PNEa in games with 2-3 players while its effectiveness for the IPG with many players
remains open. We tackle this problem by presenting the BR plus algorithm that utilizes the best
response dynamics, formally known as the standard method to find PNE in normal-form games.
Computational experiments show that our BR plus algorithm offers certain advantages over the ZR
algorithm, especially in larger games. Finally, we successfully apply the EBMCP game framework
to identify a PNE among county-level players in both single and multiple AIS scenarios, supporting
AIS prevention efforts in Minnesota.

A total matching of a graph G is a subset of G such that its elements, i.e. vertices and edges, are pairwise not adjacent. In this context, the Total Matching Problem (TMP) calls for a total matching of maximum size. This problem generalizes both the Stable Set Problem, where we look for a stable set of maximum size, and the Matching Problem, where instead we look for a matching of maximum size. In this talk, we consider the natural integer programming formulation of the TMP and study it through the prism of subdeterminants. First, we focus on the case of the forests. We give an alternative characterization of the maximum subdeterminant of the constraint matrix, as well as an approximation of it. Then, we switch to general graphs and give an FPT algorithm for computing the maximum subdeterminant. Finally, we show that the total matching problem can be solved in strongly polynomial time when the maximum subdeterminant is bounded by a constant.

It is a notorious open question whether integer programs (IPs), with an integer coefficient matrix M whose subdeterminants are all bounded by a constant in absolute value, can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from M, one obtains the transpose of a network matrix. We achieve our result in two main steps, the first related to the theory of IPs and the second related to graph minor theory. In this talk, we focus on the second part: We reformulate the problem as a maximum constrained integer potential problem on a minor-closed class of rooted graphs. We leverage this to obtain a tree-decomposition into highly structured graphs for which we can solve the problem locally, and combine the local solutions via dynamic programming.