Denis Cornaz: Some almost matroids are hard

Thursday January 12, 2023 at 10am. (room Espace One, Paris Dauphine)

Denis Cornaz (Paris Dauphine University)

Title: Some almost matroids are hard

Abstract:

A non-empty collection of subsets of a finite set form the set of the bases of an almost-matroid, if every subset A of the collection has the property that : for every x not in A, there is a y in A, so that A U {x} \ {y} is still in the collection.

We prove that, in contrast with the greedy algorithm of matroids, even with a given membership oracle, it is NP-hard to find a maximum weighted set over almost-matroids. This is proved by defining a sequential game on graphs.