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

Original · EN

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ⁿᵒ⁽¹⁾ where n is the size of the domain of the greedoid. A preliminary version ``The Complexity of Maximum Matroid-Greedoid Intersection'' appeared in Proc. FCT 2001, LNCS 2138, pp. 535--539, Springer-Verlag 2001.