This lecture presents ongoing joint work with Oxana Yu. Tsidulko (Novosibirsk) and Philipp Zschoche (Berlin) on xed-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-Pro t Domination with Matroid Constraint (MDMC)). Input: A universe U , for each u; v 2 U a pro t puv 2 N [ f0g from dominating u by v, a cost cv 2 N [ f0; 1g for using v as dominator, and a matroid (U; I). Output: Two disjoint sets D ] C U such that D 2 I and that maximize X max puv u2C v2D ? This research is supported by the Russian Foundation for Basic Research under grants 16-31-60007 mol a dk (Rene 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.
X cv: v2D Informally, we nd sets C; D U so as to maximize the pro t 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 = fC0 C : jC0j kg, and, for each u; v 2 U , cv = (0 if v 2 C; if v 2 V ; puv = (1 0 if v 2 C such that u 2 v, otherwise: We prove the following theorem and present applications to social network analysis, routing, and facility location problems.
Theorem. A maximum-pro t solution to MDMC with jCj = k is computable in 2O(k) poly(n) time, i. e. in poly-time for k 2 O(log n), where n is the input size.
Herein, the universe U , costs cv and pro ts puv for each u; v 2 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.