Description
Many combinatorial optimization problems involve additional constraints, including parity, congruence, and exact-weight constraints. These constraints can be expressed in a unified way by considering a labeling of the underlying set by the elements of a group, and looking for a solution where the sum of the labels of its entries is a prescribed group element. A special case of interest is when the prescribed element is 0, which we refer to as the zero constraint. Furthermore, in path and cycle problems on graphs, the non-zero constraint is also of interest.
Matroids play a fundamental role in combinatorial optimization. However, the study of zero and non-zero constraints in matroid problems has received surprisingly little attention. Our research aims to fill this gap by developing a theory of zero and non-zero constraints in matroid optimization. More concretely, we focus on the Zero Basis, Non-Zero Basis, Zero Common Basis, and Non-Zero Common Basis problems, and we also consider their weighted extensions. Our main goal is to decide which problems are hard, and which can be solved in polynomial time.
While finding a non-zero basis and a minimum-weight non-zero basis is not difficult, it turns out that the tractability of the Non-Zero Common Basis problem highly depends on the structure of the group. Specifically, a polynomial-time algorithm exists if and only if the group has no element of order two. In contrast, we prove that the weighted case is hard for any nontrivial group. The problem of finding zero bases and zero common bases turns out to be more difficult than
finding their non-zero counterparts.
I will finish my talk with some interesting generalizations and open problems. Joint work with Florian Hörsch, Taihei Oki and Tamás Schwarcz.