\begin{document}
\maketitle

\begin{abstract}
  \looseness=-1
  We consider
  a variant
  of the matroid median
  problem introduced by
  Krishnaswamy et al.\ [SODA 2011]:
  an
  uncapacitated discrete facility location problem
  where
  the task is to
  decide which facilities to open
  and which clients to serve
  for maximum profit
  so that
  the facilities form an independent set
  in given facility-side matroids
  and
  the clients form an independent set
  in given client-side matroids.
  We show that the problem is
  fixed\hyp parameter tractable
  parameterized by the number of matroids
  and the minimum rank among the client-side matroids.
  To this end,
  we derive fixed\hyp parameter algorithms
  for computing representative families
  for matroid intersections

  and maximum\hyp weight
  set packings with multiple matroid constraints.
  To illustrate
  the modeling capabilities
  of the new problem,
  we use it to obtain
  algorithms for
  
  a problem in
  
  
  social network analysis.
  
  
  
  
  We
  complement our tractability
  results by lower bounds.
\end{abstract}

\keywords{matroid set packing
  · matroid parity
  · matroid median
  · representative families
  · social network analysis
  · strong triadic closure}


\section{Introduction}
\label{sec:introduction}
The uncapacitated facility location problem (UFLP),
also known as the simple plant location problem,
is a classical problem studied
in operations research \citep{LNG15}
and models the following task:
a~company has to decide
where to open facilities
in order to serve its clients.
Opening a facility incurs a cost,
whereas serving clients
yields profit for the company.
The task is
to decide
where to open facilities

so as to maximize
the profit
minus the cost for opening facilities.

\paragraph{Uncapacitated facility location problem
  with matroid constraints.}
Numerous 

algorithms
have been developed for the UFLP
\citep[Section~3.4]{LNG15}.
Yet in practice,
the required solutions
are often subject to additional side constraints 
\citep{LNG15},
which make 
algorithms for the pure UFLP inapplicable.
For example:
\begin{itemize}
\item\label{ex1}
  The number of facilities
  in each of several, possibly overlapping areas
  is limited
  (environmental protection,
  precaution against terrorism or sabotage).
  
  
  
  
  
\item Facilities may be subject to move \citep{Swa16}.
\item\label{ex2}
  For each client,
  we may choose
  one of several locations
  to serve it at,
  
  which influences the
  profit
  
  
  
  (like in the
  job interval selection problem \citep{NH82,HK06,BMNW15}).
  
\item\label{ex3}
  Serving a client
  requires a subset of
  several kinds of resources,
  where
  the number of clients servable
  by each kind of resource is limited.
  
  
  
  
  

\end{itemize}
\noindent
In order to
analyze the influence
of such constraints
on the complexity of UFLP
and to
capture such constraints
in a single algorithm,
we introduce

  
the following uncapacitated facility location
problem with matroid constraints (\mdmc{}).
\begin{problem}[\mdmc{}]\leavevmode
  \label[problem]{prob:mdmc}
  \begin{compactdesc}
  \item[\normalfont\textit{Input:}]
    A universe~\(U\)
    with \(n:=|U|\),
    for each pair~\(u,v\in U\)
    a \emph{profit} \(p_{uv}\in\mathbb N\)
    obtained when
    a facility at~\(u\) serves a client at~\(v\),
    for each~\(u\in U\)
    a \emph{cost}~\(c_u\in\mathbb N\)
    for opening a facility at~\(u\),
    \emph{facility matroids} \(\{(U_i,A_i)\}_{i=1}^a\),
    and
    \emph{client matroids}~\(\{(V_i,C_i)\}_{i=1}^c\),
    where~\(U_i\cup V_i\subseteq U\).
  \item[\normalfont\textit{Task:}]
    Find two disjoint sets \(A\uplus C\subseteq U\)
    that maximize the \emph{profit}
    \begin{align}
      \sum_{v\in C}\max_{u\in A}p_{uv}-\sum_{u\in A}c_u&&
\text{such that}&&A&\in\bigcap_{i=1}^a A_i&&\text{and}&&C\in\bigcap_{i=1}^c C_i.\label{mdmcgf}
    \end{align}
  \end{compactdesc}
\end{problem}


\noindent
Besides modeling
natural facility location scenarios
like the ones described above,
\mdmc{}


generalizes several
well\hyp known
combinatorial optimization problems.
\begin{example}
  \label[example]{ex:maxcover}
  Using
  \mdmc{}
  with \(a=1\) facility matroid
  and \(c=0\) client matroids
  one can model
  the classical NP-hard
  problem \citep{Kar72}
  of covering a maximum number of elements
  of a set~\(V\)
  using at most \(r\)~sets
  of a collection~\(\cH\subseteq 2^V\).
  
  
  To this end,
  choose
  the universe~\(U=V\cup \cH\),
  a single facility matroid~\((\cH,A_1)\)
  with
  \(A_1:=\{H\subseteq \cH\mid |H|\leq r\}\),
  \(c_u=0\) for each \(u\in U\),
  and,
  for each \(u,v\in U\),
  \begin{align*}
    p_{uv}&=
            \begin{cases}
              1&\text{ if $u\in \cH$ such that $v\in u$,}\\
              0&\text{ otherwise}.
            \end{cases}
  \end{align*}
\end{example}

\noindent
Already UFLP
(without matroid constraints)


does not allow for
polynomial\hyp time approximation schemes
unless P\({}={}\)NP \citep{AS99}.
Moreover,
from \cref{ex:maxcover}
and the W[2]-hardness
of \textsc{Set Cover} \citep{CFK+15},
it immediately follows that \mdmc{}
is W[2]-hard parameterized by~$r$
even for zero costs,
binary profits,
and a single facility matroid~$r$,
making even the problem
of optimally
placing a \emph{small} number~\(r\)
of facilities hard
when the set of clients is unconstrained.


Thus,
we aim for solving the problem
optimally 


when
the number of \emph{clients} to serve is small.
Facility location problems
with a small (even constant) number of clients
have been studied before \citep{ABGL15}
and also have several applications:


\begin{itemize}
\item When clients are not end customers,
  but in the middle of the supply chain,
  then
  their number may indeed be small.
  For example,
  there are many possible locations
  for waste\hyp to\hyp energy
  
  plants,
  yet clients
  are a few city waste dumps.
  \footnote{
    The State Register
    of Waste Disposal Facilities
    of the Russian Federation
    lists 18~dumps
    for municipal solid waste
    in Moscow region---the 
    largest city of Europe.}
  
\item In the stop location problem \citep{SHLW09},
  the clients correspond to cities
  that are served by
  new train stops to be built
  along existing rail infrastructure.
  
\item Due to resource constraints
  or due to the constraint
  that each client
  be served at only one
  of several possible locations,
  the number of actually served
  clients may be small
  compared to the number of
  possible client and facility locations.
\end{itemize}
\looseness=-1
To optimally solve \mdmc{}
when the number of served clients
is small (not necessarily constant),
we employ \emph{fixed\hyp parameter algorithms}
and thus contribute to the
still relatively scarce
results
on the parameterized complexity
of problems in operations research,
so far mainly concerned with scheduling \citep{MB18},
routing \citep{BNSW14,BKS17,GWY17,GJW16,GJS17,KM14,MB18},
packing \citep{JKMS13,Jan10,AGRY16},
yet to a lesser extent with facility location \citep{FF11}.

\paragraph{Parameterized complexity.}
The main idea of fixed\hyp parameter algorithms
is to accept the exponential running time
seemingly inherent to solving NP-hard problems,
yet to confine the combinatorial explosion
to a parameter of the problem,
which can be small in applications~\citep{CFK+15}.
A problem is \emph{fixed\hyp parameter tractable}
if it can be solved in \(f(k)\cdot \poly(n)\)~time
on inputs of length~\(n\)
and some function~\(f\)
depending only on some parameter~\(k\).
Note that
this requirement is stronger than


an algorithm
that merely runs in polynomial time
for fixed~\(k\),
say, in \(O(n^k)\)~time,
which is intractable even for small values of~\(k\).


\looseness=-1
The parameterized analog
of NP and NP-hardness
is the $W$-hierarchy \(\FPT\subseteq\Wone\subseteq\Wtwo\subseteq\dots W[P]\subseteq\text{XP}\) and \(W[t]\)-hardness,
where \FPT{} is the class of
fixed\hyp parameter tractable
decision problems and
all inclusions are conjectured to be strict.


If some \(W[t]\)-hard problem
is in \FPT,
then \(\FPT=W[t]\)~\citep{CFK+15}.

\subsection{Our contributions and organization of this work}
We introduce

  
\mdmc{}
and prove first algorithmic results
(we refer the reader to \cref{sec:preliminaries}
for basic definitions from matroid theory).
\begin{theorem}
  \label{thm:alg}
  \mdmc{} is
  \begin{enumerate}[(i)]
  \item\label{thm:alg1}
    solvable in \(2^{\bigO(r\log r)}\cdot n^2\)~time
    for
    
    a single facility matroid
    given as an independence oracle
    and a single uniform client matroid
    
    of rank~\(r\).
  \item\label{thm:alg2}
    \looseness=-1
    fixed\hyp parameter tractable parameterized by \(a+c+r\),
    where \(r\)~is the minimum rank
    of the client matroids
    and representations of all matroids
    over the same finite
    field~\(\F_{p^d}\) are given
    
    
    for some prime~\(p\) polynomial in 
    
    the input size.
    
    
    
    

  \end{enumerate}
\end{theorem}


\noindent
We point out that,
if our aim is
to maximize the profit from
serving only \(k\)~clients,
then we can always
add a uniform client matroid of rank~\(k\)

and \cref{thm:alg}\eqref{thm:alg2}
gives a fixed\hyp parameter algorithm
for the parameter~\(a+c+k\).
In contrast,
recall that
\cref{ex:maxcover}
already shows that
one cannot replace~\(r\)
by the minimum rank of \emph{all} matroids
in \cref{thm:alg}\eqref{thm:alg2}.


To illustrate the modeling capabilities
of the newly introduced problem,


in \cref{sec:app},
we use \cref{thm:alg}
to obtain fixed\hyp parameter algorithms
for a problem in social network analysis,
complementing known approximation results.


In \cref{sec:tools},
we develop results
of independent interest
to matroid optimization,
like fixed\hyp parameter algorithms
for computing
\emph{representative families
  for matroid intersections}
with respect to \emph{\dtex{} weight functions}
and for maximum\hyp weight set packings
subject to several matroid constraints.

In \cref{sec:algorithm},
we use these results to
prove \cref{thm:alg}.
In \cref{sec:hardness},
we show that
\cref{thm:alg}\eqref{thm:alg2}
does not generalize to non\hyp representable
client matroids:
\begin{theorem}
  \label[theorem]{thm:hard}
  \mdmc{}
  even with unit costs,
  binary profits,
  without facility matroids,
  and a single (non\hyp representable) client matroid
  of rank~\(r\)
  is
  W[1]-hard parameterized by~\(r\).
\end{theorem}


\subsection{Related work}
\label{sec:relwork}
\paragraph{Uncapacitated facility location.}
The literature
usually studies the 
variant where
each facility~\(u\) has an opening cost~\(c_u\),
serving client~\(v\) by facility~\(u\) costs~\(p_{uv}\),
and one \emph{minimizes} the total cost
of serving \emph{all} clients.
\citet{FF11} show that
this problem
is fixed\hyp parameter tractable
when parameterized by an upper bound
on the optimum solution cost,
yet W[2]\hyp hard when parameterized
by the number of facilities that may be opened.
\citet{KKN+14} and \citet{Swa16}
study approximation algorithms
for the minimization problem
where the set of facilities
is required to be independent in
a single facility matroid
(there are no client matroids)
and show several applications.
\citet{Kal18} additionally
studies capacity constraints on facilities.
In case where the clients
also have to obey matroid constraints,
the minimization problem is meaningless:

the minimization variant of \mdmc{}
would simply
not serve clients and not open facilities.
Thus,
we study the problem
of \emph{maximizing} total profit
minus facility opening costs.
For this problem
(without matroid constraints),
\citet{AS99} show
a 0.828\hyp approximation
and that there is no polynomial\hyp time
approximation scheme.


\paragraph{Combinatorial optimization with matroid constraints.}
\looseness=-1
\citet{FW12} study
the \textsc{Maximum Coverage} problem
with a matroid constraint
and give a \((1-1/e)\)-approximation.
A construction
similar to \cref{ex:maxcover}
shows that this problem is a special case
of \mdmc{}.
\citet{CCPV11} give a \((1-1/e)\)-approximation for maximizing
a monotone submodular function
under a matroid constraint.
This problem is incomparable to ours,
since the goal function of \mdmc{}
is not submodular
yet cannot model
all submodular functions either.
\citet{LSV13} provide
approximation schemes
for \textsc{Set Packing} with a matroid constraint,
which is a generalization
of the \textsc{Matroid Matching}
and \textsc{Matroid Parity} problems
introduced by \citet{Law76}
as generalization of the \textsc{2-Matroid Intersection}
problem.
Towards proving
\cref{thm:alg},
we obtain fixed\hyp parameter
tractability result
for \textsc{Weighted Set Packing}
subject to multiple matroid constraints.


\paragraph{Matroids in parameterized complexity.}
\looseness=-1
Matroids are
an important tool
in the development
of fixed\hyp parameter algorithms~\citep{PS16}.
Many of these algorithms are based
on 

so\hyp called \emph{representative families} for
 matroids \citep{Mar09,FLPS16},
which we will generalize to
representative families for
weighted matroid \emph{intersections}.
In particular,
\citet{Mar09}
used representative families 
in randomized
fixed\hyp parameter algorithms
for the NP-hard
\textsc{Matroid Intersection} problem---a special case
of \mdmc{}.
We build on these
results of \citet{Mar09},
which have subsequently
been generalized to weighted variants
by \citet{FLPS16}
and derandomized
by \citet{LMPS18}.

\paragraph{\cref{thm:alg} generalizes
known fixed\hyp parameter tractability results.}
\citet{Mar09} showed
that a common independent set
of size~\(r\) in \(m\)~matroids
can be found in \(f(r,m)\cdot\poly(n)\)~time.
Our \cref{thm:alg}\eqref{thm:alg2}
is a direct generalization of this result
(one can add a uniform client matroid
of rank~\(r\)
to \mdmc{}).


\citet{BPS16} showed that
the problem of covering
at least \(p\)~elements of a set~\(V\)
using at most \(k\)~sets of a given
family~\(\cH\subseteq 2^V\)
is fixed\hyp parameter tractable
parameterized by~\(p\).
This result also follows
from our \cref{thm:alg}\eqref{thm:alg1}
using \cref{ex:maxcover} with an
additional uniform client matroid of rank~\(p\).
Earlier,
\citet{Mar08} showed that
\textsc{Partial Vertex Cover}
(can one cover at least \(p\)~edges of a graph by at most \(k\)~vertices?)
is fixed\hyp parameter tractable by~\(p\).
Our \cref{thm:alg} generalizes this result
and, indeed,
is based on the color coding
approach in \citeauthor{Mar08}'s \citep{Mar08} algorithm.


  


  


\section{Preliminaries}

\label{sec:preliminaries}


\looseness=-1
By \(\N\),
we denote the naturals numbers
including zero.
By \(\F_p\),
we denote the field
on \(p\)~elements.


By
\(n=|U|\),
we denote the size of the universe
(matroid ground set).

\subsection{Sets and set functions}

By \(A\uplus B\),
we denote the union of sets~\(A\) and~\(B\)
that we require to be disjoint.
By convention,
the intersection of no sets is the whole universe
and the union of no sets is the empty set.

\begin{definition}[partition]
  We call \(Z_1,\dots,Z_\ell\) a \emph{partition} of a set~\(A\)
  if \(Z_1\uplus\dots\uplus Z_\ell=A\)
  and \(Z_i\ne\emptyset\) for each~\(i\in\{1,\dots,\ell\}\).
\end{definition}

\begin{definition}[\boldmath\(\gam\)-family]
We call \(A\subseteq 2^U\)
an \emph{\(\gam\)}-family
if each set in~\(A\) has cardinality
exactly~\(\gam\).
\end{definition}


\begin{definition}[additive and
  submodular

  set functions]
  A set function \(w\colon 2^U\to\R\)
  is \emph{additive} if,
  for any subsets~\(A\cup B\subseteq U\),
  one has
  \[
  w(A\cup B)=w(A)+w(B)-w(A\cap B).
  \]
  If ``$\leq$'' holds instead of equality,
  then \(w\)~is called \emph{submodular}.
  
  
\end{definition}

\begin{definition}[coverage function]
  \label{def:covfunc}
  A set function
  \[
    w\colon 2^U\to\mathbb N,S\mapsto\Bigl|\bigcup_{u\in S}u\Bigr|,
  \]
  where \(U=2^V\), is a \emph{coverage function}.
\end{definition}

\noindent
Coverage functions are non\hyp decreasing
and submodular \citep[Section~44.1a]{Sch03}.

\subsection{Matroid fundamentals}
For proofs of the following propositions
and for illustrative examples
of the following definitions,
we refer to the book of \citet{Oxl92}.

\begin{definition}[matroid]
  \label[definition]{def:matroid}
  A pair $(U,\I)$,
  where $U$~is the \emph{ground set}
  and $\I\subseteq 2^U$ is a family of \emph{independent sets},
  is a \emph{matroid} if the following holds:
  \begin{itemize}
  \item  $\emptyset \in \I$,
  \item  If $A' \subseteq A$ and $A \in \I$, then $A' \in \I$.
  \item  If $A,B \in \I$ and $|A| < |B|$, then there is an $x \in B \setminus A$ such that $A \cup \{x\} \in \I$.
  \end{itemize}
\end{definition}

\begin{definition}[basis, rank]
  An inclusion\hyp wise
  maximal independent set~\(A\in \I\)
  of a matroid~\(M=(U,\I)\)
  is a \emph{basis}.
  The cardinality
  of the bases of~\(M\)
  is
  called the \emph{rank} of~\(M\).
\end{definition}


\begin{definition}[free matroid]
  A \emph{free matroid} is a matroid~\((U,2^U)\)
  in which every set is independent.
\end{definition}

\begin{proposition}[dual matroid]
  Each matroid~\(M\)
  has a \emph{dual matroid~\(M^*\)}
  whose bases are
  the complements of bases of~\(M\).

\end{proposition}


\begin{proposition}[matroid union, direct sum] 
  \label{def:matunion}
  \label{def:union}
  The \emph{union}
  \[M_1\vee M_2=(U_1\cup U_2, \{J_1\cup J_2\mid J_1\in I_1,J_2\in I_2\})\]
  of two matroids \(M_1=(U_1,I_1)\) and \(M_2=(U_2,I_2)\)
  is a matroid.
   If \(U_1\cap U_2=\emptyset\),
   we write \(M_1\oplus M_2:=M_1\vee M_2\)
   and call their union \emph{direct sum}.
\end{proposition}


\begin{definition}[uniform, partition, and multicolored matroids]
  A \emph{uniform matroid of rank~\(r\)}
  is a matroid~\((U,\I)\)
  such that \(\I:=\{S\subseteq U\mid |S|\leq r\}\).
  The direct sum of uniform matroids
  is called \emph{partition matroid}.
  We call the direct sum of
  uniform matroids
  of rank one
  a \emph{multicolored matroid}.
\end{definition}

\noindent
Partition matroids are useful
to model constraints
of type ``at most \(k_i\)~items of type~\(i\)''
and thus model both
the territorial constraints on facilities
as well as the resource constraints
on clients
sketched in \cref{sec:introduction}.
\subsection{Matroid representations}
In our work,
we will use two different
ways of representing matroids.


An \emph{independence oracle}
is an algorithm that
answers in constant time
whether a given set
is independent in a given matroid.
One can imagine it
as an algorithm
that decides independence quickly.
We will also use \emph{linear representations}:

\begin{definition}[linear/representable matroids]
  A matroid~\(M=(U,\I)\)
  is \emph{representable over a field \(\F\)}
  if there is a matrix~\(A\)
  with \(n\)~columns
  labeled by elements of~\(U\)
  such that \(S\in \I\)
  if and only if
  the columns of~\(A\)
  with labels in~\(S\)
  are linearly independent over~\(\F\).

  If \(A\)~is an \((r\times n)\)-matrix,
  
  
  
  we call it an \emph{\((r\times n)\)-representation} of~\(M\).
  A matroid is \emph{linear} or \emph{representable}
  if it is representable over some field.
\end{definition}
\noindent
One can transform
a representation
of a matroid with rank~\(r\)
over a field~$\F$
into a representation
over~\(\F\) with \(r\)~rows
\citep[Section~2.2]{Oxl92}
and we will always assume
to work with representations
of this form.

Not all matroids are representable
over all fields
\citep[Theorem~6.5.4]{Oxl92}.
Some are not representable at all
\citep[Example~1.5.14]{Oxl92}.
A matroid representable
over~\(\F_2\) is a \emph{binary matroid}.


Given
a representation of a matroid~\(M\)
over a field~\(\F\),
a representation
of the dual matroid \(M^*\) over~\(\F\)
is computable in linear time
\citep[Theorem~2.2.8]{Oxl92}.


If $A_i$ is a $(a_i \times b_i)$-representation 
of a matroid $M_i$ over field $\mathbb F$
for $i \in \{1,\dots, m\}$,
then
a $\left(\sum_{i=1}^m a_i \times \sum_{i=1}^m b_i \right)$-representation
of~$\bigoplus_{i=1}^m M_i$ over~\(\mathbb F\)
is computable
in time of
$\bigO(\sum_{i=1}^m a_i \cdot \sum_{i=1}^m b_i)$~operations over~$\mathbb F$
\citep[Exercise~6, p.~132]{Oxl92}.

Uniform matroids
of rank~\(r\)
on a universe of size~\(n\)
are representable over
all fields with at least \(n\)~elements

\citep[Section~3.5]{Mar09}.


The uniform matroid of rank one
is trivially representable
over \emph{all} fields.
Thus,
so are multicolored matroids.


\begin{lemma}
  \label[lemma]{lemma:matroid-set-ext}
  Given an \((r\times n)\)-representation~\(A\)
  for a matroid~$M$
  over a field~\(\mathbb F\),
  a representation of~$M \vee (X,2^X)$
  over~\(\mathbb F\)
  is computable in time of $(n+|X|)(r+|X|)$
  operations
  over~\(\mathbb F\).
\end{lemma}

\begin{proof}
  Let \(M=(U,\I)\).
  If $U \cap X \not = \emptyset$,
  consider the restriction~$M' = (U \setminus X,\{ J\subseteq U\setminus X \mid J \in \I\})$
  of~\(M\) to~$U \setminus X$,
  which is again a matroid
  \citep[Section~1.3]{Oxl92}.
  If~\(U\cap X=\emptyset\), then we get $M'=M$.
  A representation~\(A'\) for~\(M'\)
  can be obtained
  from a representation of~\(A\) for~\(M\)
  by removing the columns
  labeled by elements in~$X$.
  The free matroid~$(X,2^X)$
  is representable by the identity matrix
  over any field.
  Thus,
  \(M\vee (X,2^X)=M'\vee (X,2^X)=M'\oplus(X,2^X)\)
  is a direct sum
  of two matroids
  with known representations.
  The representation
  of this direct sum
  can therefore
  be easily obtained
  in the claimed time
  \citep[Exercise~6, p.~132]{Oxl92}.
\qed\end{proof}


\subsection{Matroids truncations}

\begin{definition}[truncation]\label{def:trunc}
  The \emph{$k$-truncation}
  of a matroid~$(U, \I)$
  is a matroid~$(U, \I')$
  with~$\I' = \{ S \subseteq U \mid S\in \I\wedge |S| \leq k \}$.

  Moreover,
  if \(A\)~is a representation of a matroid
  and \(A'\)~is a representation of its
  truncation,
  we will also
  call~\(A'\) a truncation of~\(A\).
\end{definition}


\begin{proposition}[{\citet[Theorem~3.15]{LMPS18}}]
  \label{prop:finite-trunc}
  Let $A$~be an $(r \times n)$-matrix
  of rank~\(r\)
  over a finite field~$\F_{p^d}$,
  where \(p\)~is a prime
  polynomial in the length of the encoding of~\(A\)
  as a binary string.
  For any $k\in\{1,\dots,r\}$,
  we can compute a $k$-truncation of~$A$
  over a finite field extension~$\mathbb K\supseteq\F$
  in time of a polynomial number of field operations over~$\mathbb F$,
  where $\mathbb K = \F_{p^{rkd}}$.
\end{proposition}

\begin{remark}\label[remarkn]{rem:trunc-extension}
  
  
  The proof of \citet[Theorem~3.15]{LMPS18}
  shows
  that the field extension~$\mathbb K\supseteq\mathbb F:=\F_{p^d}$
  in \cref{prop:finite-trunc}
  can be chosen as
  $\mathbb K =\F_{p^{sd}}$ for any integer~$s \ge rk$.
  The time for computing
  the truncation
  consists of computing a truncation
  over the field of fractions~\(\mathbb F(X)\)
  using \(O(nkr)\)~operations over~\(\mathbb F\)
  via Theorem~3.14 of \citet{LMPS18}
  and then computing an irreducible
  polynomial of degree~\(s\)
  over~\(\mathbb F\)
  in
  \(s^4d^2\sqrt{p}\cdot\polylog(s,p,d)\)~operations
  over~$\mathbb F$ \citep{Sho90}.
\end{remark}

\noindent
\cref{prop:finite-trunc}
applied according to \cref{rem:trunc-extension}
immediately yields:


\begin{corollary}
  \label{rem:same_field_trunc}
  For \(i\in\{1,\dots,m\}\),
  let $A_i$~be
  $(r_i \times n)$-matrices
  over~$\F_{p^d}$.
  Given a
  natural number~$k \leq \min\{r_i\mid 1\leq i\leq m\}$,
  \(k\)-truncations
  of the~\(A_i\)
  over the same
  finite field extension~$\F_{p^{rkd}}\supseteq\F$
  are computable
  in \(O(mnkr)+r^4k^4d^2\sqrt p\cdot\polylog(r,k,p,d)\)~operations
  over~\(\mathbb F\),
  where $r= \max\{r_i\mid 1\leq i\leq m\}$.
\end{corollary}

\noindent
Herein,
the additive running time is due to the fact
that we only have to construct the irreducible
polynomial of degree~\(rk\) once
in order to represent the truncated
matroids over the same field extension~\(\F_{p^{rkd}}\).


	


\section{Finding strong links in social networks}
\label{app:social}
\label{sec:app}

In this section,
we illustrate the modeling capabilities
of our newly introduced problem \mdmc{}
by using it to model a problem from social network analysis.

Finding strong links

in social networks


helps
improving clustering and advertising 
algorithms.
Assume that a social network
is given as an undirected graph~$G=(V,E)$,
whose vertices correspond to agents
and whose edges correspond to social ties between them.
The task is to infer the strong and the weak ties.
\citet{ST14} introduced the problem of labeling edges of a graph as strong or weak under the \emph{Strong Triadic Closure (STC)} hypothesis:
it was formulated in sociological work by \citet{Gr73} and
states that,
if two agents have a strong tie to a third agent,
then they should have at least a weak tie to each other.
In other words, there should not be induced paths on two vertices,
also called \emph{open triangles},
consisting of strong edges only.
An open triangle
of strong edges is called an \emph{STC violation}.

The problem of maximizing the number of strong edges (minimizing the number of weak edges) in a network so that there be 
no STC violations is NP-hard,
has been studied with respect to
approximation and parameterized algorithms \citep{ST14,GK18},
and on restricted graph classes \citep{KP17}.


\citet{RTG17} suggested

a variant

where one is additionally given
communities~$X_1, \ldots, X_m \subseteq V$,

each of which represents a group
with common interests
and thus is assumed
to be
connected via strong ties.

They showed that it is NP-hard to check
whether one can label the edges
of a graph strong or weak
so that
the subgraphs~$G[X_i]$ be connected via strong ties
and there be no STC violations.
Thus,
the number of STC violations
is inapproximable within any factor
and the problem is not fixed\hyp parameter
tractable with respect to the parameter
``number of allowed STC violations''
unless P${}={}$NP.
In contrast,
the problem
of maximizing the number~$r$ of non\hyp violated triangles

admits a polynomial-time $1/(m+1)$-approximation \citep{RTG17}.
Complementing the approximability result
for~$r$,

we show that the problem
is fixed\hyp parameter tractable
parameterized by~\(m\) and~\(r\).

\begin{problem}[STC with tight communities]\leavevmode
  \label[problem]{prob:maxtri}
  \begin{compactdesc}
  \item[\normalfont\textit{Input:}]
    A graph $G=(V,E)$,
    communities $X_1, \ldots, X_m \subseteq V$,
    and an integer~\(r\).
    
  \item[\normalfont\textit{Question:}]
    Are there weak edges~$A \subseteq E$
    (edges in~\(E\setminus A\) are \emph{strong})
    such that each $G[X_i] \setminus A$ is connected
    and there are at least~\(r\) non\hyp violated triangles?
  \end{compactdesc}
\end{problem}


\noindent
We model \cref{prob:maxtri} as \mdmc{}:
Let the universe~$U = E \cup \mathcal{K}$,
where $E$~is the set of edges
and $\mathcal{K}$~is the set of all open triangles
in~$G$.
Note that $\mathcal{K}$~can be computed in $\bigO(n^3)$ time. The set~$\mathcal{K}$ corresponds to the set of clients, and the set of edges~$E$ corresponds to the set of facilities. The cost of opening a facility~$u\in E$ (that is, the cost of making an edge weak) is~$c_u =0$. The profit that facility~$u$ gets from serving client~$v$,
that is, from resolving STC violation~\(v\),
is
\[
  p_{uv}=
  \begin{cases}
    1&\text{if the edge~$u\in E$
      is a part of the open triangle~$v\in\mathcal K$ in $G$},\\
    0&\text{otherwise}.
  \end{cases}
\]

As client matroid we can choose
$(\mathcal{K},C_1)$ with
$C_1 = \{\mathcal{K}' \subseteq \mathcal{K} \mid |\mathcal{K}'| \le r \}$,
since resolving \(r\)~STC violations
is sufficient in order to
resolve \emph{at least}~$r$ of them.


Since it is a uniform matroid,

we easily get a representation
over any field with at least \(|\mathcal K|\)~elements.
The facility matroids are
$\{M_i\}_{i=1}^m$ with
\begin{align*}
  \allowdisplaybreaks
  M_i&:=(E_i,A_i)\oplus (E\setminus E_i,2^{E\setminus E_i}),\\
  E_i&:=\{\{u,v\}\in E\mid \{u,v\}\subseteq X_i\},\text{ and}\\
  A_i&:= \{E' \subseteq E_i \mid G[X_i]\setminus E' \text{ is connected}\}.
\end{align*}
Herein, \((E_i,A_i)\) is the so\hyp called
\emph{bond matroid}
of~\(G[X_i]\) \citep[Section~2.3]{Oxl92}.
As the dual
of a \emph{graphic matroid},


we easily represent it
over \emph{any} field 
\citep[Proposition~5.1.2]{Oxl92}.
Since the free matroid
\((E\setminus E_i,2^{E\setminus E_i})\)
is also representable over any field,
so is~\(M_i\).


Therefore,
having represented all matroids
over the same field,
we can apply \cref{thm:alg}\eqref{thm:alg2}
and thus complement the
known
\(1/(m+1)\)-approximation
of the parameter~\(r\)
due to \citet{RTG17}
by the following result:

\begin{proposition}
  \label[proposition]{prop:maxtri}
  \cref{prob:maxtri} is fixed\hyp parameter 
  tractable with respect to~\(r+m\).
\end{proposition}

\noindent
As noted by \citet{RTG17},
if two communities~\(X_i\) and~\(X_j\)
are disjoint,
then the matroids~\(M_i\) and~\(M_j\)
can be combined into one via a direct sum.
Thus,
\cref{prob:maxtri}
is fixed\hyp parameter tractable
parameterized by~\(r\)
if the input communities are pairwise non\hyp intersecting.
Moreover,
hardness results of \citet{RTG17}

carry over
to \mdmc{}:

\begin{proposition}
  \mdmc{} is NP-hard even
  for a single binary facility matroid
  and no client matroids.
\end{proposition}

\noindent
Along the lines of \citet{GHK+18},
we can also generalize \cref{prop:maxtri}
to the
problem of maximizing
induced subgraphs
belonging to some set~\(F\)
and containing at least one weak edge,


if all graphs in~\(F\) have constant size.
  


      


\section{Representative families for matroid intersections
  and
  set packing with multiple matroid constraints}
\label{sec:tools}

In this section,
we generalize some known
matroid optimization
fixed\hyp parameter algorithms
for use in our algorithm for \mdmc{}.
These results are completely independent from \mdmc{}
and of independent interest.
Among them,
we will see a fixed\hyp parameter algorithm
of the following problem.


\begin{problem}[\textsc{Set Packing with Matroid Constraints} (\spmc{})]\leavevmode
  \begin{compactdesc}
  \item[\normalfont\textit{Input:}]
    Matroids $\{(U,\I_i)\}_{i=1}^m$,
    
    a family $\cH \subseteq 2^U$,
    $w \colon \cH \rightarrow \R$,
    and \(\alp\in\N\).
  \item[\normalfont\textit{Task:}]
    Find sets~\(H_1,\dots,H_\alp\in\cH\) such that
    \[
      \biguplus_{i=1}^\alp H_i\in \bigcap_{i=1}^m \I_i
      \text{\qquad and maximizing\qquad}
      \sum_{i=1}^\alp w(H_i).\]
  \end{compactdesc}
\end{problem}


\noindent
\looseness=-1
\spmc{} is a generalization of
the \textsc{Matroid Parity}
and \textsc{Matroid Matching} problems introduced
by \citet{Law76}:
in these problems,
there is only one input matroid and
all input sets have size exactly two.
In \textsc{Matroid Parity},
they are additionally required to be
pairwise disjoint.
Both problems are solvable in
polynomial\hyp time on linear matroids,
but not on general matroids \cite[Section 43.9]{Sch03}.
\citet{LSV13} studied approximation algorithms
for the variant
\textsc{Matroid Hypergraph Matching}
with one input matroid
and unweighted (but possibly intersecting) input sets.
Finally,
\citet{Mar09} 
and \citet{LMPS18}
obtained fixed\hyp parameter tractability results for
\textsc{Matroid \(\gamma\)-Parity},
where one has only one input matroid
and pairwise non\hyp intersecting unweighted sets
of size~\(\gamma\) in the input.

We generalize the fixed\hyp parameter
algorithms of \citet{Mar09} 
and \citet{LMPS18}
to \spmc{}.
Both are
based
on \emph{representative families}:

intuitively,
a representative~\(\cSs\)
of some family~\(\cS\)
for a matroid~\(M\)


ensures that,
if \(\cS\)~contains a set~\(S\)
that can be extended to
a basis of~\(M\),
then \(\cSs\) also contains
such a set
that is
``as least as good'' as~\(S\).
To solve \spmc{} (and later \mdmc{}),
we generalize
this concept to representative
families for matroid \emph{intersections}:

\begin{definition}[\boldmath max intersection $q$-representative family]\label[definition]{def:qrep}
  Given matroids~$\{(U,\I_i)\}_{i=1}^{m}$,
  a~family~$\familyS\subseteq 2^U$,
  and a function~$w\colon \familyS \rightarrow \R$,
  
  
  
  we say that a subfamily~$\cSs \subseteq \familyS$
  is \emph{max intersection $q$-representative
    for $\familyS$ with respect to~\(w\)}
  if,
  for each set~$Y \subseteq U$ of size at most~$q$,
  it holds that:
  \begin{itemize}
  \item if there is a set~$X \in \familyS$  with
    $X \uplus Y \in \bigcap_{i=1}^m\I_i$, 
  \item then there is a
    set~$\widehat X \in \cSs$ with


  $\widehat X \uplus Y \in \bigcap_{i=1}^m\I_i$ and
  
    $w(\widehat X) \geq w(X)$.	
  \end{itemize}

  If $m=1$, then we call~$\cSs$
  a \emph{max $q$-representative family} of $\familyS$.
\end{definition}

\noindent
\looseness=-1
Our aim is
computing a max intersection representative
of the family of
all feasible solutions to \spmc{},
yet we will not limit ourselves
to the goal function of \spmc{}.
Therefore,
in \cref{sec:imuf},
we first introduce
the class of set functions
with respect to which
we will compute intersection representative families.
In \cref{sec:rep-unions},
we show how to compute
a representative
of the family of independent sets
that can be formed
as the disjoint union
of \(\alp\)~sets
of cardinality~\(\gam\)
in a family~\(\cH\).
\cref{sec:rep-intersect},
we generalize this result to
max \emph{intersection} representative families,
so that we can compute
representatives of the families
of all
feasible solutions to \spmc{}
with input sets of cardinality~\(\gamma\).
We will use this result
to solve \spmc{} in
\cref{sec:spmc-fpt}.


\begin{remark}
  Although we define \spmc{}
  as a \emph{maximization} problem
  and prove our results for
  \emph{max} intersection representative families,
  all results in this section
  can also be proved
  for the \emph{minimization} variants
  by negating
  the weight functions.
\end{remark}

\subsection{\Dtext{}s}
\label{sec:imuf}

The overall goal of this \cref{sec:tools}
is computing max intersection representatives
of the family of all feasible solutions to \spmc{}.
We will compute these representatives
not only with respect to the set function
required to solve \spmc{},
but more generally
with respect to set functions of the following type.

\begin{definition}[\dtext{}]
  \label{def:dtext}
  Let \(\cH\subseteq 2^U\)
  and
  \[
    \cB(\cH):=\Bigl\{\biguplus_{j=1}^iH_j\Bigm| i\in\N,H_1,\dots,H_i\in\cH\Bigr\}.
  \]
  A set function~\(\dw\colon \cB(\cH)\to\R\)
  is called an \emph{\dtext{}}
  if there is
  a \emph{\dterm{} function}~\(\dg\colon\R\times \cH\to\R\)
  that is non-decreasing in its first argument and
  such that, for each~\(X\ne\emptyset\),
  \[
    \dw(X)=\smashoperator{\max_{\substack{H\in \cH,S\in\cB(\cH)\\S\uplus H=X}}}\dg(\dw(S),H).
  \]
  
  
  
\end{definition}

\noindent
Note that an \dtext{}~\(\dw\)
is fully determined
by the value~\(\dw(\emptyset)\)
and its \dterm{} function~\(\dg\).

\Dtext{}s resemble
primitive recursive functions
on natural numbers,
where \(S\uplus H\) plays the role
of the ``successor'' of~\(S\)
in primitive recursion.
In the following,
we show some examples and counterexamples.

\begin{example}
  \label{ex:ws}
  Let \(\cH\subseteq 2^U\) and
  \(w\colon \cH\to\R\).
  For solving \spmc{},
  we will compute
  max intersection representative families
  with respect to the function~\(\dw\)
  determined by
  \(\dw(\emptyset)=0\) and
  \(\dg\colon (k,H)\mapsto k+w(H)\).
  Concretely,
  for \(\emptyset\ne X\subseteq\cB(\cH)\),
  one gets
  \[
    w_{\Sigma}(X):=\dw(X)=\max_{X=H_1\uplus\dots \uplus H_i\atop
      H_1,\dots,H_i \in \cH}\sum_{j=1}^{i}w(H_j)
  \]
  due to the associativity and commutativity
  of the maximum and sum.
\end{example}
\noindent
\Dtext{}s generalize additive set functions.
\begin{example}
  \label{rem:additive}
  \label{ex:additive}
  Any additive set function~\(w\colon 2^U\to\R\)
  is \dtex{}
  since,
  for the \dtext{}~\(w_{\Sigma}\)
  in \cref{ex:ws}, one has
  \(w_{\Sigma}(X)=\sum_{j=1}^{i}w(H_j)=w(X)\)
  for \emph{any} partition
  \(X=H_1\uplus\dots \uplus H_j\).
\end{example}

\noindent
However,
submodular functions
are generally not
\dtex{}:

\begin{example}
  \label{ex:nocoverage}
  Let \(f\colon 2^U\to\R\)~be a coverage function
  (cf.\ \cref{def:covfunc})
  on \(U=\{u_1,v_1,u_2,v_2\}\) with
  \begin{align*}
    u_1&=\{a\}, & v_1&=\{c\}, & u_2 &=\{a,b\},&&\text{and} & v_2=\{c,d\}.
  \end{align*}
  Assume that
  \(f\)~is \dtex{}
  for   \(\cH=\{\{u_1\},\{v_1\},\{u_2\},\{v_2\}\}\).
  The only partition of~\(\{u_1,v_2\}\)
  into sets in~\(\cH\) is~\(\{u_1\}\uplus\{v_2\}\).
  Thus,
  $f(\{u_1,v_2\})=\dg(f(\{u_1\}),\{v_2\})$
  or
  $f(\{u_1,v_2\})=\dg(f(\{v_2\}),\{u_1\})$,
  whichever is larger.
  In the first case, we get the contradiction
  \[
    3=f(\{u_1,v_2\})=\dg(f(\{u_1\}),\{v_2\})=\dg(f(\{v_1\}),\{v_2\})\leq f(\{v_1,v_2\})=2.
  \]
  Otherwise,
  in the second case, we get the contradiction
  \[
    3=f(\{u_1,v_2\})=\dg(f(\{v_2\}),\{u_1\})=\dg(f(\{u_2\}),\{u_1\})\leq f(\{u_1,u_2\})=2.
  \]
\end{example}

\noindent
\looseness=-1
We see that
coverage functions are not
\dtex{} since
the function~\(\dg\)
\dterm{}~\(\dw\) in \cref{def:dtext}
is allowed to
depend only on \(\dw(S)\)~in the first argument,
not on~\(S\) itself.
We will indeed see that requirement is crucial
and presume that \dtext{}s
are the most general class of functions
with respect to which
we can prove the results in \cref{sec:rep-unions,sec:rep-intersect}.

\subsection{Computing representative families for unions of disjoint sets}
\label{sec:rep-unions}

In this section,
we prove the following result,
which
will
allow us to compute
a representative of the family
of feasible solutions to \spmc{}
with respect to one matroid.
We generalize it
to multiple matroids in
\cref{sec:rep-intersect}.


\begin{proposition}
  \label{thm:core-tool}
  Let $M = (U,\I)$~be a linear matroid
  of rank $r=(\alp+\bet)\gam\geq 1$, 
  $\cH\subseteq 2^U$~be a $\gam$-family
  of size~$t$, 
  and \(\dw\colon\cB(\cH)\to\R\)~be an \dtext{}
  (cf.\ \cref{def:dtext}). 

  Given a representation
  of~$M$ over a field~$\mathbb F$
  and the value~\(\dw(\emptyset)\),
  one can
  compute a
  max $\bet \gam$-representative~$\widehat \familyS$ of 
  size~$r \choose \alp \gam$ for the 
  family
  \[\familyS = \{ S = H_1 \uplus \dots \uplus H_\alp 
    \mid
    S\in\I\text{ and }
    H_j \in \cH\text{ for }j \in \{1,\dots, \alp \}\}
  \]
  with respect to~\(\dw\)
  in time of $2^{O(r)}\cdot t$~operations over $\mathbb F$
  and calls to the
  function~\(\dg\) \dterm{}~\(\dw\).
\end{proposition}


\noindent
Before proving \cref{thm:core-tool},
we provide some context.
The main feature of \cref{thm:core-tool}
is that it allows us
to compute max intersection representatives
of the family~\(\cS\),
whose size may be
exponential in the size of~\(\cH\),
in time growing merely linearly
in the size of~\(\cH\).
The literature
uses several implicit
ad\hyp hoc
proofs of
variants of \cref{thm:core-tool}
in algorithms for concrete problems
\citep{Mar09,FLPS16,FLPS17}.
These proofs usually
use non\hyp negative additive
functions in place of~\(\dw\).


Our \cref{thm:core-tool}


does not require additivity,
yet,
as shown by \cref{ex:additive},
works perfectly fine
for all additive weight functions.

As shown by \cref{ex:nocoverage},
submodular functions
are not necessarily \dtex{}
and,


indeed,
using \cref{ex:maxcover},
one can show that
generalizing \cref{thm:core-tool}
even
to coverage functions
would yield \(\FPT=\Wtwo\).
The proof also makes
for an illustration
of \cref{def:qrep} and \cref{thm:core-tool}:

\begin{observation}
  If \cref{thm:core-tool}
  holds for coverage functions~\(\dw\),
  then \(\FPT=\Wtwo\).
\end{observation}

\begin{proof}
  Consider a coverage
  function~\(\dw\colon 2^U\to\mathbb N\).
  Clearly,
  finding a set
  \(S\subseteq U\) with \(|S|\leq r\)
  maximizing~\(\dw(S)\)
  is our problem from \cref{ex:maxcover},
  which is
  called \textsc{Maximum Coverage}
  and W[2]-hard parameterized
  by~\(r\) \citep{CFK+15}.

  Now, assume that we could
  apply \cref{thm:core-tool}
  with a uniform matroid~\(M=(U,\I)\)
  of rank~\(r\),
  \(\alp=r\), \(\bet=0\), \(\gam=1\),
  and
  the \(\gam\)-family $\cH = \{ \{ u \} \mid u \in U \}$
  to compute a \(0\)-representative~\(\cSs\)
  of size \({r\choose\alp\gam}=1\)
  of the family
  \begin{align*}
    \cS&=\{S=H_1\uplus\dots\uplus H_\alp\mid S\in\I
    \text{ and }H_j\in\cH\text{ for }j\in\{1,\dots,\alp\} \}\\
    &=\{S\subseteq U\mid |S|= r\}.
  \end{align*}
  with respect to~\(\dw\)
  in time of
  \(2^{O(r)}\cdot |\cH|=2^{O(r)}n\)~operations over~\(\F\),
  where \(M\)~is representable over
  \(\F=\F_{2^d}\)
  for \(d=\lceil\log r\rceil\).
  Then \(\cSs\)
  only contains
  the set~\(S\) with \(|S|=r\) maximizing~\(\dw(S)\).
  Since each operation over~\(\F_{2^d}\)
  can be carried out in \(\poly(d)\in\poly(n)\)~time,
  we thus
  solve the \(\Wtwo\)-hard
  \textsc{Maximum Coverage}
  problem
  in \(2^{O(r)}\cdot \poly(n)\)~time,
  which implies \(\FPT=\Wtwo\).\qed
\end{proof}

\noindent
We now prove \cref{thm:core-tool}.
Like its implicit ad\hyp hoc proofs
in the literature \citep{Mar09,FLPS16,FLPS17},
we will prove it by iterative
application of the following known result.

\begin{proposition}[{\citet[Theorem~3.7]{FLPS16}}]
  \label{prop:repset}
  Let $M = (U,\I)$~be a linear matroid
  of rank~$r=\alp + \bet$,
  $\familyS = \{S_1,\dots,S_t\}$~be
  an $\alp$-family of independent sets,
  and $w \colon \familyS \rightarrow \R$.
  \footnote{\citet{FLPS16}
    require the weight function to be non\hyp negative.
    Yet their proof does not exploit non\hyp negativity.
    Moreover,
    one can always transform the weight function
    so that it is non\hyp negative and then transform it back.}
  Then,
  there exists a max $\bet$-representative~$\cSs \subseteq \familyS$
  of size at most~${r \choose \alp}$.
  Given a representation of~$M$
  over a field~$\mathbb F$,
  $\cSs$ can be found using
  \[\bigO\left({r \choose \alp}t\alp^{\omega} + t{r \choose \alp}^{\omega-1}\right)\text{ operations over~\(\F\)},\]
  where $\omega < 2.373$~is
  the matrix multiplication exponent.
\end{proposition}


      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      


      
      
      
      
      
      
      
      
      

\noindent
\cref{alg:q-repset}
computes
the representative families
required by \cref{thm:core-tool}
by iteratively applying \cref{prop:repset}.
\cref{thm:core-tool}
follows from
the correctness proof of
\cref{alg:q-repset} in \cref{lem:q-repset}
and its running time analysis in
\cref{lem:q-repset-running-time}.


  


\begin{algorithm}[t]
  \KwIn{A representation
    of a matroid~\(M=(U,\I)\) 
    of rank $r=(\alp+\bet)\cdot \gam\geq 1$
    over $\mathbb F$,
    $\bet \in \mathbb N$,
    a $\gam$-family $\cH\subseteq 2^U$ of size~$t$,
    a function~\(\dg\colon \R\times \cH\to\R\)
    non\hyp decreasing in the first argument,
    and \(\dw(\emptyset)\).}
  \KwOut{a max $\bet \gam$-representative~\(\widehat\familyS\) of size $r \choose \alp \gam$ for the 
    family $\familyS:=\{ S = H_1 \uplus \dots \uplus H_\alp 
      \mid  S \in \I \text{ and } H_j \in \cH
      \text{ for }j\in\{1,\dots,\alp\}\}
      $ with respect to the
      \dtext{}~$\dw$ generated by \(\dw(\emptyset)\)
      and \(\dg\).}

  $\cSs_0 \gets \{ \emptyset \}$\nllabel{lin:base-case}.\;
  $w_0(\emptyset)\gets \dw(\emptyset)$\nllabel{lin:base-case-end}.\;
  \ForEach(\nllabel{lin:rs-fork}){$i \in \{ 1, \ldots, \alp \}$}{
    $\cSst_i\gets \emptyset$.\nllabel{lin:csst}\;
    $w_i\colon 2^U\to\R, S\mapsto 0$.\nllabel{lin:wi}\;

    \ForEach(\nllabel{lin:for2}){$H\in\cH,S\in\cSs_{i-1},H\cap S=\emptyset,H\cup S\in\I$}{
      $\cSst_i\gets \cSst_i\cup\{H\uplus S\}.$
      \nllabel{lin:ri}\;
      $w_i(H\uplus S)\gets \max\{w_i(H\uplus S),\dg(w_{i-1}(S),H)\}$.
      \nllabel{lin:weight}\;
    }
    $\cSs_i\gets{}$max $(r-\gam i)$-representative of \(\cSst_{i}\) with respect to~\(w_i\) of size
    at most~\({r\choose \gam i}\) using \cref{prop:repset}.
    \nllabel{lin:compress}
    \;
  }
  
  
  
  
  
  
  
  
  
  
  
  
  
  \KwRet{$\cSs_{\alp}$}.\nllabel{lin:retcSsalp}\;
  \caption{Algorithm for the proof of \cref{thm:core-tool}.}

  \label[algorithm]{alg:q-repset}
\end{algorithm}


  
  
  
  
  
  
  
  
  
  
  
  
  


\begin{lemma}
	\label[lemma]{lem:q-repset}
	\cref{alg:q-repset} is correct.
\end{lemma}
\begin{proof}
    We prove by induction that,
  in \cref{lin:compress} of \cref{alg:q-repset},
  \begin{enumerate}[(i)]
  \item\label{ind1} $\cSs_i$ is
    max $(r-\gam i)$-representative     with respect to~\(\dw\)
    for
    \begin{align*}
      \cS_i&\phantom:=\{S=H_1\uplus\dots\uplus H_i\mid S\in\I
             \text{ and }H_j\in\cH\text{ for }j\in\{1,\dots,i\}\}.
    \end{align*}
  \item\label{ind2} To this end,
    we simultaneously show
    that
    $w_i(X)=\dw(X)$ for $X\in\cSst_i$.
  
  
  
  \end{enumerate}
  The lemma then follows since
  \cref{alg:q-repset} returns \(\cSs_{\alp}\)
  in \cref{lin:retcSsalp},
  which has size~\({r\choose\alp \gam{}}\)
  by construction in \cref{lin:compress}.

  Both \eqref{ind1} and \eqref{ind2} hold
  for~\(i=1\)
  since \(\cS_1=\cSst_1=\cH\cap \I\)
  and
  \(\dw(X)=\dg(\dw(\emptyset),X)=w_1(X)\)
  for all \(X\in\cH\) by \cref{def:dtext}.
  For the induction step,
  assume that \eqref{ind1} and \eqref{ind2}
  hold for~\(i-1\)   and observe that
  \begin{enumerate}[(a)]
  \item by construction,
    \(\cSs_i\subseteq \cSst_i\subseteq \cS_i\)
    for all~\(i\in\{1,\dots,k\}\) and
  \item\label{cla2}  since \(\cH\)~is a \(\gam\)-family
    and every subset of an independent set is independent,
    for all \(X=H\uplus S\in\cS_i\)
    with \(H\in \cH\) and \(S\in\cB(\cH)\),
    one has \(S\in\cS_{i-1}\).
  \end{enumerate}
  We first prove \eqref{ind2}.
  
  
  
  
  
  
  
  
  
  For each set~\(X\) added to~\(\cSst_i\)
  by \cref{alg:q-repset}
  in \cref{lin:ri},

  
  
  \begin{align*}
    w_i(X)&=\max\{\dg(w_{i-1}(S),H)\mid H\in\cH,S\in\cSs_{i-1},X=H\uplus S\}.\\
    \intertext{Since,
    by induction,
    \(w_{i-1}(X)=\dw(X)\)
    for all \(X\in\cSs_{i-1}\subseteq \cSst_{i-1}\),
    this is}
          &=\max\{\dg(\dw(S),H)\mid H\in\cH,S\in\cSs_{i-1},X=H\uplus S\}.\\
    \intertext{Since,
    by induction,
    \(\cSs_{i-1}\)~is max representative
    for \(\cS_{i-1}\) with respect to~\(\dw\)
    and since \(\dg\)~is non\hyp decreasing in its first argument,
    this is}
          &=\max\{\dg(\dw(S),H)\mid H\in\cH,S\in\cS_{i-1},X=H\uplus S\}\\
          &=\max\{\dg(\dw(S),H)\mid H\in\cH,S\in\cB(\cH),X=H\uplus S\}=\dw(X),
  \end{align*}
  where the last equality is due to \cref{def:dtext}.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

  
  
  
  
  
  
  
  
  
  
  


  We now show \eqref{ind1}.
  In \cref{lin:compress},
  using \cref{prop:repset},
  we create a 
  max $(r-\gam i)$-representative $\cSs_i$
  of $\cSst_i$ 
  with respect to $w_i$,
  which coincides with~\(\dw\) on~\(\cSst_i\)
  by \eqref{ind2}.
  
  
  The claim now is that $\cSs_i$ is
  max $(r-\gam i)$-representative
  for $\cS_i$
  with respect to $\dw$.
  
  First, let
  $Y \subseteq U$ with
  $|Y|=r-\gam i$
  be such that
  there is an~$X \in \cS_i$ with


  $Y \uplus X \in \I$.

  Since 
  
  \(\dw\)~is
  an \dtext{} (cf.\ \cref{def:dtext}),
  there is a 
  partition~$S \uplus H = X$
  with
  
  
  $H \in \cH$,
  $S\in \cB(\cH)$
  such that
  \begin{equation}
    \dw(X)=\dg(\dw(S),H).\label{eq:razlozhenie}
  \end{equation}
  Since \(X\in\cS_i\), one has \(S\in S_{i-1}\) by \eqref{cla2}.
  
  
  
  
  By induction,
  $\cSs_{i-1}$~is
  max $(r-\gam(i-1))$-representative
  for~$\cS_{i-1}$
  with respect to~\(\dw\).
  Thus,
  there is a  set~$S' \in \cSs_{i-1}$
  with
  \begin{itemize}

  \item $(Y \uplus H) \uplus S' \in \I$, and
  \item $\dw(S')\geq\dw(S)$.
  \end{itemize}
  By construction of~\(\cSst_i\) in \cref{lin:ri},
  $S' \uplus H \in \mathcal\cSst_i$.
  Since,
  by \cref{lin:compress},
  $\cSs_i$ is max
  $(r-\gam i)$-representative
  for $\cSst_i$
  with respect to~\(w_i\),
  
  
  
  
  there finally is
  an~$X' \in \cSs_{i}$ with
  \begin{itemize}

  \item $Y \uplus X' \in \I$, and
  \item $\dw(X')=w_i(X')\geq w_i(S'\uplus H)=\dw(S'\uplus H)$.
  \end{itemize}
  Since \(\dg\)~is non\hyp decreasing
  in its first argument
  and by \eqref{eq:razlozhenie},
  we get
  $\dw(X')\geq \dw(S'\uplus H)
    
    
    \geq \dg(\dw(S'),H)
    \geq \dg(\dw(S),H)

    
    
    
    
    =\dw(X).$


    \looseness=-1
    Finally,
  consider \(Y\subseteq U\) with
  $|Y|<r-\gam i$
  such that
  there is an~$X \in \cS_i$ with
  
  
  
    $Y \uplus X \in \I$.
  
  Since matroid~\(M\) has rank~\(r\),
  there is a superset~\(Y'\supseteq Y\)
  with \(|Y'|=r-\gam i\)
  such that

 $Y' \uplus X \in \I$.
  Thus, there exists \(X'\in\cSs_{i}\) such that

$Y' \uplus X' \in \I$, and
$\dw(X')\geq \dw(X)$
  and both properties hold when
  replacing~\(Y'\) by~\(Y\).
\qed\end{proof}
\noindent
Having shown that \cref{alg:q-repset}
is correct,
to prove \cref{thm:core-tool},
it remains to show that
\cref{alg:q-repset}
runs in the claimed time.


\begin{lemma}
  \label[lemma]{lem:q-repset-running-time}
  \cref{alg:q-repset} runs in time of
  $2^{O(r)} \cdot t$~operations over~$\mathbb F$
  and calls to the generating function~\(\dg\).
\end{lemma}
\begin{proof}
  Without loss of generality,
  \(U=\{1,\dots,n\}\).
  We represent subsets of~\(U\)
  as sorted lists.
  Since the input sets in~\(\cH\)
  have cardinality~\(\gamma\),
  we can initially sort each of them
  in \(O(\gamma\log\gamma)\)~time.
  The sorted union and intersection
  of a sorted list of length~\(a\)
  and a sorted list of length~\(b\)
  can be computed in \(O(a+b)\)~time
  \citep[Section~4.4]{AHU83}.
  We thus get a representation
  of sets as words of length~\(r\)
  over an alphabet of size~\(n\).
  We can thus store and look up
  the weight of a set of size at most~\(r\)
  in a trie
  in \(O(r)\)~time \citep[Section~5.3]{AHU83}.
  Note that we do not have the time
  to completely initialize
  the \(O(t)\)~size-$n$ arrays
  in the trie nodes.
  Instead,
  we will initialize
  each array cell of a trie node at
  the first access:
  to keep track of the
  already initialized array positions,
  we use a
  data structure for \emph{sparse sets}
  over a fixed universe~\(U\)
  that allows membership tests,
  insertion, and deletion of elements
  in constant time \citep{BT93}.
  
  
  
  
  
  
  
  The running time of \cref{alg:q-repset}
  is dominated by the $\alp$~iterations 
  of the for-loop starting in \cref{lin:rs-fork}.
  We analyze the running time of iteration~\(i\)
  of this loop.


  The family~$\cH$ consists of $t$~sets of size~$\gam{}$.
  The family~$\cSs_{i-1}$ consists of
  $r \choose {\gam{}(i-1)}$~sets of size $\gam{}(i-1)$.
  Thus,
  the for-loop starting in \cref{lin:for2}
  makes at most \(2^r\cdot t\) iterations:
  
  
\begin{enumerate}[(i)]
\item $H \cap S = \emptyset$ can be checked
  in $O(\gam{}i)\subseteq O(r)$~time.
\item We check $H \uplus S \in \I$
  by
  testing \(|H\uplus S|\leq r\)~columns of~\(A\)
  of height~\(r\)
  for linear independence
  using $O(r^3)$~operations over $\mathbb F$
  with Gaussian elimination.
  
  
\item The running time of \cref{lin:ri,lin:weight}
  is dominated
  by
  looking up and storing weights of sets
  of size at most~\(r\)
  in \(O(r)\)~time using a trie,
  and a call to~\(\dg\).
\end{enumerate}
Thus,
the for-loop in \cref{lin:for2}
runs in time of
\(2^{O(r)} \cdot t\)~operations over~\(\mathbb F\)
and calls to~\(\dg\).
Finally,
in
\cref{lin:compress},
we build a max \((r-\gamma i)\)-representative
of the \(\gamma i\)-family~\(\cR_i\).
Since \(|\cR_i|\leq 2^r\cdot t\),
by \cref{prop:repset},
this works
in time of
\[
  O\Biggl( \biggl({r \choose \gam{}i}(\gam{}i)^\omega + {r \choose \gam{}i}^{\omega-1}\biggr)\cdot|\cR_i| \Biggr)\subseteq O((2^r r^\omega+2^{r\omega})\cdot 2^r\cdot t)\subseteq 2^{O(r)}\cdot t
\]
operations over~\(\mathbb F\).


\qed
\end{proof}

\subsection{Computing intersection representative families}
\label{sec:rep-intersect}

In this section,
we use \cref{thm:core-tool}
to compute
max intersection representatives
of the families of feasible
solutions to \spmc{}
with input sets of cardinality~\(\gamma\).
Concretely,
we show the following theorem,
which will also play a central
role in our algorithm for \mdmc{}.


\begin{theorem}
  \label[theorem]{lem:max-int-repr}
  Let $\{M_i =(U,\I_i)\}_{i=1}^m$~be
  linear matroids of rank~$r:=(\alp+\bet)\gam\geq 1$,
  \(\cH\subseteq 2^U\) be  a \(\gamma\)-family of size~\(t\),
  and \(\dw\colon\cB(\cH)\to\R\)~be an \dtext{}
  (cf.\ \cref{def:dtext}). 

  Given
  a
  representation~\(A_i\)
  of~\(M_i\) for each~\(i\in\{1,\dots,m\}\)
  over the same field~$\mathbb F$
  and  the value~\(\dw(\emptyset)\),
  one can
  compute
  a max intersection $\bet\gam$-representative
  of size at most~$r m \choose \alp\gam m$
  of the family
  \[\familyS = \Bigl\{ S = H_1 \uplus \dots \uplus H_\alp 
    \Bigm|
    S\in\bigcap_{i=1}^m \I_i\text{ and }
    H_j \in \cH\text{ for }j \in \{1,\dots, \alp \}\Bigr\}
  \]  
  
  with respect to~\(\dw\)
  in time of $2^{\bigO(rm)}  \cdot t+O(m^2rn)$~operations
  over $\mathbb F$ and calls to the function~\(\dg\)
  generating~\(\dw\).
\end{theorem}


\noindent
To prove \cref{lem:max-int-repr},
we reduce the \(m\)~matroid constraints
to a single matroid constraint.


To this end, we use a
folklore construction
sketched by \citet[page~359]{Law76}
in a reduction of the \textsc{Matroid Intersection}
to the \textsc{Matroid Parity} problem.
It works
at the expense of replacing
each universe element
by a ``block'' of \(m\)~copies that
is only allowed to be \emph{completely}
included in or excluded from an independent set.
We then use
our \cref{thm:core-tool}
to compute a representative
of the family of independent sets
that can be obtained as unions of these ``blocks''.
We now present
the folklore construction
and then prove \cref{lem:max-int-repr}.


\begin{lemma}
  \label[lemma]{lem:sum-matroid}
  Let $\{M_i=(U,\I_i)\}_{i=1}^m$~be
  linear matroids of rank $r$ and
  \(\cH\subseteq 2^U\).
  \begin{align*}
    U_{{\oplus}}&{}:=\{ u^{(1)},\ldots, u^{(m)} \mid u \in U \},\\
    f\colon 2^U\to 2^{U_{\oplus}}, X &{}\mapsto \{ u^{(1)},\ldots, u^{(m)} \mid u \in X \},\text{ and}\\
    \cH_{\oplus}&{}:=\{f(X)\mid X\in\cH\},
  \end{align*}
  Then,     for all~\(S,S'\subseteq U\),
  
  
  \begin{enumerate}[(i)]


  \item \label{sm:1}
    \(S\ne S'\iff f(S)\ne f(S')\), that is, \(f\)~is injective,
    
  \item \label{sm:2}
    \(f(S)\cup f(S')=f(S\cup S')\), and
  \item \label{sm:3}
    $S \cap S' = \emptyset \iff f(S) \cap f(S') = \emptyset$,
  \end{enumerate}
  and given \((r\times n)\)-representations~\(A_i\) of~\(M_i\) for all \(i\in\{1,\dots,m\}\)
  over the same field $\mathbb F$,
  one can,
  in time of $\bigO(m^2 \cdot r \cdot n)$~operations over $\mathbb F$,
  compute a
  \((r m \times n m)\)-representation
  of a matroid~$M_{\oplus}= (U_{\oplus},\I_{\oplus})$ over~$\mathbb F$  such that
  \begin{enumerate}[(i)]
    \setcounter{enumi}{3}
  \item \label{sm:4} for all $S\subseteq U$, $S \in \displaystyle\bigcap\limits_{i=1}^{m} \I_i\iff f(S) \in \I_{\oplus}$.
  \end{enumerate}
  
  
\end{lemma}
\begin{proof}
  We choose~\(M_{\oplus}\)
  to be the
  direct sum
  of pairwise disjoint copies~\(M_i'\) of~\(M_i\):
  \begin{align*}
  M_{\oplus}&\phantom:=(U_{\oplus},\I_{\oplus}) = \bigoplus_{i=1}^m M_i',&\text{where}&&
    M_i'&\phantom:=(U_i,I_i')\text{ with}\\
    U_i &:= \{ u^{(i)} \mid u \in U \}&\text{and}&&
    \I_i' &:= \{ \{ u_1^{(i)},\ldots,u_j^{(i)} \} \mid \{ u_1,\ldots,u_j \} \in \I_i \}.
  \end{align*}
  We get a \((r m \times n m)\)-representation
  over~$\mathbb F$
  of~\(M_{\oplus}\) in time of $\bigO(m^2 \cdot r\cdot n)$~operations 
  over~$\mathbb F$ 
  \citep[Exercise~6, p.~132]{Oxl92}.
  
  Properties \eqref{sm:1}--\eqref{sm:3}
  obviously hold by construction.
  It remains to prove \eqref{sm:4}.
  Let \(S=\{ u_1,\ldots,u_j \}\subseteq U\)
  and,
  for an arbitrary $i \in \{1,\ldots, m \}$,
  let $S_i = f(S) \cap U_i$.
  Then,
  $S_i = \{ u_1^{(i)},\ldots,u_j^{(i)}\}$
  and
  $S \in \I_i$
  if and only if
  $S_i \in \I_i'$.
  Thus,
  if $S \in \bigcap_{i=1}^{m} \I_i$,
  then  $S_i \in \I_i'$
  for all~$i \in \{1,\ldots,m\}$
  and, hence,
  $\bigcup_{i=1}^{m} S_i = f(S) \in \I_{\oplus}$
  by \cref{def:union} on direct sums.
  
  Conversely,
  if $f(S) \in \I_{\oplus}$,
  then $S_i \in \I_i'$
  for all~$i \in \{1,\ldots,m\}$
  and, therefore,
  $S \in \bigcap_{i=1}^{m} \I_i$.
\qed\end{proof}


\noindent
We now prove \cref{lem:max-int-repr}
using \cref{thm:core-tool},
replacing \(m\)~matroid
constraints to a single one


as described in \cref{lem:sum-matroid}


\begin{proof}[of \cref{lem:max-int-repr}]
  We will reduce
  the task of computing
  a max intersection \(\beta\gam\)-representative
  for the intersection of several matroids
  to the task
  of computing a max \(\beta\gam m\)-representative
  for a single matroid
  using \cref{thm:core-tool}.

  To this end,
  let $M_{{\oplus}}=(U_{{\oplus}},\I_{{\oplus}})$
  be the linear matroid
  of rank $rm = (\alp+\bet)\gam m$,
  $f\colon 2^U \rightarrow 2^{U_{\oplus}}$
  be the injective function,
  and
  \(\cH_{\oplus}=\{f(X)\mid X\in\cH\}\)
  be the \(\gam m\)-family
  
  
  
  
  
  created from~\(\{M_i\}_{i=1}^m\) and
  \(\cH\)
  
  using
  \cref{lem:sum-matroid}.
  For applying \cref{thm:core-tool},
  we compute an
  $(rm \times nm)$-representation~\(A\) of~$M_{{\oplus}}$
  in
  time of $O(m^2\cdot r\cdot n)$~operations
  over $\mathbb F$
  by \cref{lem:sum-matroid}.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Consider
  \begin{align*}
    \cS_{{\oplus}}&:=\{f(S)\mid S\in\cS\}
                  =\{S=f(H_1)\uplus\dots\uplus f(H_\alpha)\mid f(H_i)\in\cH_{\oplus}\text{ and }S\in \I_{\oplus}\},
  \end{align*}
  where equality is due to \cref{lem:sum-matroid}\eqref{sm:2} and \eqref{sm:4}.
  For the function~\(\dg\colon\R\times\cH\to\R\) generating~\(\dw\),
  consider the non\hyp decreasing in its first argument function
  \[
    \dg_{\oplus}\colon\R\times\cH_{\oplus}\to\R,\,\,
    (k,f(H))\mapsto \dg(k,H).
  \]
  Then,
  \(\dw_{\oplus}(\emptyset):=\dw(\emptyset)\)
  and \(\dg_{\oplus}\)
  fully determine a
  \dtext{}~\(\dw_{\oplus}\colon\cB(\cH_{\oplus})\to\R\).
  Since \(\dg_{\oplus}(k,f(H))=\dg(k,H)\)
  for all \(k\in\R\) and all \(f(H)\in\cH_{\oplus}\),
  one gets \(\dw_{\oplus}(f(X))=\dw(X)\)
  for all~\(f(X)\in \cB(\cH_{\oplus})\).

  


  Using \cref{thm:core-tool}
  on \(\cH_{\oplus}\), 
  we build a max \(\beta\gam m\)-representative~\(\cSs_{{\oplus}}\)
  of size~$rm \choose \alp \gam m$
  for~\(\cS_{{\oplus}}\)
  with respect to~\(\dw_{\oplus}\)
  in time of $2^{O(rm)}\cdot t$
  operations over~$\mathbb F$
  and calls to~\(\dg_{\oplus}\).
  Herein,
  one call to~\(\dg_{\oplus}\)
  is one call to~\(\dg\).
  Finally, we show that
  \begin{align*}
    \cSs&:=\{S\in\cS\mid f(S)\in\cSs_{{\oplus}}\}=
          \Bigl\{H_1\uplus\dots\uplus H_\alp\Bigm|
    H_i\in\cH\text{ and }
          \biguplus_{i=1}^\alp f(H_i)\in\cSs_{{\oplus}}\Bigr\}
  \end{align*}
  which
  has size~\(|\cSs_{\oplus}|\),
  is
  max \(\beta \gam\)-intersection
  representative of~\(\cS\)
  with respect to~\(\dw\).
  Note that it can be constructed in
  \(\alp\gam m\cdot|\cSs_{\oplus}|\)~time
  by simply iterating over
  the sets in~\(\cSs_{{\oplus}}\),
  replacing
  a group of elements~\(u^{(1)},\dots,u^{(m)}\)
  by element~\(u\).
  
  Let $Y \subseteq U$ with \(|Y|\leq\beta\gam\)
  and $X \in \mathcal \cS$ with
  $Y \uplus X \in \bigcap_{i=1}^m \I_i$.
  Then
  $f(Y) \uplus f(X) \in \I_{\oplus}$
  by \cref{lem:sum-matroid}\eqref{sm:3} and \eqref{sm:4}.
  Moreover, $f(X) \in \cS_{\oplus}$.
  By \cref{def:qrep},
  there is a set $X' \in \cSs_{\oplus}$ such that
  $f(Y) \uplus X' \in \I_{\oplus}$,
  and $\dw_{\oplus}(X') \geq \dw_{{\oplus}}(f(X))$.
  By construction of~\(\cSs\),
  there is an \(X''\in\cSs\)
  with \(f(X'')=X'\).
  Note that \(Y\cap X''=\emptyset\)
  by \cref{lem:sum-matroid}\eqref{sm:3}
  since \(f(Y)\cap f(X'') = f(Y)\cap X'=\emptyset\).
  Moreover,
  \(Y\cup X''\in\bigcap_{i=1}^m \I_i\)
  by \cref{lem:sum-matroid}\eqref{sm:4}
  since \(f(Y)\uplus f(X'')=f(Y)\uplus X'\in \I_{{\oplus}}\).
  Finally,
  \(\dw(X'')=\dw_{{\oplus}}(f(X''))=\dw_{{\oplus}}(X')\geq \dw_{{\oplus}}(f(X))=\dw(X)\).
\qed
\end{proof}


\subsection{Solving
  Set Packing with Matroid Constraints}
\label{sec:spmc-fpt}
In this section,
we apply \cref{lem:max-int-repr}
to provide a fixed\hyp parameter
algorithm for \spmc{}.
It will play a key role
in our algorithm for \mdmc{}
in \cref{sec:algorithm}.

\begin{theorem}
  \label[theorem]{thm:solve-spmc}
  \spmc{} on matroids of rank at most~\(r\)
  represented over a field~\(\mathbb F=\mathbb F_{p^d}\)
  is solvable in time
  of
  \(
  2^{O(\alp\gam m)}\cdot |\cH|^2\cdot\poly(r)+ m^2n\cdot\poly(r,\alp,\gam,p,d)
  \)
  operations over~\(\mathbb F\),
  where \(\gam\)~is an upper bound
  on the sizes of the sets in~\(\cH\).
\end{theorem}


\begin{proof}
  The algorithm will use
  \cref{lem:max-int-repr}
  to compute max intersection representatives.
  To make it applicable,
  we will
  \begin{enumerate}[(a)]
  \item\label{pf1} pad the sets in~\(\cH\) so
    that they have equal size,
  \item\label{pf-dtext}
    construct a  \dtext{} suitable for \spmc{}, and
  \item\label{pf2} truncate the input matroids
    so that they have equal rank.
  \end{enumerate}

  \eqref{pf1}
  We construct a family~$\cH'$
  from~\(\cH\) in which each set has
  size exactly~$\gam$.
  
  
  
  To this end,
  let $D := D_1 \uplus \dots \uplus D_{\alp}$~be a 
  set of $\alp\gam$~\emph{dummy elements}
  with $D \cap U = \emptyset$
  and
  $|D_i|=\gam$
  
  
  for $i\in \{1, \dots, \alp\}$.


  Now,
  for each $H \in \cH$,
  set \(\cH'\)~contains
  the sets~$H^{(1)},\ldots,H^{(\alp)}$,
  each \(H^{(i)}\) of which has size exactly~$\gam$
  and is obtained from~\(H\) by adding
  \(\gamma-|H|\)~arbitrary dummy elements
  from~$D_i$.
  Note that this step \eqref{pf1}
  can be executed in \(|\cH|\alp\gam\)~time.

  We also add the dummy elements
  to our matroids:
  For each input matroid~\(M_i\)
  of rank~\(r_i\), where \(i\in\{1,\dots,m\}\),
  consider
  the matroid~$M_i^*=(U^*,\I_i^*):= M_i \oplus (D,2^D)$
  of rank~\(r_i+\alp \gam\)
  with \(|U^*|=n+\alp \gam\) and
  
  
  
  note that
  \begin{equation}
    \begin{aligned}
      \text{there are sets $H_1,\ldots,H_\alp \in \cH$}
      &
      \text{\quad with $\biguplus_{i=1}^\alp H_i \in \bigcap_{i=1}^m \I_i$
        if and only if}\\
      \text{there are sets
        $H_1^{(1)},\ldots,H_\alp^{(\alp)} \in \cH'$}
      &
      \text{\quad with $\biguplus_{i=1}^\alp H_i^{(i)} \in \bigcap_{i=1}^m \I_i^*$}.
    \end{aligned}
    \label{pf4}
  \end{equation}

  \eqref{pf-dtext}
  For
  \(
  w' \colon \cH' \rightarrow \mathbb R,H\mapsto
  w(H\setminus D),
  \)
  as shown in \cref{ex:ws},
  the function
  \[
    w_{\Sigma}(X):=\max_{X=H_1\uplus\dots \uplus H_i\atop
      H_1,\dots,H_i \in \cH'}\sum_{j=1}^{i}w'(H_j)
  \]
  is \dtex{}
  with \(w_{\Sigma}(\emptyset)=0\)
  and the generating function
  \(\dg\colon\R\times\cH'\to\R, (k,H)\mapsto k+w'(H)\),
  which is computable in constant time,
  since,
  when generating a set~\(H'\in\cH'\)
  from a set~\(H\in\cH\),
  we can store the weight \(w'(H')=w(H)\)
  in the same data structure as~\(H'\).
  
  
  \eqref{pf2}
  We compute
  $\alp\gam$-truncations~\(M_1',\dots,\allowbreak M_m'\)
  
  of
  the matroids~$M_1^*,\ldots,\allowbreak M_m^*$.
  To this end,
  for each~\(i\in\{1,\dots,m\}\),
  we first compute
  a 
  representation~\(A_i^*\)
  of 
  matroid~$M_i^*$
  of rank~\(r_i+\alp\gam\)
  in
  $O((r_i+\alp\gam)(n+\alp\gam))$~operations
  over~$\mathbb F$.
  Then,
  we apply
  \cref{rem:same_field_trunc}
  in time of
  \begin{align*}
    O(m\cdot (n+\alp\gam)\cdot\alp\gam\cdot(r+\alp\gam))+(r+\alp\gam)^4\cdot (\alp\gam)^4\cdot d^2\sqrt p\cdot\polylog(r+\alp\gam,p,d)\\
    \subseteq mn\cdot\poly(r,\alp,\gam,p,d) \text{ operations over~$\mathbb F$}
  \end{align*}
  to obtain
  an $(\alp\gam \times (n+\alp\gam))$-representation~\(A_i'\)
  of \(M_i'\)
  over
  $\mathbb F' := \mathbb F_{p^{(r+\alp \gam)\alp\gam d}}$
  for each~$i \in \{1,\ldots,m\}$.
  
  
  Note that any operation over~\(\mathbb F'\)
  can be executed using
  \(\poly(r,\alp,\gam)\)~operations over~\(\mathbb F\).

  We now show an algorithm
  
  

  that computes
  the weight of an optimal
  solution to the input \spmc{} instance.
  
  
  
  
  
  The actual solution
  can then be retrieved via self\hyp reduction,
  calling this algorithm \(|\cH|\)~times.
  
  
  
  
  
  
  
  
  
  
  
  The algorithm works as follows.
  We apply
  \cref{lem:max-int-repr}
  to the matroids~$M_1',\ldots,\allowbreak M_m'$
  of rank~\(\alp\gam\)
  to compute a max 0-representative~\(\cSs\)
  of size ${\alp\gam m\choose \alp\gam m}=1$
  of the family
  \[
    \cS:=\Bigl\{ S=H_1 \uplus \dots \uplus H_\alp
    \Bigm|  S \in \bigcap_{i=1}^m\I'_i\text{ and }H_i \in \cH'\text{ for }i\in\{1,\dots,\alp\}\Bigr\}
  \]
  with respect to~\(w_{\Sigma}\)
  as defined in \eqref{pf-dtext}.
  This takes time of $2^{O(\alp\gam m)}\cdot |\cH|$~operations
  over $\mathbb F'$,
  plus \(m^2n\cdot \poly(\alp,\gam,r)\)~time
  for the application of \cref{lem:sum-matroid}
  in the proof of \cref{lem:max-int-repr}
  (which we will apply only
  once,
  not for every repeated call of the algorithm
  in the self\hyp reduction).
  

  Observe that,
  by \cref{def:qrep},
  \(\cSs\)~only contains
  the independent set~\(S\in\cS\)
  maximizing~\(w_{\Sigma}(S)\).
  We finally prove that
  \(\cSs\)~contains
  a set whose weight
  is exactly that
  of an optimal solution to
  our input \spmc{} instance
  if and only if that instance
  has a feasible solution.
  
  
  Thus,
  looking at \(\cSs\),
  we get the weight
  of an optimum solution~\(S^*\)
  to \spmc{} in constant time;
  the overall running time
  of the algorithm 
  (that is,
  of steps \eqref{pf1}--\eqref{pf2},
  one application of \cref{lem:sum-matroid},
  and \(|\cH|\)~computations
  of a representative family)
  is as stated in the theorem.
  
  ($\geq$)
  Let \(S^*:=\biguplus_{i=1}^\alp H_i\in\bigcap_{i=1}^m\I_i\)
  be an optimal solution to \spmc{}.
  One has $S:=\biguplus_{i=1}^\alp H_i^{(i)} \in \bigcap_{i=1}^m \I_i^*$
  by \eqref{pf4}.
  Since \(|S|=\alp\gam\),
  \(S\in \bigcap_{i=1}^m \I_i'\).
  
  
  Thus,
  \(S\in\cS\).
  Since \(\cSs\) is max 0-representative,
  there is an \(S'\in\cSs\)
  with
  \begin{align*}
    w_{\Sigma}(S')&\geq w_{\Sigma}(S)
                        
                        
                        
                        \geq
                        \sum_{i=1}^{\alp}
                        w'(H_i^{(i)})
                        =\sum_{i=1}^{\alp}
                        w(H_i).
  \end{align*}

  \noindent
  ($\leq$)
  For \(S\in\cSs\),
  there are
  \(H_1^{(1)},\dots,H_\alp^{(\alp)}\in\cH'\)
  such that
  \(\biguplus_{i=1}^\alp H_i^{(i)}\in\bigcap_{i=1}^m\I'_i\) and
  \[
    w_{\Sigma}(S)=
    \sum_{i=1}^{\alp}
    w'(H_i^{(i)})
    =\sum_{i=1}^{\alp}
    w(H_i),
  \]
  which is at most
  the weight of an optimal solution to \spmc{},
  because the~\(H_i\)
  are a feasible solution:
  
  
  
  $\biguplus_{i=1}^\alp H_i^{(i)} \in \bigcap_{i=1}^m \I_i^*$.
  Thus,
  by \eqref{pf4},
  $\biguplus_{i=1}^{\alp}H_i\in\bigcap_{i=1}^m\I_i$.
  \qed\end{proof}
  


  


  


\section{A fixed-parameter algorithm for \mdmc{}}
\label{sec:algorithm}

In this section,
we describe our fixed\hyp parameter algorithms
for \mdmc{},
thus proving \cref{thm:alg}.
First,
in \cref{sec:cc},
we reduce \mdmc{}
to a simplified problem variant.


In \cref{sec:uniclients},
we present an algorithm
for \mdmc{}
where we have only one facility matroid
and one uniform client matroid.
This eventually proves \cref{thm:alg}\eqref{thm:alg1}.
In \cref{sec:alggeneral},
we present an algorithm
for \mdmc{} on linear matroids,
thus proving \cref{thm:alg}\eqref{thm:alg2}.


\subsection{Color coding}
\label{sec:cc}

One major difficulty
in solving \mdmc{} is
that the profit
from opening a facility
depends on
which other facilities are already open.
To name an extreme example:
when opening only facility~\(u\),
it induces cost~\(c_u\)
and yields profit
from serving all the clients.
However,
when some other facility~\(v\)
is already open,
then additionally opening~\(u\)
induces cost~\(c_u\)
yet might not yield any profit
if all clients are more profitably
already served by~\(v\).
To avoid such interference
between facilities,
we reduce \mdmc{}
to an
uncapacitated facility location problem
with matroid and \emph{color constraints} (\mdmcc{}).


\pagebreak[3]
\begin{problem}[\mdmcc{}]
  \label{prob:mdmcc}
  \leavevmode
  \begin{compactdesc}
  \item[\normalfont\textit{Input:}]
    A universe~\(U\),
    a coloring~\(\col\colon U\to\{1,\dots,k+\ell\}\),
    a partition
    \(Z_1\uplus\dots\uplus Z_\ell=\{\ell+1,\dots,\ell+k\}\),
    for each pair~\(u,v\in U\)
    a \emph{profit}~\(p_{uv}\in\mathbb N\)
    gained when
    a facility at~\(u\) serves a client at~\(v\),
    for each~\(u\in U\)
    a \emph{cost}~\(c_u\in\mathbb N\)
    for opening a facility at~\(u\),
    \emph{facility matroids}~\(\{(U_i,A_i)\}_{i=1}^a\),
    and
    \emph{client matroids} \(\{(V_i,C_i)\}_{i=1}^c\),
    where~\(U_i\cup V_i\subseteq U\).
  \item[\normalfont\textit{Task:}]
    Find two sets \(A\uplus C\subseteq U\) such that
    \begin{enumerate}[(i)]
    \item\label{mdmcc:colored-fac} for each \(i\in\{1,\dots,\ell\}\),
      there is exactly one \(u\in A\) with \(\col(u)=i\), 
    \item \label{mdmcc:colored-client} for each \(i\in\{\ell+1,\dots,\ell+k\}\),
      there is exactly one \(v\in C\)
      with \(\col(v)=i\),
    \item\label{mdmcc:independent} \(
      \displaystyle
      A\in\bigcap_{i=1}^a A_i\text{\quad and\quad}C\in\bigcap_{i=1}^c C_i,
      \)
      
      
      
      
      
    \end{enumerate}
    and that maximizes
    \begin{align}
      \sum_{u\in A}\Bigl(-c_u+
      \smashoperator{\sum_{v\in C\cap Z(u)}}p_{uv}
      \Bigr),
      \label{mdmccgf}
      \text{ where }
      Z(u):=\{v\in U\mid
      \col(v)\in Z_{\col(u)}\}.
    \end{align}
  \end{compactdesc}
\end{problem}


\noindent
We call $A\uplus C$
a \emph{feasible solution}
if it satisfies~\eqref{mdmcc:colored-fac}--\eqref{mdmcc:independent},
not necessarily maximizing~\eqref{mdmccgf}.


In \mdmcc{},
a facility~\(u\) of color~\(i\)
gets profit
only from clients in~\(Z(u)\),
that is, from clients
with color in~\(Z_i\).
Moreover,
there can be only one facility of color~\(i\)
and the clients with a color in~\(Z_i\)
are only served by facilities of color~\(i\).
Thus,
the contribution of a facility~\(u\)
to the goal function of \mdmcc{}
is independent
from the contributions of other facilities,
which makes \mdmcc{} significantly
easier than \mdmc{}.
We prove the following lemma.
\begin{lemma}
  \label[lemma]{lem:turingred}
  If \mdmcc{} is solvable
  in \(t(k+\ell)\)~time,
  then
  \mdmc{}
  is solvable in
  \(2^{\bigO(r\log r)}(t(2r)+n)\log n\)~time,
  where \(r\)~is the minimum rank
  of the client matroids.
\end{lemma}

\noindent
To prove \cref{lem:turingred},
we will prove that
\begin{enumerate}[(a)]
\item\label{cc-dir1}
  any feasible
  solution to \mdmcc{}
  is a feasible solution
  with at least the same profit
  for \mdmc{}
  and
  
\item\label{cc-dir2}
  for any optimal solution~\(A\uplus C\)
  to \mdmc{},
  we can sufficiently quickly find
  a coloring
  and
  a partition~\(Z_1\uplus\dots\uplus Z_\ell\)
  such that
  \(A\uplus C\)~is a feasible
  solution
  with at least the same profit
  for \mdmcc{}.
\end{enumerate}

\noindent


Towards \eqref{cc-dir2},
note that
we cannot simply try out
all partitions and colorings;
for example,
there are
\(\bigO(r^n)\)~colorings---
too much for \cref{lem:turingred}.


However,
since there is a client matroid
of rank~\(r\),
there is an optimal solution
to \mdmc{}
such that \(|C|=\ka\)
and \(|A|=\ell\)
for some \(\ell\leq \ka\leq r\).
Thus,
without loss of generality
assuming \(U=\{1,\dots,n\}\),


the colorings in a
\emph{$(n,\ka+\ell)$-perfect hash family}
as defined below
will contain a coloring
such that the elements
of \(A\cup C\) get pairwise distinct colors:
\begin{definition}[\boldmath $(n,s)$-perfect hash family
  {\citep[Definition~5.17]{CFK+15}}]
  An \emph{\((n,s)\)-perfect hash family}
  is a set~\(\mathcal F\)
  of functions~\(f\colon\{1,\dots,n\}\to\{1,\dots,s\}\)
  such that,
  for any \(S\subseteq\{1,\dots,n\}\)
  with \(|S|\leq s\),
  there is a function~\(f\in \mathcal F\)
  
  injective on~\(S\).
\end{definition}

\begin{proposition}[{\citep[Theorem~5.18]{CFK+15}}]
  \label[proposition]{prop:perfhash}
  An \((n,s)\)-perfect hash family
  of size \(e^ss^{\bigO(\log s)}\log n\)
  can be computed
  in
  \(e^ss^{\bigO(\log s)}n\log n\)~time.
\end{proposition}

\noindent
In the following,
we will prove that
\cref{alg:turingred}
correctly solves \mdmc{}.

\begin{algorithm}[t]
  \KwIn{An \mdmc{} instance:
    universe~\(U=\{1,\dots,n\}\),
    profits~\(p_{uv}\in\N\)
    for each~$u,v\in U$,
    costs~\(c_u\in\N\)
    for each~$u\in U$,
    facility matroids \(\{(U_i,A_i)\}_{i=1}^a\),
    and client matroids \(\{(V_i,C_i)\}_{i=1}^c\)
    of minimum rank~\(r\),
    where \(U_i\cup V_i\subseteq U\).}
  \KwOut{An optimal solution~\(A\uplus C\) to \mdmc{}.}
  \ForEach(\nllabel{lin:guessell}){$1\leq\ell\leq\ka\leq r$}{
    \(\mathcal F\gets(n,\ell+\ka)\)-perfect hash family.
    \nllabel{lin:perfhash}\;
    \ForEach(\nllabel{lin:forhash}){$f\in\mathcal F$}{
      \ForEach(\nllabel{lin:x}){$X\subseteq\{1,\dots,\ell+k\}$ with \(|X|=\ell\)}
      {
        \nllabel{lin:startlinear}
        bijectively rename colors in~\(f\) and~\(X\)
        so that \(X=\{1,\dots,\ell\}\).\;
        \ForEach(\nllabel{lin:partitions}){partition
          \(Z_1\uplus\dots\uplus Z_\ell=\{\ell+1,\dots,\ell+\ka\}\)}{
          
          
          
          
          
          
          
          
          
          Solve \mdmcc{} with
          universe~\(U\),
          coloring~\(f\),
          partition~\(Z_1\uplus\dots\uplus Z_\ell\),
          profits~\((p_{uv})_{u,v\in U}\),
          costs~\((c_u)_{u\in U}\),
          matroids \(\{(U_i,A_i)\}_{i=1}^a\)
          and \(\{(V_i,C_i)\}_{i=1}^c\)
          \nllabel{lin:solve}.\;
        }
      }
    }
  }
  \KwRet{maximum\hyp profit
    \mdmcc{} solution found in any iteration.}
  \nllabel{lin:return}\;
  \caption{Algorithm for
    the proof of \cref{lem:turingred}.}
  \label[algorithm]{alg:turingred}
\end{algorithm}

\begin{lemma}
  \label[lemma]{lem:mdmcc-to-mdmc}
  Any \mdmcc{} solution~\(A\uplus C\)
  is also an \mdmc{} solution
  with at least the same profit.
\end{lemma}

\begin{proof}
  Let \(A\uplus C\) be
  any \mdmcc{} solution.
  Obviously,
  it is also feasible for \mdmc{}.
  Its profit as an \mdmcc{} solution is
  given by \eqref{mdmccgf}
  and,
  denoting
  \(\bar p_{uv}:=p_{uv}\)
  if $v\in Z(u)$ and \(\bar p_{uv}:=0\) otherwise,
  is
  \begin{align*}
    &\sum_{u\in A}\Bigl(-c_u+
      \smashoperator{\sum_{v\in C\cap Z(u)}}p_{uv}
      \Bigr)
    ={}\sum_{u\in A}\Bigl(-c_u+\sum_{v\in C}\bar p_{uv}\Bigr)
    ={}-\sum_{u\in A}c_u+\sum_{v\in C}\sum_{u\in A}
         \bar p_{uv}.
    \\
    \intertext{Since, for each~\(v\in C\),
    there is exactly one~\(u\in A\)
    with \(v\in Z(u)\),
    this is}
    \leq
    {}&-\sum_{u\in A}c_u+\sum_{v\in C}\max_{u\in A} p_{uv},
  \end{align*}
  which is exactly the cost of~\(A\uplus C\)
  as a solution to \mdmc{} as given by \eqref{mdmcgf}.
\qed\end{proof}


\begin{lemma}
  \label[lemma]{lem:algcorrect}
  \cref{alg:turingred} is correct.
\end{lemma}

\begin{proof}
  Let \(A\uplus C\)~be
  an optimal solution to \mdmc{}
  such that \(A\)~is of minimum size.
  We show that \cref{alg:turingred}
  outputs a solution to \mdmc{}
  of equal profit.
  
  Since one of the client matroids has rank~\(r\),
  \(|A|=\ell\) and~\(|C|=\ka\)
  such that \(1\leq \ell\leq\ka\leq r\).
  \cref{alg:turingred}
  tries these \(\ell\) and~\(\ka\) in
  \cref{lin:guessell}.
  Thus,
  the \((n,\ka+\ell)\)-perfect hash family~\(\mathcal F\)
  generated in \cref{lin:perfhash}
  contains a function~\(\col\colon U\to\{1,\dots,\ka+\ell\}\)
  that is bijective restricted to~\(A\uplus C\).
  \cref{alg:turingred}
  tries this~\(\col\) in \cref{lin:forhash}.
  Since \(|A|=\ell\)
  contains elements of pairwise
  distinct colors,
  \cref{alg:turingred}
  in \cref{lin:x}
  iterates over the color set~\(X\) of~\(A\)
  and renames all colors so that \(X=\{1,\dots,\ell\}\).
  We get that \(A\)~contains
  exactly one element of each color of \(X=\{1,\dots,\ell\}\)
  and that \(C\)~contains
  exactly one element of each color of~\(\{\ell+1,\dots,\ell+k\}\).
  
  Now,
  recall that \(U=\{1,\dots,n\}\)
  and,
  for each \(v\in C\), let \(m(v)\in A\)~be
  the facility with minimum index
  that serves~\(v\) with maximum profit,
  that is,
  \[m(v):=\min\{u\in A\mid p_{uv}=\max_{w\in A}p_{wv}\}.\]
  Then,
  for each~\(u\in A\),
  there is a \(v\in C\)
  such that \(m(v)=u\):
  otherwise,
  we can rewrite the goal function \eqref{mdmcgf}
  of \mdmc{}
  as
  \[
    \sum_{v\in C}\max_{u\in A}p_{uv}-\sum_{u\in A}c_u=
    \sum_{v\in C}p_{m(v),v}-\sum_{u\in A}c_u,
  \]
  and removing~\(u\) from~\(A\)
  would yield a solution
  to \mdmc{} with at least the same profit but smaller~\(A\),
  contradicting the minimality of~\(A\).
  
  Thus,
  for each \(i\in\{1,\dots,\ell\}\),
  the set~\(Z_i\)~of colors of the clients~\(v\)
  served by a facility~\(m(v)\) of color~\(i\),
  that is,
  \begin{align*}
    Z_i&:=\{\col(v)\mid v\in C, m(v)=u, \col(u)=i\},
  \end{align*}
  is nonempty. Hence,
  \(Z_1\uplus\dots\uplus Z_\ell=\{\ell+1,\dots,\ell+\ka\}\)
  is a partition:
  \begin{itemize}
  \item Equality follows since \(C\)~contains exactly one element of each color of~\(\{\ell+1,\dots,\ell+k\}\)
    and \(m(v)\)~is defined for each~\(v\in C\).
  \item Pairwise disjointness follows
    since \(m(v)\)~for each client~\(v\in C\) is unique.
  \end{itemize}
  \noindent
  Since \(Z_1\uplus\dots\uplus Z_\ell\)~is a partition,
  \cref{alg:turingred} in \cref{lin:partitions}
  iterates over this partition
  and  
  \(A\uplus C\)~is a feasible solution
  to the \mdmcc{} instance in this iteration.
  We show that its profit as an \mdmcc{}
  solution,
  given by \eqref{mdmccgf},
  is the same as the profit as an \mdmc{} solution,
  given by \eqref{mdmcgf}.
  To this end,
  denote
  \[
    \bar p_{uv}:=
    \begin{cases}
      p_{uv}&\text{ if $m(v)=u$, and}\\
      0&\text{ otherwise},
    \end{cases}
  \]
  and observe that,
  for \(u\in A\) and~\(v\in C\),
  one has
  \(m(v)=u\) if and only if
  \(\col(v)\in Z_{\col(u)}\).
  By choice in \eqref{mdmccgf},
  this is if and only if
  \(v\in C\cap Z(u)\).
  Thus, the cost of~\(A\uplus C\)
  as a solution to \mdmc{} is
  \begin{align*}
    \sum_{v\in C}\max_{u\in A}p_{uv}-\sum_{u\in A}c_u
    =\sum_{v\in C}\sum_{u\in A}\bar p_{uv}-\sum_{u\in A}c_u
    =\sum_{u\in A}\sum_{v\in C\cap Z(u)} p_{uv}-\sum_{u\in A}c_u,
  \end{align*}
  
  
  
  
  
  
  
  which is exactly the profit~\eqref{mdmccgf}
  of~\(A\uplus C\)
  as a solution to the \mdmcc{} instance
  given solved in this iteration.
  Thus,
  in \cref{lin:return},
  \cref{alg:turingred}
  will return an \mdmcc{}
  solution with at least this profit.
  By \cref{lem:mdmcc-to-mdmc},
  this will be an \mdmc{} solution
  of at least the same profit.
  Since \(A\uplus C\)~is
  an optimal \mdmc{} solution,
  we conclude that the solution
  returned by \cref{alg:turingred}
  is also optimal.
\qed\end{proof}

\noindent
We can now complete
the reduction of \mdmc{} to \mdmcc{}.

\begin{proof}[of \cref{lem:turingred}]
  We have shown in \cref{lem:algcorrect}
  that \cref{alg:turingred}
  correctly solves \mdmc{}.
  It remains to analyze the running time.
  
  The loop in \cref{lin:guessell}
  makes \(r\cdot(r+1)/2\)~iterations.
  Observe that
  \(\ell+k\leq 2r\).
  By \cref{prop:perfhash},
  the perfect hash family
  in \cref{lin:perfhash}
  is computable in
  \(e^{\ell+\ka}\cdot(\ell+\ka)^{\bigO(\log(\ell+\ka))}\cdot
  n\log n\)~time
  and
  the loop in \cref{lin:forhash}
  makes
  \(e^{\ell+\ka}\cdot(\ell+\ka)^{\bigO(\log(\ell+\ka))}\cdot\log n\)~iterations.
  \Cref{lin:startlinear} works in \(\bigO(n)\)~time,
  whereas \cref{lin:solve} works
  in \(t(k+\ell)\)~time
  by assumption.
  There are at most \(\ell^{\ell+k}\)~variants
  to chose \(X\uplus Z_1\uplus \dots\uplus Z_{\ell}\).
  Thus, the overall running time of the algorithm is
  \(2^{\bigO(r\log r)}(t(2r)+n)\log n\).
\qed\end{proof}


\subsection{One arbitrary facility matroid and
  one uniform client matroid}
\label{sec:uniclients}

In this section,
we prove \cref{thm:alg}\eqref{thm:alg1}:
an algorithm that solves
\mdmc{} in \(2^{\bigO(r\log r)}\cdot n^2\)~time
if there is only one,
yet arbitrary (not necessarily linear)
facility matroid
and one uniform client matroid of rank~\(r\).
To this end,
we show:
\begin{proposition}
  \label{lem:mdmccpoly}
  \mdmcc{} is solvable in \(O(\ell n^2)\)~time
  if there is one facility matroid
  given as an independence oracle
  and one client matroid
  that is uniform.
\end{proposition}

\noindent
Then,
\cref{thm:alg}\eqref{thm:alg1}
follows from \cref{lem:mdmccpoly,lem:turingred}.
To present the algorithm
for the proof of \cref{lem:mdmccpoly},
we introduce the following notation:
\begin{definition}
  \label{def:ui}
  For a universe~\(U\)
  with coloring~\(\col\colon\allowbreak U\to\{1,\dots,k+\ell\}\),
  we denote by $U(i):=\{u\in U\mid \col(u)=i\}$
  the elements of color~\(i\).
\end{definition}
\begin{algorithm}[t]
  \KwIn{An \mdmcc{} instance:
    a universe~\(U=\{1,\dots,n\}\),
    profits~\(p_{uv}\in\N\) for each~$u,v\in U$,
    costs~\(c_u\in\N\) for each~$u\in U$,
    a~coloring~\(\col\colon U\to\{1,\dots,k+\ell\}\),
    a facility matroid~\((U_1,A_1)\),
    a uniform client matroid \((V_1,C_1)\) of rank~\(r\),
    where~\(U_1\cup V_1\subseteq U\), and a
    partition~\(Z_1\uplus\dots \uplus Z_\ell=\{\ell+1,\dots,\ell+k\}\).}
  \KwOut{An optimal solution~\(A\uplus C\) to \mdmcc{}.}
  \lIf(\nllabel{lin:check-kr}){$k>r$}{\KwRet{No solution exists}.}
  \lIf(\nllabel{lin:checkcol}){$\{\ell+1,\dots,\ell+k\}\nsubseteq \{\col(v)\mid v\in V_1\}$}
  {\KwRet{No solution exists}.}
  
  
  
  \ForEach{$u\in U$}
  {
    \(\displaystyle
    F(u)\gets\{\argmax_{v\in V_1\cap U(j)}p_{uv}\mid j\in Z_{\col(u)}\}\).
    \nllabel{lin:fu}\;
    \(w(u)\gets -c_u+\sum_{v\in F(u)}p_{uv}\).
    \nllabel{lin:wu}\;
  }
  Compute \(A\in A_1\) 
  maximizing \(\sum_{u\in A}w(u)\)
  and
  containing exactly one element of each color
  \(\{1,\dots,\ell\}\).
  
  
  
  
  \nllabel{lin:compA}\;
  \lIf(\nllabel{lin:check-A}){\(A\) not found}{
    \KwRet{No solution exists}.
    \nllabel{lin:nosolution}}
  \(C\gets\bigcup_{u\in A}F(u)\).
  \nllabel{lin:compC}\;
  \KwRet{$A\uplus C$.}
  \nllabel{lin:retAC}\;
  \caption{Algorithm for the proof of \cref{lem:mdmccpoly}.}
  \label{alg:mdmccpoly}
\end{algorithm}

\noindent
To prove \cref{lem:mdmccpoly},
we use \cref{alg:mdmccpoly},
which solves \mdmcc{} as follows.
In \cref{lin:fu},
for each facility~\(u\),
it computes a set~\(F(u)\)
containing of each color in~\(Z_{\col(u)}\)
exactly one client~\(v\in V_1\)
that maximizes~\(p_{uv}\).
The intuition is that
if facility~\(u\) will be part of a solution,
then the clients~\(F(u)\) will
\emph{follow}~\(u\) into the solution.
In \cref{lin:wu},
it assigns
to each facility~\(u\)
a weight~\(w(u)\),
which is the profit
gained from serving
the clients in~\(F(u)\) by~\(u\)
minus the cost for opening facility~\(u\).
Finally,
in \cref{lin:compA},
it computes a maximum\hyp
weight set~\(A\in A_1\)
containing exactly one facility
of each color~\(\{1,\dots,\ell\}\)
and chooses \(C:=\bigcup_{u\in A}F(u)\).
The crucial point herein is
that the set~\(A\) can be computed
as the
maximum\hyp weight common independent set
of size~\(\ell\)
of two matroids,
which can be done in polynomial time
\citep[Sections~41.3 and~41.3a]{Sch03}.
In the following,
we prove the correctness
and the running time of
\cref{alg:mdmccpoly}.


\begin{lemma}
  \label[lemma]{lem:mdmccpoly-correct}
  \cref{alg:mdmccpoly} is correct.
\end{lemma}

\begin{proof}
  First, assume that
  \cref{alg:mdmccpoly}
  returns some \(A\uplus C\)
  in \cref{lin:retAC}.
  We show that
  \(A\uplus C\)~is
  a feasible solution to
  the input \mdmcc{} instance.
  By construction of~\(A\)
  in \cref{lin:compA},
  \(A\in A_1\) and contains exactly on element
  of each color~\(\{1,\dots,\ell\}\).
  Thus,
  \cref{prob:mdmcc}\eqref{mdmcc:colored-fac}
  is satisfied.
  Since \(Z_1\uplus\dots\uplus Z_\ell\)~is
  a partition of~\(\{\ell+1,\dots,\ell+k\}\)
  and
   
  \cref{lin:checkcol}
  has been passed,
  \(C=\bigcup_{u\in A}F(u)\)
  for the sets~\(F(u)\subseteq V_1\) computed
  in \cref{lin:fu}
  contains 
  
  
  
  
  
  exactly one element
  of each color~\(\{\ell+1,\dots,\ell+k\}\)
  and \eqref{mdmcc:colored-client} is satisfied.
  Thus, \(C\subseteq V_1\) and \(|C|=k\).
  Moreover,
  
  \(k\leq r\)
  since \cref{lin:check-kr}
  has been passed.
  Thus,
  since \((V_1,C_1)\)~is a uniform
  matroid of rank~\(r\),
  it follows that \(C\in C_1\)
  and \eqref{mdmcc:independent} is satisfied.
  We conclude that
  \(A\uplus C\)~is a feasible solution.

  \looseness=-1
  Now assume that there is
  an optimal solution~\(A^*\uplus C^*\)
  to \mdmcc{}.
  
  
  We show that
  \cref{alg:mdmccpoly}
  returns a solution with the same profit.
  First,
  since \(C^*\)~contains
  exactly one vertex of each color
  \(\{\ell+1,\dots,\ell+k\}\)
  by \cref{prob:mdmcc}\eqref{mdmcc:colored-client},
  we get \(|C^*|=k\).
  Second,
  since \(C^*\in C_1\) by \eqref{mdmcc:independent},
  we get \(C^*\subseteq V_1\) and \(k=|C^*|\leq r\).
  Thus,
  the tests in \cref{lin:check-kr,lin:checkcol}
  pass.
  Thus,
  \cref{lin:compA}
  of
  \cref{alg:mdmccpoly}
  computes a set~\(A\in A_1\)
  containing exactly
  one element of each color~\(\{1,\dots,\ell\}\)
  (by \eqref{mdmcc:colored-fac},
  \(A^*\) witnesses the existence of such a set),
  a corresponding set~\(C=\bigcup_{u\in A}F(u)\)
  in \cref{lin:compC},
  and finally
  returns \(A\uplus C\) in \cref{lin:retAC},
  which we already proved to be a feasible solution
  for \mdmcc{}.
  It remains to
  compare the profit of~\(A\uplus C\)
  to that of~\(A^*\uplus C^*\).
  To this end,
  the goal function \eqref{mdmccgf} for~\(A^*\uplus C^*\)
  can be rewritten as
  \begin{align*}
    \sum_{u\in A^*}w'(u)&&\text{for}&&w'(u):=&-c_u+\smashoperator{\sum_{v\in C^*\cap Z(u)}}p_{uv}.
  
  
\intertext{In comparison,
  consider the weight~\(w(u)\)
  assigned to each \(u\in A^*\)
  as in \cref{lin:wu} of \cref{alg:mdmccpoly}.
  Since, for each~\(u\in A\) with \(\col(u)=i\),}
&&&&    w(u)=&      -c_u+\smashoperator{\sum_{v\in F(u)}}p_{uv}=-c_u+\sum_{j\in Z_i}\max_{v\in V_1\cap U(j)}p_{uv},
  \end{align*}
  one has \(w(u)\geq w'(u)\).
  Since \(A\)~computed in \cref{lin:compA}
  maximizes \(\sum_{u\in A}w(u)\),
  \begin{align*}
    \sum_{u\in A^*}w'(u)

      \leq \sum_{u\in A}w(u)
      =\sum_{u\in A}
      \Bigl(
      -c_u+\smashoperator{\sum_{v\in F(u)}}p_{uv}
      \Bigr)
      =\sum_{u\in A}
      \Bigl(
      -c_u+\smashoperator{\sum_{v\in C\cap Z(u)}}p_{uv}
      \Bigr),
  \end{align*}
  which is exactly the profit
  of solution~\(A\uplus C\) to \mdmcc{}.
\qed\end{proof}

\noindent
Having shown the correctness of \cref{alg:mdmccpoly},
we now analyze its running time.

\begin{lemma}
  \label[lemma]{lem:mdmccpoly-time}
  \cref{alg:mdmccpoly} can be run in \(\bigO(\ell n^2)\)~time
  if the matroid \((U_1,A_1)\)
  is given as an independence oracle.
\end{lemma}

\begin{proof}
  Lines~\ref{lin:check-kr} to \ref{lin:wu},
  \ref{lin:compC}, and \ref{lin:retAC}
  are easy to implement in \(\bigO(n^2)\)~time.
  We show how to execute \cref{lin:compA} efficiently.
  To this end,
  
  consider the partition
  matroid~\((U_1',B)\)
  in which a subset of~\(U_1\)
  is independent
  if it contains at most one element
  of each color~\(\{1,\dots,\ell\}\)
  and no elements of other colors.
  \Cref{lin:compA} is then
  computing a set~\(A\) of maximum weight
  and cardinality~\(\ell\)
  that is independent
  in both matroids~\((U_1,A_1)\) and~\((U_1,B)\).
  This can be done in
  \(\bigO(\ell n^2)\)~time
  \citep[Sections~41.3 and~41.3a]{Sch03}.
  
  
\qed\end{proof}

\noindent
\cref{lem:mdmccpoly-time,lem:mdmccpoly-correct,lem:turingred}
together finish
the proof of \cref{thm:alg}\eqref{thm:alg1}.


\subsection{Facility and client matroids representable over the same field}
\label{sec:alggeneral}
In this section,
we prove \cref{thm:alg}\eqref{thm:alg2}: \mdmc{} is fixed\hyp parameter tractable parameterized by the number of matroids and the minimum rank over all client matroids
if all matroids are representable
over the same field.
To this end,
we prove the following,
which, together with \cref{lem:turingred},
yields \cref{thm:alg}\eqref{thm:alg2}.
\begin{proposition}
  \label{lem:mdmccfpt}
  An optimal solution to an \mdmcc{} instance~\(\I\)
  can be found in
  $f(a+c+k+\ell)\cdot \poly(|\I|)$~time
  if representations
  of the \(a\)~facility matroids
  and \(c\)~client matroids
  over the same field~\(\F_{p^d}\) are given
  
  
  for some prime~\(p\) polynomial in~\(|\I|\).
  
  
  
  
\end{proposition}
The algorithm for \cref{lem:mdmccfpt}
is more involved
than \cref{alg:mdmccpoly},


which breaks in
the presence of client matroids,
even a single one:
we cannot guarantee
that the sets~\(F(u)\)
chosen in \cref{lin:fu} of \cref{alg:mdmccpoly}
are independent in the client matroids
or that their union will be.
Ideally,
one would we able to choose
from all possible subsets~\(F(u)\subseteq Z(u)\)
of clients that could be served by~\(u\),
yet there are too many.
Here the \emph{max intersection representative families}
that we construct in \cref{sec:rep-intersect}
come into play:

using \cref{lem:max-int-repr},
we compute a family~\(\cFs(u)\)
so that, if there is any set of clients
that can be served by~\(u\)
and that is independent in all client
matroids together with the clients
served by other facilities,
then \(\cFs(u)\)~contains
at least one such subset
yielding at least the
same profit.
Using \cref{thm:solve-spmc},
we can then compute
disjoint unions of these
sets maximizing profit.
To describe the algorithm,
we introduce some notation.

\begin{definition}
  For a universe~\(U\)
  with coloring~\(\col\colon\allowbreak U\to\{1,\dots,k+\ell\}\) and \(U(i)\) as in \cref{def:ui},
  we denote by
  \begin{align*}\allowdisplaybreaks
    U_A&:=\smashoperator{\bigcup_{i=1}^\ell} U(i)&&\text{ is the set of \emph{facilities}, and}\\
    U_C&:=\smashoperator{\bigcup_{i=\ell+1}^{\ell+k}} U(i)&&\text{ is the set of \emph{clients}.}
  \end{align*}
\end{definition}

\begin{algorithm}[t]
  \KwIn{An \mdmcc{} instance:
    universe~\(U=\{1,\dots,n\}\),
    partition~\(Z_1\uplus\dots \uplus Z_\ell=\allowbreak\{\ell+1,\dots,\ell+k\}\),
    coloring~\(\col\colon U\to\{1,\dots,k+\ell\}\),
    profits~\(p_{uv}\in\N\)
    for each~$u,v\in U$,
    costs~\(c_u\in\N\)
    for each~$u\in U$,
    facility matroids $\mathcal A = \{ (U_i,A_i) \}_{i=1}^a$,
    client matroids $\mathcal C = \{ (V_i,C_i) \}_{i=1}^c$,
    all given as representations over the same finite field,
    where $U_i,V_i \subseteq U$.}
  \KwOut{An optimal solution~\(A\uplus C\) to \mdmcc.}
  \(M_P\gets (U,\{ I \subseteq U \mid\)
  \(I\)~has at most one element
  of each color in \(\{1,\dots,k+\ell\})\).
  \label{alg2:color-matroid}
  \;
  \(\mathcal M\gets\{M_P\}\cup\{M\vee (U_C,2^{U_C})\mid M\in\mathcal A\}\cup\{M\vee (U_A,2^{U_A})\mid M\in\mathcal C\}\).
  \label{alg2:mat-ext}\;
  \lIf{some matroid in \(\mathcal M\) has rank
    less than \(k+\ell\)}{\KwRet{No solution exists.}}
  \nllabel{alg2:smallrank}
  Truncate all matroids in~$\mathcal M$
  to rank~$k+\ell$ (using \cref{rem:same_field_trunc}).
  \label{alg2:truncation}\;
  \ForEach(\nllabel{alg2:for-loop}){$u \in U_A$ and \(i:=\col(u)\)}{
  
  
  
  
  
  
  
  
  
  
  \(\widehat\cF(u)\gets\)
  max intersection~$(k+\ell-|Z_{i}|)$-representative for the family
  \[\cF(u):=\{ I \subseteq Z(u)\mid
    I\text{ is independent in each of } \mathcal M
    \text{ and } |I|=|Z_i|\}
  \]
  with respect to
  weights~$w_u\colon 2^U\to\N,I\mapsto\sum_{v\in I}p_{uv}$ (via \cref{lem:max-int-repr}).
  \label{alg2:get-followers}\;
  $\cFs[u] \gets \{ X \cup \{ u \} \mid X \in \cFs(u) \}$.
  \nllabel{alg2:pad-followers}\;
  
  
}
$\cFs \gets \bigcup_{u\in U_A}\cFs[u]$.
\label{alg2:the-family}\;
  
  \(S_1,\dots,S_\ell\gets\) solution to
  \spmc{}  with matroids~\(\mathcal M\),
  family~\(\cFs\), and
  weights $w\colon \cFs\to\Z,X\mapsto w_u(X\setminus\{u\})-c_u$, where $\{u\}=X\cap U_A$ (via \cref{thm:solve-spmc}).
  
  
  
  
  \nllabel{alg2:ask-marx-for-help}\;
  \lIf(){not found}{
    \KwRet{No solution exists}.
  }
  $A \gets U_A \cap (S_1 \cup \dots \cup S_\ell)$.\;
  $C \gets U_C \cap (S_1 \cup \dots \cup S_\ell)$.\;
  \KwRet{$A \uplus C$}.\nllabel{alg2:retsol}\;

  \caption{Algorithm for the proof of \cref{lem:mdmccfpt}}
  \label{alg:mdmccfpt}
\end{algorithm}

\noindent
\cref{alg:mdmccfpt}
now solves \mdmcc{} as follows.
In \cref{alg2:color-matroid},
it constructs 


a multicolored matroid~\(M_P\)
that will ensure that


any independent
set of \(k\)~facilities
and \(\ell\)~clients
fulfills
\cref{prob:mdmcc}\eqref{mdmcc:colored-fac}
and \eqref{mdmcc:colored-client}.
In \cref{alg2:mat-ext},
it computes a family~\(\mathcal M\)
of matroids that contains~\(M_P\)
and all facility and client matroids,
which
are extended 

so that
a set~$A \uplus C \subseteq U$
is independent in all of them
if and only if $A$~is independent
in all facility matroids
and $C$~is independent in all client matroids.
Now,
if one of the matroids in~\(\mathcal M\) has rank
less than~\(k+\ell\),
then there is no common independent
set of \(\ell\)~facilities
and \(k\)~clients,
which is checked in \cref{alg2:smallrank}.

The truncation in
\cref{alg2:truncation}
thus results in each matroid in~\(\mathcal M\)
having rank exactly~\(k+\ell\),
which is needed
to apply \cref{lem:max-int-repr}
in
\cref{alg2:get-followers}.


In \cref{alg2:get-followers},
we construct for each~$u \in U_A$
with \(\col(u)=i\)
a max intersection~$(k + \ell - |Z_i|)$-representative~$\cFs(u)$
for the family~\(\cF(u)\)
of all sets of clients
that could potentially be served by~$u$
in a solution.
Afterwards, in \cref{alg2:the-family},
we construct a family of sets,
each consisting of one facility~$u \in U_A$
and a potential client set from~$\cFs(u)$.
Finally,
in \cref{alg2:ask-marx-for-help},
we will use \cref{thm:solve-spmc}
to combine $\ell$~of such sets
into a set that is independent in all matroids
in~$\mathcal M$ and yields maximum profit.
To prove \cref{lem:mdmccfpt},
we now show that
\cref{alg:mdmccfpt}
is correct and
analyze its running time.

\begin{lemma}
  \label{lem:alg2-feasible}
  Any solution output by \cref{alg:mdmccfpt}
  is feasible for \mdmcc{}.
\end{lemma}

\begin{proof}
  If \cref{alg:mdmccfpt}
  outputs a solution in \cref{alg2:retsol},
  then, in \cref{alg2:ask-marx-for-help},
  it found
  sets~$S_1,\dots,S_{\ell} \in \cFs$
  such that \(S=S_1\uplus\dots\uplus S_{\ell}\)
  is independent in all matroids~$\mathcal M$.
  We show that \(A\uplus C\)
  for
  $A = S \cap U_A$
  and
  $C = S \cap U_C$ is a feasible solution for \mdmcc{},
  that is, it satisfies
  properties
  \cref{prob:mdmcc}\eqref{mdmcc:colored-fac}--\eqref{mdmcc:independent}.

  \eqref{mdmcc:colored-fac} and \eqref{mdmcc:colored-client}:
  Observe that each set in~$\cFs$
  (constructed in \cref{alg2:the-family})
  contains
  exactly one facility~$u \in U_A$
  and \(|Z_i|\)~elements from~\(U_C\)
  for \(i=\col(u)\).
  Thus,
  \[
    |S|=\sum_{i=1}^\ell|S_i|=\ell+\sum_{i=1}^\ell|Z_i|=\ell+k
  \]
  since \(Z_1\uplus\dots\uplus Z_\ell=\{\ell+1,\dots,\ell+k\}\).
  Since \(S\)~is independent
  in the multicolored matroid~$M_P$,
  it follows that \(S\)~contains
  exactly one facility and exactly one client
  of each color.
  Since \(A=S\cap U_A\) and \(C=S\cap U_C\),
  \eqref{mdmcc:colored-fac} and \eqref{mdmcc:colored-client}
  hold.


  \eqref{mdmcc:independent}:
  Since \(A\)~is independent in
  all matroids of~\(\mathcal M\),
  it is independent in all matroids
  of~\(\{M\vee (U_C,2^{U_C})\mid M\in\mathcal A\}\).
  Since \(A\subseteq U_A\) and thus
  \(A\cap U_C=\emptyset\),
  it follows that \(A\)~is independent
  in all matroids in~\(\mathcal A\).
  Analogously,
  it follows that \(C\)~is independent
  in all matroids in~\(\mathcal C\).
  
  
  
  
  
  
  
  
  
  
  
  
  
  \qed
\end{proof}

\begin{lemma}
\label[lemma]{lemma:alg2-correct}

Given a feasible
\mdmcc{} instance,
\cref{alg:mdmccfpt} outputs
a solution of maximum profit.
\end{lemma}


\begin{proof}


  
  
  
  
  
  
  
  
  Let \(S=A\uplus C\)
  be an optimal solution to \mdmcc{}.
  We show that \cref{alg:mdmccfpt}
  outputs a solution of \mdmcc{}
  with the same profit.

  Since \(S\)~contains exactly one
  facility of each color in~\(\{1,\dots,\ell\}\)
  by \cref{prob:mdmcc}\eqref{mdmcc:colored-fac}
  and exactly one client
  of each color in~\(\{\ell+1,\dots,\ell+k\}\)
  by \eqref{mdmcc:colored-client},
  it is independent in the colorful matroid~\(M_P\)
  constructed in \cref{alg2:color-matroid}.
  Moreover, by \eqref{mdmcc:independent},
  \(C\)~is independent in all matroids in~\(\mathcal C\)
  and trivially in~\((U_C,2^{U_C})\).
  Similarly, \(A\)~is independent in all matroids
  in~\(\mathcal A\) and~\((U_A,2^{U_A})\).
  Thus,
  by \cref{def:matunion} about matroid unions,
  \(A\uplus C\)~is independent in
  all matroids in the set~\(\mathcal M\)
  constructed in \cref{alg2:mat-ext}.
  Since \(|A\uplus C|=k+\ell\),
  it follows that each matroid in~\(\mathcal M\)
  has rank at least~\(k+\ell\)
  and \cref{alg2:smallrank} is passed.
  It follows that after \cref{alg2:truncation},
  all matroids in~\(\mathcal M\)
  have rank \emph{exactly} \(k+\ell\).

  Now,
  consider an arbitrary facility~\(u\in A\)
  and \(i:=\col(u)\).
  For the set~\(Z(u)\) in \eqref{mdmccgf}
  and the set~\(\cF(u)\) constructed in
  \cref{alg2:get-followers},
  one has \(C_u:=C\cap Z(u)\in\cF(u)\)
  and
  \[
    w_{u}(C_u)=\sum_{v\in C_u}p_{uv}.
  \]
  Moreover, one has
  \(|A\uplus C|=k+\ell\),
  \(|C_u|=|Z_i|\),
  and
  \[
    A\uplus C=A\uplus\biguplus_{w\in A}C_{w}=(A\uplus\smashoperator{\biguplus_{w\in A\setminus\{u\}}}C_{w})\uplus C_u.
  \]
  Since \(\cFs(u)\) is max intersection
  \((k+\ell-|Z_i|)\)-representative
  with respect to~\(w_{u}\),
  by \cref{def:qrep},
  there is \(C_u'\in\cFs(u)\) with
  \(w_{u}(C_u')\geq w_{u}(C_u)\)
  and such that
  \[
    A\uplus C'=(A\uplus\smashoperator{\biguplus_{w\in A\setminus\{u\}}}C_{w})\uplus C_u'
  \]
  is independent in all matroids of~\(\mathcal M\).
  
  
  
  
  
  
  Consequently,
  \(\{u\}\uplus C_u'\in\cFs\) in \cref{alg2:the-family}
  and
  \[
    A\uplus C''=\biguplus_{u\in A}(\{u\}\uplus C_u')
  \]
  is a feasible solution to the \spmc{} instance
  in \cref{alg2:ask-marx-for-help}.
  Thus,
  \cref{alg:mdmccfpt} in \cref{alg2:ask-marx-for-help}
  finds an optimal \spmc{} solution~\(S_1,\dots,S_\ell\in\cFs\)
  for the weights $w\colon \cFs\to\Z,X\mapsto w_u(X\setminus\{u\})-c_u$, where \(\{u\}=X\cap U_A\).
  It returns \(A^*\uplus C^*\) for
  \(A^*=U_A\cap(S_1\uplus\dots\uplus S_\ell)\)
  and
  \(C^*=U_C\cap(S_1\uplus\dots\uplus S_\ell)\)
  in \cref{alg2:retsol},
  which is a feasible solution for \mdmcc{} by
  \cref{lem:alg2-feasible}.
  Finally,
  since each such set~\(S_i\in\cFs\)
  consists of one facility~\(u\in U_A\)
  and \(|Z_{\col(u)}|\)~elements of~\(Z(u)\)
  with pairwise distinct colors,
  the profit of \(A^*\uplus C^*\)
  as a solution to \mdmcc{}
  given by \eqref{mdmccgf} is
  \begin{align*}
    \sum_{u\in A^*}(-c_u+\smashoperator{\sum_{v\in C^*\cap Z(u)}}p_{uv})&=
    \sum_{j=1}^\ell w(S_j)
    \geq \sum_{u\in A} w(\{u\}\uplus C_u')=\sum_{u\in A}(-c_u+w_u(C_u'))\\
    &\geq \sum_{u\in A}(-c_u+w_u(C_u))
    =    \sum_{u\in A}(-c_u+\sum_{v\in C_u}p_{uv}),
  \end{align*}
  which is exactly the profit of the optimal
  solution~$A\uplus C$.
\qed\end{proof}


  


\begin{lemma}
\label[lemma]{lemma:alg2-runtime}
Given representations of all matroids over the same field $\mathbb F$, where \fieldconst{the input size},
\cref{alg:mdmccfpt} can be executed in
$2^{O(\ell k (a+c))}\cdot\poly(x)$~time,
where $a$ is the number of facility matroids,
$c$ is the number of client matroids, $k+\ell$ is the number of colors, 
and $x$ is the input size.
\end{lemma}
\begin{proof}
  First,
  we compute
  a $((k+\ell) \times n)$-representation~\(B=(b_{ij})\)
  of the multicolored matroid~$M_P$ in
  \cref{alg2:color-matroid} of 
  \cref{alg:mdmccfpt} over~\(\mathbb F\)
  in $\bigO(nk)$~time:
  \(b_{ij}=1\) if
  element $j\in U$ has color~$i$, and
  \(b_{ij}=0\) otherwise.
	
	
  
  
  
  
  
  
  
  By \cref{lemma:matroid-set-ext},
  we can compute the set~$\mathcal M$
  of matroids and their representations over~\(\mathbb F\)
  in \cref{alg2:mat-ext}
  in time of a polynomial number
  of field operations over~$\F$.

  Due to \cref{alg2:smallrank},
  all matroids in~\(\mathcal M\) have rank at
  least~\(k+\ell\).
  In \cref{alg2:truncation},
  we use \cref{rem:same_field_trunc}
  to compute $(k+\ell)$-truncations
  of all matroids in~$\mathcal M$
  over a field extension~$\mathbb F' \supseteq\mathbb F$,
  
  in a polynomial number
  of field operations over~$\mathbb F$.
  Herein,
  \(\mathbb F'=\F_{p^{d'}}\)
  with
  $d'= (k+\ell)\cdot rd \in \poly(n+d)$ since $\ell\leq k \le n$
  and $r$~is the maximum rank of the input matroids.
	
	
        
        
	
	
  Let $m=|\mathcal M|=a+c+1$.
  Using \cref{lem:max-int-repr} with~\(\gamma=1\),
  \(\cH:=\{\{v\}\mid v \in \cF(u)\}\),
  and weight function~\(w_{u}\colon 2^U\to\N\)
  to implement \cref{alg2:get-followers},
  we can execute the
  for-loop starting at \cref{alg2:for-loop}
  in time of $2^{\bigO((k+\ell)\cdot m)} \cdot n^2$ 
  operations over $\F'$:
  since \(\cH\)~is a 1-family
  and,
  thus,
  the partition of any
  subset of~\(U\) into sets of~\(\cH\) is unique,
  the function~\(w_{u}\)
  is \dtex{}
  for \(w_{u}(\emptyset)=0\)
  and
  constant\hyp time computable
  generating function~\(\dg\colon \N\times \cH\to\N,(k,\{v\})\mapsto k+p_{uv}\)
  (cf.\ \cref{ex:ws}).

  In \cref{alg2:pad-followers},
  for each $u\in U_A$,
  it holds that $|\cFs[u]|\leq|\cFs(u)| \leq {{(k + \ell)m} \choose {km}}\leq 2^{(k+\ell)m}$
  by \cref{lem:max-int-repr}.
  
  
  
  Thus, in \cref{alg2:the-family},
  we have
  \(|\cFs|\leq n 2^{(k+\ell)m}\).
  Moreover,
  each set in~\(\cFs\) has size at most~\(k+1\).
  Therefore,
  by \cref{thm:solve-spmc},
  \cref{alg2:ask-marx-for-help}
  can be executed in time of
  \(2^{O(\ell (k+1) m)}\cdot n\cdot\poly(p,d')\)
  operations over~\(\mathbb F'\).

  
  
  
      
      
      
	
	
	
        
	
	
        
	
	
	
	
  
  
  
  
  
  


  Since we initially get the representations
  of the input matroids 
  over the field~$\mathbb F_{p^d}$
  with $p^d$ elements, we need
  at least $d \log p$ bits to encode
  an element of the field.
  Thus, $d \log p$ is less than
  the input size.
  Therefore, \(d\) and \(d'\) are polynomially
  bounded by the input size.
  Since
  each element of the field $\mathbb F_{p^{d'}}$ 
  can be encoded using $d' \log p$ bits,
  each field operation over~$\mathbb F'$ 
  (and therefore over~$\mathbb F$)
  can be executed in $\poly(d' \log p)$~time, 
  which is polynomial in the input size.
  Thus,
  \cref{alg:mdmccfpt}
  can be executed in
  $2^{O(\ell k (a+c))}\cdot\poly(x)$~time.
\qed\end{proof}

\noindent
\cref{lem:mdmccfpt}
now follows from
\cref{lemma:alg2-correct,lemma:alg2-runtime,lem:alg2-feasible}.
Finally,
\cref{thm:alg}\eqref{thm:alg2} follows
from \cref{lem:mdmccfpt,lem:turingred}.


\section{Hardness for non\hyp linear client matroids}
\label{sec:hardness}
\cref{thm:alg}\eqref{thm:alg2} showed that \mdmc{}
is fixed\hyp parameter tractable
parameterized by the number of matroids
and the minimum rank of the client matroids
when a representation of all matroids
is given.
We now show that \cref{thm:alg}\eqref{thm:alg2}
does not generalize to nonlinear matroids.
That is,
we prove \cref{thm:hard}.
To this end,
we exploit that the
\clique{} problem
is \Wone-hard parameterized by~\(k\)~\cite{CFK+15}:
\begin{problem}[\clique{}]\leavevmode
  \begin{compactdesc}
  \item[\normalfont\textit{Input:}]
	  A graph $G=(V,E)$ and integer $k \in \mathbb N$.
  \item[\normalfont\textit{Question:}]
	  Does \(G\)~contain a clique on $k$~vertices?
\end{compactdesc}
\end{problem}

\noindent
To transfer the \Wone-hardness of \textsc{Clique}
parameterized by~\(k\)
to \mdmc{} parameterized by the client matroid rank,
we reduce the problem
of finding a clique of size~\(k\)
to \mdmc{} with a client matroid of rank~\(2k\).


The reduction
is inspired
by the proof
that \textsc{Matroid Parity}
is not polynomial\hyp time solvable
in general, non\hyp linear matroids
\citep[Section~43.9]{Sch03}.


\begin{construction}
  \label[construction]{constr:hard}
  Let \((G,k)\) with~\(G=(V,E)\)~be an instance
  of \clique{}.
  We construct an instance
  of \mdmc{} as follows.
  
  
  
  
  For each vertex~$u \in V$,
  let \(D_u:=\{u',u''\}\) such that~\(D_u\cap V=\emptyset\),
  let $L := \{ D_u \mid u \in V  \}$,
  and $S := \bigcup_{ u \in V} D_u$.
  Our \mdmcs{} instance
  consists of the universe~$U = V \uplus S$,
  and, for all \(u,v\in U\),
  \begin{align}
    \label{eq:profit}
    c_u&=
         \begin{cases}
           1&\text{ if $u\in V$,}\\
           0&\text{ otherwise, and}
         \end{cases}
            &&&
               p_{uv}&=\begin{cases}
                 1, & \text{ if $u \in V$ and $v \in D_u$, and}\\
                 0, & \text{otherwise.}
               \end{cases}
  \end{align}
  We do not use a facility matroid.
  
  
  
  As client matroid, we use the known
  matroid~$(S,\I_C)$ \cite[Section 43.9]{Sch03} with
  \begin{align*}
    \I_C =\{ J \subseteq S \mid{}& |J| \leq 2k -1 \}\\
    {}\cup\{ J \subseteq S \mid{}& |J| = 2k \text{ and } J \text{ is not the union of any $k$~pairs in~$L$} \}\ \\
    {}\cup
    \Bigl\{ J \subseteq S \Bigm|{}&A\subseteq V,|A|=k, J=\smashoperator{\biguplus_{u\in A}}D_{u},\text{ and $G[A]$ is a clique}\Bigr\}.
  \end{align*}
  
  
\end{construction}


\begin{proof}[of \cref{thm:hard}]
  
  
  
  
  
  
  
  
  \cref{constr:hard}
  works in polynomial time
  and creates an \mdmc{} instance
  with unit costs and binary profits as
  claimed in \cref{thm:hard}.
  Moreover,
  the rank of the client matroid is~\(2k\).
  
  
  
  We now show that
  there is a clique
  of size~$k$
  in~$G=(V,E)$
  if and only if
  there is
  a solution to the created \mdmc{}
  instance with profit~\(k\).
  
  (\(\Rightarrow\))
  Let~$A\subseteq V$, \(|A|=k\),
  $G[A]$~be a clique,
  and $C:=\biguplus_{u\in A}D_{u}$.

  Since $|C| = 2k$, 
  
  it follows that $C \in \I_C$.
  Hence, \(A\uplus C\)~is a feasible solution to \mdmc{}.
  Since
  each~$u\in A$
  has \(c_u=1\)
  and
  each~$v\in C$ has \(p_{uv}=1\)
  for the \(u\in A\) with \(v\in D_u\),
  the profit of~\(A\uplus C\)
  given by \eqref{mdmcgf} is
  \[\sum_{v \in C} \max_{u \in A} p_{uv} - \sum_{u \in A} c_u = 2k - k = k.\]
  
  (\(\Leftarrow\)) Let~$A \uplus C$~be
  an inclusion\hyp minimal
  solution with profit at least~\(k\)
  to the created \mdmc{} instance.
  Since 
  each facility~\(u\in A\)
  has \(c_u=1\)
  and since \(p_{uv}=1\) if and only if~\(v\in D_u\cap C\),
  the profit of \(A\uplus C\) given by \eqref{mdmcgf} is
  \begin{align}
    - \sum_{u \in A} c_u+    \sum_{v \in C} \max_{u \in A} p_{uv}=-|A|+\sum_{u\in A}|D_u\cap C|\geq k.
    \label{firstbudget}
  \end{align}
  Hence,
  if there is an \(u\in A\)
  with \(|D_u\cap C|\leq 1\),
  then \((A\uplus C)\setminus (\{u\}\cup D_u)\)
  is a solution with at least the same profit,
  contradicting the minimality of~\(A\uplus C\).
  Thus, for each~\(u\in A\), we have \(D_u\subseteq C\).
  Moreover, \(|C|\leq 2k\)
  since \(C\in\I_C\) and
  the client matroid~\((S,\I_C)\) has rank~\(2k\).
  Combining this with \eqref{firstbudget}, we thus get
  \begin{align*}
    2k\geq\sum_{u\in A}|D_u\cap C|=2|A|\geq k+|A|,
  \end{align*}
  which means \(|A|=k\).
  Thus,


  $C = \biguplus_{u\in A}D_u$, \(|C|=2k\), \(C\in\I_C\),
  and we conclude that
  $G[A]$~is a clique of size~$k$.
\qed\end{proof}


\section{Conclusion}


We have seen fixed\hyp parameter
algorithms for \mdmc{}
parameterized by the minimum rank
of the client matroids
in case when
the facility matroid is arbitrary
and the client matroid is uniform,
or when all matroids are linear.
The problem becomes W[1]-hard
when the client matroid is \emph{not} linear,
even without facility matroids.
The complexity of \mdmc{}
thus seems to be determined
by the client matroids.
It would be interesting to settle
the complexity of \mdmc{}
with one \emph{arbitrary} facility matroid
parameterized by the rank
of a single linear client matroid.


We point out that both algorithms
in \cref{thm:alg} are easy to implement:
the construction of perfect
hash families using \cref{prop:perfhash}
can be replaced by coloring the universe
uniformly at random with~\(k+\ell\) colors \citep{AYZ95}
and the truncation
of matroids using \cref{rem:same_field_trunc},
involving large field extensions
and generation of irreducible polynomials,
can be replaced by a very simple
randomized algorithm 
that does not enlarge fields \citep[Proposition~3.7]{Mar09}.
Doing so,
when aiming for an error probability
of at most~\(\varepsilon\in(0,1)\),
the asymptotic running time of our algorithms
increases by a factor~\(\ln(1/\varepsilon)\).

\looseness=-1
For future research,
we point out that our algorithm
for \cref{thm:alg}\eqref{thm:alg1}
works in polynomial space,
whereas \cref{thm:alg}\eqref{thm:alg2}
requires exponential space
due to \cref{lem:max-int-repr,thm:solve-spmc}.
It is interesting whether this is avoidable.
Moreover,
given that approximation algorithms
are known for UFLP
without matroid constraints~\citep{AS99},
for the minimization variant of UFLP
with a single facility matroid~\citep{KKN+14,Swa16},
as well as for
other optimization problems
under matroid constraints \citep{CCPV11,FW12,LSV13},
it is canonical to study
approximation algorithms
for \mdmc{}.


\subsection*{Acknowledgments}

We thank F.\ V.\ Fomin and F.\ Panolan
for valuable input.
This study was initiated
at the 7th annual research retreat
of the Algorithmics and Computational Complexity group
of TU Berlin,
Darlingerode, Germany,
March 18th--23rd, 2018.

\looseness=-1
René van Bevern
was supported by Russian Foundation for Basic Research (RFBR)
grant 16-31-60007 mol\_a\_dk.
Oxana Yu.\ Tsidulko
was supported by RFBR
grant 18-31-00470 mol\_a.
Both 
were
jointly supported
by TU~Berlin and RFBR
grant~18-501-12031~NNIO\textunderscore a
while participating at the retreat,
and
by Russian Science Foundation grant~16-11-10041
while working on \cref{app:social}.


\bibliographystyle{splncs04nat}
\bibliography{mcmc}


  


  
  
  
  	
  
  	
  
  	
  
  	
  
  
  	
  
  
  	
  
  


\end{document}
{"config": "arxiv", "file": "1806.11527/mcmc.tex"}