Group Activity Selection parameterized by the Number of Agent Types

Speaker(s)

Rahul CS

Affiliation

Instytut Informatyki, UW

Date

Jan. 25, 2018, 10:15 a.m.

Room

room 4790

Seminar

Seminar Games, Mechanisms, and Social Networks

---

We study the parameterized complexity of GASP (Group Activity Selection Problem) and its variant gGASP w.r.t. the number of different agent types as a parameter. We show that GASP can be solved in polynomial time if the number of agent types is a constant and complement this result with a strong parameterized hardness result, showing that GASP is unlikely to be fixed parameter tractable even when combining this parameter with the number of activities. In the case of gGASP we provide an even stronger hardness result showing that gGASP is unlikely to be fixed-parameter tractable parameterized by the number of agent types, the number of activities, and the vertex cover number of the network.

---