Maximum-Profit Domination with Matroid
        Constraints: A Fixed-Parameter Algorithm
                     and Applications?

                                  René van Bevern1,2
        1
         Novosibirsk State University, Novosibirsk, Russian Federation, rvb@nsu.ru
    2
        Sobolev Institute of Mathematics of SB RAS, Novosibirsk, Russian Federation


Keywords: social network analysis, routing, facility location, matroid optimiza-
tion, parameterized complexity, NP-hard problem.

This lecture presents ongoing joint work with Oxana Yu. Tsidulko (Novosibirsk)
and Philipp Zschoche (Berlin) on fixed-parameter algorithms for the following
generalization of Set Cover and Dominating Set. It models various social network
analysis, routing, and facility location problems:
Problem (Max-Profit Domination with Matroid Constraint (MDMC)).
Input: A universe U , for each u, v ∈ U a profit puv ∈ N ∪ {0} from dominating u
   by v, a cost cv ∈ N ∪ {0, ∞} for using v as dominator, and a matroid (U, I).
Output: Two disjoint sets D ] C ⊆ U such that D ∈ I and that maximize
                                X               X
                                     max puv −      cv .
                                         v∈D
                                   u∈C            v∈D

Informally, we find sets C, D ⊆ U so as to maximize the profit from dominating
the elements in C by elements in D minus the cost for the dominators in D.
Example. We obtain the classical problem of covering a maximum number
of elements of an universe V using at most k sets of a collection C ⊆ 2V by
choosing U = V ∪ C, I = {C 0 ⊆ C : |C 0 | ≤ k}, and, for each u, v ∈ U ,
            (                             (
             0    if v ∈ C,                 1 if v ∈ C such that u ∈ v,
       cv =                      puv =
             ∞ if v ∈ V ,                   0 otherwise.
We prove the following theorem and present applications to social network
analysis, routing, and facility location problems.
Theorem. A maximum-profit solution to MDMC with |C| = k is computable in
2O(k) · poly(n) time, i. e. in poly-time for k ∈ O(log n), where n is the input size.
   Herein, the universe U , costs cv and profits puv for each u, v ∈ U are given
explicitly in the input, whereas the matroid (U, I) is given as an oracle that, in
constant time, answers whether a subset of U belongs to I.
?
    This research is supported by the Russian Foundation for Basic Research under
    grants 16-31-60007 mol a dk (René van Bevern) and 18-31-00470 mol a (Oxana Yu.
    Tsidulko), and by the Ministry of Science and Education of the Russian Federation
    under the 5-100 excellence programme.