A Structural Approach to Activity Selection

1 Introduction

Imagine a host who is in charge of organizing an event for a larger number of people. At the beginning, the host might want to select which people to invite for his event. Later on, he or she might need to assign the attendees to groups: for instance, some participants might want to play a game of football while others would like to play poker, or later on the host may need to make table assignments for dinner. In all of these settings, the problem we are dealing with is to find an assignment of a certain set of agents to one or several activities subject to certain rationality and/or stability conditions given by the agents. This setting has motivated the introduction of two distinct NP-complete problems (see [Darmann and Lang, 2017] for a survey on group activity selection):

· In the STABLE INVITATIONS PROBLEM (SIP), we are given a set of agents, each of which has a list of friends, a list of enemies, and a set of natural numbers called the approval set. The task is to select a set of satisfied agents for a single activity, where an agent is satisfied if all of its friends are in the activity, none of its enemies are in the activity, and the size of the activity is in its approval set. The stability condition most frequently used here is based on Nash stability:

for each agent that is not selected, adding him to the activity would violate at least one of this agent's three criteria for being satisfied. SIP was introduced by Lee and Shoham (2015) and studied by Lee and Williams (2017a).

· In the GROUP ACTIVITY SELECTION PROBLEM (GASP), we are given a set of agents along with a set of activities, and for each agent we get a separate approval set for every activity. The task is to assign agents into activities so that each agent is satisfied, meaning that each agent is in an activity whose size is in the agent's approval set (for that activity). Several stability conditions have been defined and used for this problem, including Nash stability. GASP was introduced by Darmann et al. (2012; 2017b) and has been studied in various settings [Lee and Williams, 2017b; Darmann et al., 2017a; Darmann, 2015; Igarashi et al., 2017a; 2017c; Gupta et al., 2017].

This paper studies the problem underlying both SIP and GASP in its full generality. In particular, we introduce the COMPREHENSIVE ACTIVITY SELECTION PROBLEM (CAS), where we are given a set of agents along with their friends and enemies (as in SIP), a set of activities (as in GASP), and approval sets which specify the size constraints for each agent and activity. The stability conditions for CAS can be translated directly from GASP and SIP; as in previous work, here we focus primarily on Nash stability and EF (envy-freeness). Hence our task in the COMPREHENSIVE ACTIVITY SELECTION PROBLEM is to assign agents to activities so that each agent is satisfied in that activity (its friends are there, its enemies are missing, and it approves of its size), and agents that are not assigned to any activity have a reason not to want to join any activity (meaning a friend is missing there, an enemy is there, or the size would not be satisfactory). The advantage of CAS is that it allows us to capture more complex real-life situations than either of SIP or GASP on their own; aside from the aforementioned example of event organization, numerous applications come to mind in the context of social networks where information about friends (and sometimes also enemies) are readily available.

While both SIP and GASP are NP-hard, it is easy to see that the problems become polynomial-time tractable when one is only interested in assigning at most a constant number c out of n agents (c is then called the solution size). However, the running time of a naive algorithm would be roughly O(nc ), which is far from practical. Recent works [Lee and Williams, 2017a; 2017b; Igarashi et al., 2017a; Gupta et al., 2017] employed the parameterized complexity paradigm [Downey and Fellows, 2013; Cygan et al., 2015] to obtain a more refined complexity analysis of the problem in the case of selecting only few agents. In parameterized complexity, one considers inputs which are associated with a numerical parameter k, and the central question is whether the (parameterized) problem can be solved in time f(k)·nO(1) ; algorithms with this running time are called fixed-parameter algorithms, and parameterized problems that admit such algorithms are called fixed parameter tractable (FPT). For instance, Lee and Williams (2017a; 2017b showed that neither GASP nor SIP are FPT when parameterized by solution size (however, they do become FPT under additional assumptions on the input); for GASP, parameters such as number of agents and number of activities have also been considered [Igarashi et al., 2017a; Gupta et al., 2017].

Contribution. In line with previous work on GASP and SIP, we also study CAS through the lens of parameterized complexity, but with a twist. Instead of focusing on solution size, we turn our attention to the development of algorithms which exploit the structure of agent interactions captured in terms of an association graph, which provides a concise representation of agent interactions in terms of friend and enemy relations. This approach has two main advantages: it circumvents the strong lower bounds obtained by Lee and Williams (2017a; 2017b) when parameterizing by solution size, and leads to algorithms which can perform well even for instances with large solution sizes. Previously, structural parameters have only been considered for a variant of GASP with connectivity constraints [Igarashi et al., 2017c; 2017a; Gupta et al., 2017].

We set the stage by identifying the limits of how far graph structure can take us for a problem as complex as CAS. Since GASP is NP-hard, it is obvious that CAS will in general remain NP-hard even on edgeless association graphs; in other words, there is little hope of solving CAS when the number of activities is unbounded. Hence we restrict our attention to three restrictions of the problem:

• the (base) case where the number of activities is a fixed constant c (denoted c-CAS),
• the (more general) case where the number of activities is upper-bounded by the parameter (denoted CAS∗ ),
• the casewhere the number of activities is upper-bounded by the parameter but additional restrictions are placed on the approval sets (denoted SIMPLE-CAS∗ ).

In particular, the restrictions in SIMPLE-CAS∗ require that approval sets must be continuous and that there are only few types of agents (see Section 3 for an exact definition); we note that both of these restrictions were introduced and motivated already in the original paper by Darmann et al. (2012). As a warmup, we show that c-CAS admits a simple polynomialtime algorithm on edgeless association graphs. Somewhat surprisingly, we then show that CAS∗ is W[1]-hard even on edgeless association graphs, meaning that it is not FPT under well-established complexity assumptions. Note that this hardness result is not covered by [Igarashi et al., 2017b, Theorem 2], since there hardness is shown for a more expressive version of GASP and specifically the constructed instance uses this additional expressive power. On the other hand, the more restricted setting of SIMPLE-CAS∗ allows us to obtain a fixed-parameter algorithm on edgeless association graphs.

Having dealt with the base case of edgeless graphs, we proceed to the graph parameter treewidth [Robertson and Seymour, 1984]. Treewidth is, by far, the most prominent structural parameter and has been extensively used in many diverse areas of computer science [Bodlaender, 2008; Samer and Szeider, 2010; Ganian et al., 2017; Eiben et al., 2016]. Here we obtain a fixed-parameter algorithm for cCAS parameterized by the treewidth of the association graph. As for CAS∗ , the aforementioned lower bound on edgeless graphs rules out the fixed-parameter tractability of the problem parameterized by treewidth. However, we show that (unlike the case of edgeless association graphs), SIMPLE-CAS∗ becomes W[1]-hard parameterized by treewidth.

The results obtained so far beg the following question: can one lift the fixed-parameter tractability of SIMPLE-CAS∗ from edgeless graphs to graphs exhibiting a more restrictive form of structure than treewidth? We answer this affirmatively, in particular by parameterizing by vertex cover number (vcn). The vertex cover number (i.e., the size of a minimum vertex cover) has been successfully used to obtain a number of fixed-parameter algorithms for notoriously difficult problems [Lampis, 2012; Fellows et al., 2008]. Our results are summarized in Table 1.

Our final result revisits the setting of Lee and Williams (2017a) and provides a spark of hope after the strong negative results obtained for SIP. In particular, it was shown by these authors that SIP is W[1]-hard parameterized by solution size even if each agent has at most 1 friend and 1 enemy. Interestingly, the class of association graphs of such instances can still be "dense" in the sense of being somewhere dense [Neˇsetˇril and de Mendez, 2012]; for example, one can easily obtain an association graph that is a subdivision of a clique. On the other hand, while we do expect realistic instances to include agents with more than one friend and/or enemy, many real-world networks were shown to be nowhere dense and in particular exhibit bounded expansion [Reidl, 2016; Demaine et al., 2014]. We prove that CAS∗ (a generalization of SIP) is FPT parameterized by solution size when the association graphs are nowhere dense.

2 Preliminaries

For an integer i, we let [i] = {1, 2, . . . , i}. We refer to the handbook by Diestel (2012) for standard graph terminology. We also refer to the standard textbooks [Downey and Fellows, 2013; Cygan et al., 2015] for basic notions in parameterized complexity, such as: fixed-parameter algorithms, XP algorithms, treewidth, nice tree-decompositions and the complexity classes FPT, XP, W[1]. The vertex cover number of a graph G is the minimum size of a vertex cover in G.

The Comprehensive Activity Selection Problem (CAS). In CAS, we are given: a set of agents V = {v1, . . . , vn}, a set of activities A = {a1, . . . , ap}, and for each agent vi ∈ V , a portfolio Γi = (Fi, Ei, Si) where Fi ⊆ V is the friend set, Ei ⊆ V is the enemy set and Si ⊆ A×[n] is the approval set. We let P = {Γi | i ∈ [n] } denote the set of all portfolios.

For i ∈ [n], j ∈ [p] we use Si(aj) to denote the set of all admissible sizes of activity aj for agent vi, i.e., ℓ ∈ Si(aj) if and only if (aj, ℓ) ∈ Si. An assignment τ (also called outcome in the literature) is a mapping from V to A∗ = A ∪ {a0}, where a0 is the "void activity" (i.e., agents assigned to a0 are interpreted as not participating in any of the activities in A). For brevity, for an assignment τ we will denote the set of agents assigned by τ to activity aj simply as τ -1 (aj).

An assignment is individually rational (IR) if each agent is willing to participate; formally, τ is IR iff ∀i ∈ [n] with a = τ(vi) and a ∈ A it holds that Fi ⊆ τ -1 (a), Ei ∩ τ -1 (a) = ∅, and |τ -1 (a)| ∈ Si(a). We note that the empty assignment is always IR, because no friends and enemy conditions are required for agents assigned to a0. An assignment τ is (Nash) stable if it is IR and furthermore no agent assigned to a0 would be willing to join an activity; formally, ∀i such that τ(vi) = a0 and ∀j ∈ [p], at least one of the following must be true: Fi ̸⊆ τ -1 (aj), Ei∩τ -1 (aj) ̸= ∅, or |τ -1 (aj)|+1 ̸∈ Si(aj). An assignment τ is envy-free (EF) if it is IR and furthermore no agent assigned to a0 would be willing to join an activity instead of another agent; the formal definition is nearly identical to that of stability, with a slight modification to the third condition.

Finally, an assignment is stable-EF if it is stable and envyfree. We note that our algorithms will be able to solve CAS regardless of which of the above stability conditions are desired, and so we will assume that each CAS instance also includes a specification of which stability conditions are required (i.e., a value ι ⊆ {stable, EF}). A solution to a CAS instance (V, A, P, ι) is an assignment which satisfies ι.

Given a CAS instance I, we will use GI to denote the association graph of I, which provides a concise representation of agent interactions in terms of friend and enemy relations. The vertex set of GI is the set V of agents in I, and two agents vi, vj are connected by an edge if vi ∈ Ej ∪ Fj or vj ∈ Ei ∪Fi (or both).

Let us now briefly compare CAS to the previously studied GROUP ACTIVITY SELECTION PROBLEM (GASP) [Lee and Williams, 2017b] and STABLE INVITATIONS PROBLEM (SIP) [Lee and Williams, 2017a]. In particular, SIP is the restriction of CAS to the case where |A| = 1, and GASP is the restriction of CAS to the case where ∀vi ∈ V : Fi = Ei = ∅. This implies that, on their own, neither restrictions on the structure of the association graph nor restricting the number of activities can lead to efficient algorithms for CAS. Our focus lies on showing that a suitable combination of both types of restrictions does, however, allow us to obtain efficient solutions for the problem. We now formally define c-CAS.

c-CAS

Input: V = {v1, . . . , vn}, A = {a1, . . . , ac}, P = {Γ1, . . . , Γn}, ι ⊆ {stable, EF}. Task: Find an assignment that satisfies ι.

CAS∗ is defined similarly as c-CAS; the only difference is that instead of the number of activities being a fixed constant c, instead it is a parameter p. The third variant of interest, SIMPLE-CAS∗ , will be introduced in the next section.

3 The Base Case: no Friends, no Enemies

This section sets the stage for our later results by showing exactly how far graph structure can take us for c-CAS and CAS∗ ; in particular, we will focus on the case where the association graph is edgeless. We note that this problem precisely corresponds to GASP viewed through the lens of the number of activities, and each new result obtained in this section can be equivalently stated as a new result for GASP. We begin by mentioning an already known result.

Fact 1 ([Darmann et al., 2012]). c-CAS can be solved in time (n+1)cnO(1) if the association graph is edgeless.

Next, we show that the above result cannot be improved to a fixed-parameter algorithm for CAS∗ ; we note that this was left open in the previous work of Lee and Williams (2017b).

Theorem 2. CAS∗ is W[1]-hard, even on instances with an edgeless association graph.

Sketch of Proof. We give a parameterized reduction from the MULTICOLORED CLIQUE problem (MCC), which is wellknown to be W[1]-complete: Given a k-partite graph G = (V,E) with V = {V1, . . . , Vk}, determine whether it contains a k-clique. We denote by Ei,j the set of edges of G with one endpoint in Vi and one endpoint in Vj. W.l.o.g. we assume that each Vi has size n and each Ei,j has size m.

We will first give a formal construction and then provide the underlying intuition. To simplify notation in our setting, we assume our CAS∗ instance is given by a set N of agents, a set A of activities, and for every n ∈ N an approval set Sn ⊆ A × N. Given an instance of MCC, we construct an instance I = (N,A, (Sn)n∈N) of GASP as follows. The set A contains the following activities: One activity a, for every i with 1 ≤ i ≤ k three activities ai, a′i , and ci, and for every i and j with 1 ≤ i < j ≤ k the activity ai,j .

For every i and j with 1 ≤ i < j ≤ k let αi be a bijection from Vi to the set {1, 3, . . . , 2n - 1} and similarly let αi,j be a bijection from Ei,j to the set {1, 3, . . . , 2m- 1}. We are now ready to define the set N of agents. Apart from an agent v with approval set Sv = {(a, 1), (a, 3)}, we have the following agents for every i with 1 ≤ i ≤ k and every v ∈ Vi:

• one agent f v i whose approval set is given as the union of the sets {(ai, αi(v′ )) | v′ ∈ Vi ∧ αi(v′ ) ≥ αi(v)}, { (ai,j, αi,j(e) + 1) | j > i ∧ e ∈ Ei,j ∧ v ∈ e}, and { (aj,i, αj,i(e) + 1) | j < i ∧ e ∈ Ej,i ∧ v ∈ e }.
• one agent ¯ f v i whose approval set is given as the union of the sets { (ai, αi(v′ )) | v′ ∈ Vi ∧ αi(v′ ) > αi(v) }, {(ci, n + 1)}, and {(a, 2)}.

• one agent rv i whose approval set is given as the union of the sets {(a′i , αi(v′ ) | v′ ∈ Vi ∧ αi(v′ ) ≥ 2n - 1 - αi(v)+1 } { (ai,j, αi,j(e)+1) | j > i ∧e ∈ Ei,j ∧v ∈ e }, and { (aj,i, αj,i(e) + 1) | j < i ∧ e ∈ Ej,i ∧ v ∈ e }.
• one agent ¯ rv i whose approval set is given as the union of the sets {(a′i , αi(v′ ) | v′ ∈ Vi ∧ αi(v′ ) > 2n - 1 - αi(v) + 1 } {(ci, n + 1)}, and {(a, 2)}.
• for every i and j with 1 ≤ i < j ≤ k, a set Ni,j of 2m - 1 agents with approval sets {(ai,j , 1), (ai,j , 3), . . . , (ai,j , max{2m - 1, 4n + 1})}.

For i and v with 1 ≤ i ≤ k and v ∈ Vi, we denote by Ff (i), Fh(i), F(i), Rr(i), Rh(i), R(i), F(i, v), and R(i, v) the sets of agents {f w i | w ∈ Vi }, { ¯ f w i | w ∈ Vi }, Ff(i) ∪ Fh(i), { rw i | w ∈ Vi }, { ¯ rw i | w ∈ Vi }, Rr(i)∪Rh(i), { f w i , ¯ f w i | w ∈ Vi ∧αi(w) < αi(v) }∪{f v i }, and { rw i , ¯ rw i | w ∈ Vi∧αi(w) > αi(v) }∪{rv i }, respectively. See Figure 1 for an illustration of F(i, v) and R(i, v).

This completes the construction of the instance I, and we conclude the proof sketch by outlining the main idea behind the reduction. First, using the approval set of the agents in Ni,j it is ensured that the size of the activity ai,j in any stable assignment π for I indicates the edge from Ei,j that is chosen to be in the k-clique. More precisely, a size of s = |π-1 (ai,j)| for activity ai,j corresponds to the edge α-1 (s). Moreover, for every i the approval sets for the agents in F(i)∪R(i) ensure that there is an v ∈ Vi (with v corresponding to the vertex in Vi in the k-clique) such that all agents in F(i, v) are assigned to activity ai, all agents in R(i, v) are assigned to activity a′i , and all agents in Fh(i) ∪ Rh(i) that have not yet been assigned are in activity ci (see Figure 1 for an illustration of such an assignment).

Observe that the above hardness result strongly relies on the fact that the approval set Si of an agent vi can be arbitrarily complex. However, we may often encounter situations where we only have limited information about our agents: for instance, their approval sets could be obtained through a questionnaire, and it is unlikely that people will fill in irregular sets of numbers with gaps for individual activities. Alternatively, in the context of social networks, approval sets could be obtained automatically based on certain limited information we have about users. To model these more realistic settings with better fidelity, we will consider a version of CAS∗ where there are additional restrictions on the approval sets of agents: agents can only choose from a limited number of approval sets, and the approval sets consist of a consecutive set of integers for each activity. Both of these restrictions have already been considered in the classical setting by Darmann et al. (2012). We formalize below.

SIMPLE-CAS∗

Parameter: p+ q

Promise: There exist at most q approval sets which are pairwise distinct, and for each approval set Si and each activity aj the set Si(aj) must be consecutive.

Task: Find an assignment that satisfies ι.

We note that GASP is known to be NP-hard even if all approval sets are consecutive [Darmann et al., 2012]. In any instance of SIMPLE-CAS∗ , agents can be partitioned into at most q agent-types Q1, . . . ,Qq, where agents vi, vj belong to the same agent-type iff Si = Sj. Let Q be the set of all agent-types and SQ i be the approval set of the agents in Qi.

Our last goal for this section will be to show that, unlike CAS∗ , SIMPLE-CAS∗ is in fact FPT on edgeless graphs. In order to do so, we will first introduce and solve an auxiliary problem, which we call RESTRICTED TOKEN ASSIGNMENT. Our algorithm for SIMPLE-CAS∗ will later rely on making calls to a subroutine solving this problem.

RESTRICTED TOKEN ASSIGNMENT

Input: A set V = {v1, . . . , vn} of tokens, a set A = {a0, . . . , am} of bins, and a specification β where β(aj) is an interval and β(vi) is a subset of A.

Task: Find an assignment τ from V to A s.t. (T1) for each vi ∈ V , τ(vi) ∈ β(vi), and (T2) for each aj ∈ A, |τ -1 (aj)| ∈ β(aj).

Lemma 3. RESTRICTED TOKEN ASSIGNMENT can be solved in time O((n+m)4 · log(n+m)).

Sketch of Proof. The problem can be reduced to the CIRCULATION problem, a generalization of NETWORK FLOW; the run-time follows from the result of Orlin (1988).

Theorem4. SIMPLE-CAS∗ can be solved in time 2O(q(p+1)) · n4 log n if the association graph is edgeless.

Sketch of Proof. We begin by exhaustively branching over all possibilities of which agent-types are compatible with which activities based on their size. Formally, let the compatibility set Ci of activity ai be an element of 2Q, and let us branch over the at most (2q )p+1 possible compatibility sets for each activity in A∗ . For the following, let us fix one particular choice of compatibility sets C0, C1, . . . , Cp. We interpret our compatibility sets as the following assumptions:

• for i > 0, activity ai has compatibility set Ci ̸= ∅ means that only agents from Ci can participate in activity ai (i.e., the size of ai lies in the approval set of Ci);

• for activity a0, C0 contains all agent-types which will contain at least one agent that is assigned to a0 (this is important due to the stability conditions).

Next, we will check that the chosen compatibility sets are valid: for each activity ai ∈ A such that Ci ̸= ∅, we compute a pre-restriction α′i = ⋂Qj∈Ci SQ j (ai). Observe that α′i contains all sizes of ai which are consistent with our assumption that all agents from Ci could participate in ai. Our third task is to ensure that the stability conditions are not violated. Depending on ι, we will prune each α′i so as to not invalidate our stability criteria in ι (this has to be done for each agent-type in C0). If Ci ̸= ∅ but α′i = ∅ then this means we have made an invalid assumption and we terminate our current branch. Observe that at this stage, α′i may consist of up to q + 1 consecutive segments. So, we apply a second round of branching: for each α′i , we branch over its at most q + 1 consecutive segments and denote the chosen segment αi. Let us consider a specific branch η, corresponding to a choice of compatibility sets and consecutive segments α1, . . . , αp.

Finally, for each branch η, we construct an instance Iη of RESTRICTED TOKEN ASSIGNMENT as follows. The set of bins in Iη is the set of activities including a0. For each agent-type Qj ∈ Q such that Qj ̸∈ C0, we proceed as follows: for each v ∈ Qj we create a token v′ and we set β(v′ ) = {ai | Qj ∈ Ci }. On the other hand, for each agenttype Qj ∈ C0 we arbitrarily choose one agent v0 ∈ Qj, for each agent v ∈ Qj \ {v0} we create a token v′ , and we set β(v′ ) = { ai | Qj ∈ Ci }. Finally, we set β(a0) = [0,∞] and for i > 0 we set β(ai) = αi (or, more precisely, the interval corresponding to consecutive segment αi). This completes the construction of Iη. The algorithm attempts to solve each instance Iη obtained in our branches using Lemma 3 and outputs YES iff at least one Iη is a YES-instance.

4 Algorithms and Bounds using Treewidth

Given the above baseline results, we now turn our attention to the more general setting of association graphs with low treewidth. We begin with a fixed-parameter algorithm.

Theorem 5. c-CAS can be solved in time n3c+1 · 2O(c·ℓ) if the association graph has treewidth at most ℓ.

Sketch of Proof. We begin by computing a nice treedecomposition (T, X) of the association graph G with width k ≤ 5ℓ + 4 using the known approximation algorithm [Bodlaender et al., 2016]. Next, we branch over all at most nc - many target sizes of the activities in A. In each branch, we denote the size of activity ai as ri, and our task will be to find an assignment of agents to activities such that each activity ai receives precisely ri agents. We now have complete information about the allowed activities for each agent.

As our third step, we solve c-CAS using a leaf-to-root dynamic programming procedure along T. In this procedure, for each node t ∈ V (T) we will compute all the possible ways the activities in Xt can be assigned together with all the possible sizes of the activities based on agents assigned up to this point in the leaf-to-root run. In addition, we will also keep information for each agent in Xt assigned to a0

specifying which activities are currently violating the stability conditions of this agent.

Corollary 6. CAS∗ admits an XP algorithm when additionally parameterized by the treewidth of the association graph.

Naturally, the biggest question left for treewidth at this point is whether one can retain the fixed parameter tractability of SIMPLE-CAS∗ while generalizing the graph structure to treewidth. Surprisingly, we show that this is not the case.

Theorem 7. SIMPLE-CAS∗ is W[1]-hard when additionally parameterized by the treewidth of the association graph.

Sketch of Proof. We give a parameterized reduction from the EQUITABLE COLORING problem: given a graph G with n vertices and an integer q such that n/q = r is an integer, partition the vertices of G into q independent sets of size precisely r. EQUITABLE COLORING is W[1]-hard when parameterized by the treewidth of G and q [Fellows et al., 2011].

The starting point of our reduction is an instance (G, q) of EQUITABLE COLORING. We construct an instance I of SIMPLE-CAS∗ as follows. The activity set of I consists of q "main" activities a1, . . . , aq and q "auxiliary" activities aq+1, . . . , a2q. For each vertex v ∈ V (G) of G, we add an agent v to I with no friends, enemies equal to its neighbors in G, and the approval set Sv = { (ai,m) | 1 ≤ i ≤ q, 1 ≤ m ≤ r + 1}. We then add 2q additional agents to I, denoted xq+1, . . . , x2q and yq+1, . . . , y2q, with no friends and no enemies such that the approval set for each xi is Sxi = {(ai, 1), (ai-q, r + 1)}, and the approval set for each yi is Syi = {(ai, 2)}. To conclude the construction of I, let ι = {stable}. Observe that tw(GI) = tw(G), and we note that I contains no friends. In the end, it suffices to show that (G, q) is a yes-instance if and only if I is a yes-instance.

5 Solving SIMPLE-CAS∗ using Vertex Covers

Here we give a fixed-parameter algorithm for SIMPLE-CAS∗ par. by the vertex cover number of the association graph.

Theorem 8. SIMPLE-CAS∗ can be solved in time at most qO(ℓ2 ·p·log p) · n4 log n, where ℓ is the vertex cover number of the association graph.

Sketch of Proof. Let I be the given instance of SIMPLECAS∗ . The general strategy is to apply two levels of branching and then reduce the resulting, simplified instance to RESTRICTED TOKEN ASSIGNMENT (cf. Lemma 3).

Our first step will aim at obtaining certain restrictions on the sizes of the activities, and in this sense its goal will be similar to that in Theorem 4. However, it will be more advantageous to use a slightly different approach here than in the aforementioned theorem: instead of beginning with the compatibility sets used in Theorem 4, here we will begin by directly branching on the intervals of sizes for individual activities, as follows. For each activity ai, we let U ′ i be the tuple containing the endpoints of the approval sets (intervals) for ai over all approval sets SQ 1 , SQ 2 , . . . , SQ q , in ascending order and without multiplicities. We will use U ′ i to define the set Ui of "relevant size intervals" for our activity i, as follows. Ui contains: (A) for each number z ∈ U ′ i , the single-element interval [z, z]; (B) for each number z ∈ U ′ i greater than 0, the single-element interval [z-1, z-1]; (C) all consecutive intervals of natural numbers surrounding the single-unit intervals added up to this point between 0 and n.

To illustrate the above definitions, consider the example where q = 3 and SQ 1 (ai) = [2, 10], SQ 2 (ai) = [6, 15] and SQ 3 (ai) = [15, 50]. Then U ′ i = (2, 6, 10, 15, 50). Subsequently, the set Ui would then contain the following intervals: [0], [1], [2], [3, 4], [5], [6], [7, 8], [9], [10], [11, 13], [14], [15], [16, 48], [49], [50], [51, n]. On an intuitive level, one may observe that (as far as approval sets are concerned) whether |τ (ai)| = 30 or |τ (ai)| = 40 would make no difference as far as which agent is allowed to go to activity ai or other activities. On the other hand, the case of |τ(a1)| = 9 may differ from the case of |τ(ai)| = 10 due to stability: in the former case an agent in Q1 assigned to a0 could violate stability due to preferring to be in ai, while in the latter case no agent in Q1 would prefer to be in ai.

To conclude the first step in our algorithm, we observe that for each i ∈ [p], |Ui| ≤ 4q + 2. We will exhaustively branch by choosing an interval βi from each of the sets Ui, resulting in a branching factor of at most (4q + 2)p . Next, we will exploit the structure of the vertex cover through a second level of branching: we exhaustively branch over all (p + 1)ℓ possibilities of which agents in X are assigned to which activity. The algorithm will check whether the chosen assignment of X is compatible with the selected intervals βi and also assign all agents whose assignments are already fixed by these choices (e.g., due to them having friends in X). Modulo some technicalities, this allows us to deal with all friend and enemy relations in the instance at the cost of certain additional simple constraints; at that point, it is possible to reduce the problem to RESTRICTED TOKEN ASSIGNMENT using a reduction which extends the one used in the proof of Theorem 4.

6 An Algorithm for CAS∗ on Sparse Graphs

The goal in our last section is to establish the fixed-parameter tractability of CAS∗ parameterized by solution size when restricted to instances whose association graphs belong to a fixed nowhere dense graph class. We note that the definition of nowhere dense graph classes [Neˇsetˇril and de Mendez, 2012] is rather technical; however, it is worth mentioning that nowhere dense graph classes include many well-known graph classes such as graphs of bounded degree and planar graphs. The main tool we will use to establish our result is the fact that model checking for first order logic is FPT when parameterized by the size of the formula on nowhere dense labeled graph classes [Grohe et al., 2017]. For clarity, we provide a full statement for the problem parameterized by solution size below, and note that SIP parameterized by solution size [Lee and Williams, 2017a] is the special case where |A| = 1.

S-CAS∗ Parameter: p+k Input: V = {v1, . . . , vn}, A = {a1, . . . , ap}, P = {Γ1, . . . , Γn}, ι ⊆ {stable, EF}. Task: Find an assignment that satisfies ι which assigns precisely n - k agents to a0.

Theorem 9. S-CAS∗ is in FPT when restricted to instances whose association graphs belong to a fixed nowhere dense graph class C.

Sketch of Proof. We begin by exhaustively branching over the at most kp possible mappings θ : A → [k] such that ∑a∈A θ(a) = k. Clearly, our S-CAS∗ instance I is a YESinstance if and only if there exists an assignment τ which satisfies ι and maps precisely θ(a) agents to each a ∈ A for some choice of θ. In the following we consider one fixed choice of θ and show how to determine the existence of τ .

Our next step is to perform a greedy preprocessing of all our agents in order to simplify our instance (w.r.t. our choice of θ). First of all, we loop over each agent vi ∈ V and check whether vi could violate the stability conditions given in ι due to the final size of an activity aj projected by θ; if this is the case, we mark vi as j-bad. If an assignment τ which respects θ assigns a bad agent vi to a0, then τ must either assign an enemy of vi to aj or not assign a friend of vi to aj. Second, for each vi, we loop over each aj ∈ A and we mark vi as j-compatible if θ(aj) ∈ Si(aj). Note that an IR assignment can only assign agents to activity aj if they are j-compatible.

Our final task is to verify the existence of an assignment τ which assigns precisely k agents to non-void activities while respecting the restrictions imposed by the friends and enemies and ensuring that all bad vertices do not violate ι and that only j-compatible agents are assigned to activity aj . All of these properties can be checked locally on the association graph (or, more precisely, a relational structure enriching the association graph to capture friend and enemy relations along with the properties of being bad and compatible), and in particular they can be expressed by a first-order formula. The proof then follows by the result of Grohe et al. (2017).

7 Concluding Remarks

We initiated the study of the COMPREHENSIVE ACTIVITY SELECTION PROBLEM (CAS), a natural generalization of GASP and SIP. We investigated the complexity of CAS with respect to structural restrictions on the instance, and used this perspective to obtain a number of new algorithms (which can also be used for GASP and SIP).

Our algorithmic results are motivated and complemented by the lower bounds presented in Theorem 2 and 7. We note that Theorem 2 settles the complexity of GASP parameterized by the number of activities, a question left open in previous work [Darmann et al., 2012]. In the base GASP setting, this still leaves open the complexity of the problem when parameterized by the number of agent types alone; we believe this is a natural and interesting open problem in the area.

Acknowledgments

Eduard Eiben was supported by Pareto-Optimal Parameterized Algorithms (ERC Starting Grant 715744). Robert Ganian is also affiliated with FI MU, Brno, Czech Republic.