Using matroids to solve subset sum.
The (Decision) Subset Sum Problem:
Given a set of integers S, does there exist a subset of S whose elements sum to k?
Better definition here
Let I be the set of all sets in S which do not sum to k.
Define a matroid of independent sets on I.
Clearly,
- the empty set is in I
- for all X in I, X' \subset X, X' is obviously in I (only if all elements in the ground set are positive)
- if X, X' \in I, and |X| > |X'|, then it is trivial to prove that there exists at least one element e \in X, s.t X' U e \in I.
Hence this is a well defined matroid. Perhaps we can do something with this?
Since we can solve MST, we have a polynomial time algorithm to find a maximal independent set in I. Can we leverage this and duality to get a nice solution to subset sums? Particularly, a polynomial time algorithm to find such as subset if it exists?