Stability in Graphs with Matroid Constraints

Abstract We study the following Independent Stable Set problem. Let $$\varvec{G}$$ G be an undirected graph and $$\varvec{\mathcal {M}} \varvec{=} \varvec{(V(G),} \varvec{\mathcal {I})}$$ M = ( V ( G ) , I ) be a matroid whose elements are the vertices of $$\varvec{G}$$ G . For an integer $$\varvec{k}\varvec{\ge } \varvec{1}$$ k ≥ 1 , the task is to decide whether $$\varvec{G}$$ G contains a set $$\varvec{S}\varvec{\subseteq } \varvec{V(G)}$$ S ⊆ V ( G ) of size at least $$\varvec{k}$$ k which is independent (stable) in $$\varvec{G}$$ G and independent in $$\varvec{\mathcal {M}}$$ M . This problem generalizes several well-studied algorithmic problems, including Rainbow Independent Set , Rainbow Matching , and Bipartite Matching with Separation . We show that when the matroid $$\varvec{\mathcal {M}}$$ M is represented by an independence oracle, then for any computable function $$\varvec{f}$$ f , no algorithm can solve Independent Stable Set using $$\varvec{f(k)} \varvec{\cdot } \varvec{n}^{\varvec{o(k)}}$$ f ( k ) · n o ( k ) calls to the oracle. On the other hand, when the graph $$\varvec{G}$$ G