TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 14.07,2016


Page Content

to Navigation

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.


16:30 h
Jiehua Chen
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe