direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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. [1]

------ Links: ------

Zusatzinformationen / Extras