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

Taneli Mielikäinen (Taneli.Mielikaineniki.fi)
Esko Ukkonen (Esko.Ukkonencs.Helsinki.FI)

Abstract: 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.

Keywords: $NP$-Hardness, Inapproximability, Fixed-Parameter Intractability

Category 1: Combinatorial Optimization

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

Download: [PDF]

Entry Submitted: 02/11/2004
Entry Accepted: 02/11/2004
Entry Last Modified: 02/11/2004

Modify/Update this entry