direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

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.

Zusatzinformationen / Extras