The Complexity of Maximum Matroid-Greedoid Intersection and Weighted Greedoid Maximization

The maximum intersection problem for a matroid and a greedoid, given by polynomial-time oracles, is shown $NP$-hard by expressing the satisfiability of boolean formulas in $3$-conjunctive normal form as such an intersection. The corresponding approximation problems are shown $NP$-hard for certain approximation performance bounds. Moreover, some natural parameterized variants of the problem are shown $W[P]$-hard. The results are in contrast with the maximum matroid-matroid intersection which is solvable in polynomial time by an old result of Edmonds. We also prove that it is $NP$-hard to approximate the weighted greedoid maximization within $2^{n^{O(1)}}$ where $n$ is the size of the domain of the greedoid.

Citation

unpublished: Report C-2004-2, Department of Computer Science, University of Helsinki, Finland

Article

Download

View The Complexity of Maximum Matroid-Greedoid Intersection and Weighted Greedoid Maximization