  Perturbed graphic matroids are binary matroids that can be obtained from a
graphic matroid by adding a noise of small rank. More precisely, r-rank
perturbed graphic matroid M is a binary matroid that can be represented in the
form I +P, where I is the incidence matrix of some graph and P is a binary
matrix of rank at most r. Such matroids naturally appear in a number of
theoretical and applied settings. The main motivation behind our work is an
attempt to understand which parameterized algorithms for various problems on
graphs could be lifted to perturbed graphic matroids.
  We study the parameterized complexity of a natural generalization (for
matroids) of the following fundamental problems on graphs: Steiner Tree and
Multiway Cut. In this generalization, called the Space Cover problem, we are
given a binary matroid M with a ground set E, a set of terminals T\subseteq E,
and a non-negative integer k. The task is to decide whether T can be spanned by
a subset of E\setminus T of size at most k.
  We prove that on graphic matroid perturbations, for every fixed r, Space
Cover is fixed-parameter tractable parameterized by k. On the other hand, the
problem becomes W[1]-hard when parameterized by r+k+|T| and it is NP-complete
for r\leq 2 and |T|\leq 2.
  On cographic matroids, that are the duals of graphic matroids, Space Cover
generalizes another fundamental and well-studied problem, namely Multiway Cut.
We show that on the duals of perturbed graphic matroids the Space Cover problem
is fixed-parameter tractable parameterized by r+k.
