Research Group Algorithmics and Computational ComplexityTalk 14.07,2016

# Parameterized Complexity of Team Formation in Social Networks

Jiehua Chen (TU Berlin)

Given a set of required skills and a social network of individuals with different skills, the Team Formation problem asks to find a team of individuals that covers all the skills, while minimizing communication costs. Since the problem is NP-hard, we identify the source of intractability by analyzing its parameterized complexity with respect to parameters such as the total number~$k$ of skills, the team size~$\ell$, the communication cost budget~$b$, and the maximum vertex degree~$\Delta$.

We show that the computational complexity strongly depends on the communication cost measure: when using the weight of a minimum spanning tree of the subgraph induced by the selected team, we obtain fixed-parameter tractability with respect to the parameter~$k$. In contrast, when using the diameter as measure, the problem is parameterized intractable with respect to any single parameter; however, combining $\Delta$ with either $b$ or~$\ell$ yield fixed-parameter tractability.

Date
Speaker
Location
Language
14.07.2016
16:30 h
Jiehua Chen
TEL 512
English

Back to the research colloquium site.

# Navigation

## Direktzugang

Schnellnavigation zur Seite über Nummerneingabe