key: cord-0044020-o8yf9l6j
authors: Chiarelli, Nina; Krnc, Matjaž; Milanič, Martin; Pferschy, Ulrich; Pivač, Nevena; Schauer, Joachim
title: Fair Packing of Independent Sets
date: 2020-04-30
journal: Combinatorial Algorithms
DOI: 10.1007/978-3-030-48966-3_12
sha: a0b527c1fa15a06f1a5a47c42993469ae313aae6
doc_id: 44020
cord_uid: o8yf9l6j

In this work we add a graph theoretical perspective to a classical problem of fairly allocating indivisible items to several agents. Agents have different profit valuations of items and we allow an incompatibility relation between pairs of items described in terms of a conflict graph. Hence, every feasible allocation of items to the agents corresponds to a partial coloring, that is, a collection of pairwise disjoint independent sets. The sum of profits of vertices/items assigned to one color/agent should be optimized in a maxi-min sense. We derive complexity and algorithmic results for this problem, which is a generalization of the classical Partition and Independent Set problems. In particular, we show that the problem is strongly NP-complete in the classes of bipartite graphs and their line graphs, and solvable in pseudo-polynomial time in the classes of cocomparability graphs and biconvex bipartite graphs.

Allocating resources to several agents in a satisfactory way is a classical problem in combinatorial optimization. In particular, interesting questions arise if agents have different valuations of resources or if additional constraints are imposed for a feasible allocation. In this work we study the fair allocation of n indivisible goods or items to a set of k agents. Each agent has its own additive utility function over the set of items. The goal is to assign every item to exactly one of the agents such that the minimal utility over all agents is as large as possible. Related problems of fair allocation are frequently studied in Computational Social Choice, see, e.g., [9] . In the area of Combinatorial Optimization a similar problem is wellknown as the Santa Claus problem (see [5] ), which can be also seen as weight partitioning as well as a scheduling problem.

In this paper we look at the problem from a graph theoretical perspective and add a major new aspect to the problem. We allow an incompatibility relation between pairs of items, meaning that incompatible items should not be allocated to the same agent. This can reflect the fact that items rule out their joint usage or simply the fact that certain items are identical (or from a similar type) and it does not make sense for one agent to receive more than one of these items. We will represent such a relation by a conflict graph where vertices correspond to items and edges express incompatibilities. Now, every feasible allocation to one agent must be an independent set in the conflict graph. This means that the overall solution can also be expressed as a partial k-coloring of the conflict graph G, but in addition every vertex/item has a profit value for every color/agent and the sum of profits of vertices/items assigned to one color/agent should be optimized in a maxi-min sense.

We believe that this problem combines aspects of independent sets, graph coloring, and weight partitioning in an interesting way, offering new perspectives to look at these classical combinatorial optimization problems.

Disjunctive constraints represented by conflict graphs were considered for a wide variety of combinatorial optimization problems. We just mention the knapsack problem [20, 21] , bin packing [18] , scheduling (e.g., [8, 13] ) and problems on graphs (e.g., [11] ).

For a formal definition of our problem we consider a set V of items with cardinality |V | = n and k profit functions p 1 , . . . , p k : V → Z + . The satisfaction level of an ordered k-partition (X 1 , . . . , X k ) of V (with respect to p 1 , . . . , p k ) is defined as the minimum of the resulting profits p j (X j ) := v∈Xj p j (v), where j ∈ {1, . . . , k}. The classical fair division problem can be stated as follows.

Fair k-Division of Indivisible Goods Input: A set V of n items, k profit functions p 1 , . . . , p k : V → Z + . Task: Compute an ordered k-partition of V with maximum satisfaction level.

For the special case, where all k profit functions are identical, i.e., p 1 = p 2 = . . . = p k , the problem can also be represented in a scheduling setting. There are k identical machines and n jobs, which have to be assigned to the machines by a k-partitioning. The goal is to maximize the minimal completion time (corresponding to the satisfaction level) over all k machines. It was pointed out in [12] that this problem is weakly NP-hard even for k = 2 machines. Indeed, it is easy to see that an algorithm deciding the above scheduling problem for two machines would also decide the classical Partition problem: given n integers a 1 , . . . , a n , can they be partitioned into two subsets with equal sums? For k ≥ 3, one can simply add jobs of length one half of the sum of weights in the instance of Partition. If k is not fixed, but part of the input, the same scheduling problem is strongly NP-hard as mentioned in [4] . In fact, an instance of the strongly NPcomplete 3-Partition problem with 3m elements and target bound B could be decided by any algorithm for the scheduling problem with n = 3m jobs, k = m machines and a desired minimal completion time equal to B. We conclude for later reference.

Fair k-Division of Indivisible Goods, even with k identical profit functions, is weakly NP-hard for any constant k ≥ 2 and strongly NP-hard for k being part of the input.

Note that the problem is still only weakly NP-hard for constant k even for arbitrary profit functions, since we can construct a pseudo-polynomial algorithm solving the problem with a k-dimensional dynamic programming array.

The first elaborate treatment of Fair k-Division of Indivisible Goods was given in [7] , where two approximation algorithms with bounded (but not constant) approximation ratio were given. They also mention that the problem cannot be approximated by a factor better than 1/2 (under P = NP). In [14] further approximation results were derived. In 2006 Bansal and Sviridenko [5] coined the term Santa Claus problem, which corresponds to the variant of the above problem when k is not fixed but part of the input. Since then a huge number of approximation results have appeared on this problem of allocating indivisible goods exploring different concepts of objective functions and various approximation measures.

A different specialization is assumed in the widely studied Restricted Max-Min Fair Allocation problem. This is a special case of Fair k-Division of Indivisible Goods where every item v i ∈ V has a fixed valuation p(v i ) and every kid either likes or ignores item v i , i.e., the profit function

A fairly recent overview of approximation results both for this restricted setting as well as for the general case of the Santa Claus problem can be found in [3] .

In this paper we study a generalization of Fair k-Division of Indivisible Goods, where a conflict graph G = (V, E) on the set V of items to be divided is introduced. An edge {i, j} ∈ E means that items i and j should not be assigned to the same subset of the partition. The conflict graph immediately gives rise to (partial) colorings of the graph which were studied by Berge [6] and de Werra [22] .

A partial k-coloring of a graph G is a sequence (X 1 , . . . , X k ) of pairwise disjoint independent sets in G.

Combining the profit structure with the notion of coloring we define for the k profit functions p 1 , . . . , p k : V → Z + and for each partial k-coloring c = (X 1 , . . . , X k ) a k-tuple (p 1 (X 1 ), . . . , p k (X k )), called the profit profile of c. The minimum profit of a profile, i.e., min k j=1 {p j (X j )}, is the satisfaction level of c. Now we can define the problem considered in this paper: In the hardness reductions of this paper we will frequently use the decision version of this problem: for a given q ∈ Z + , does there exists a partial k-coloring of G with satisfaction level at least q?

Note that an optimal partial k-coloring (X 1 , . . . , X k ) does not necessarily select all vertices from V . Furthermore, note also that for k = 1, the problem coincides with the weighted independent set problem. In particular, since the case of unit weights and k = 1 generalizes the independent set problem, we obtain the following result.

Thus, the addition of the conflict structure gives rise to a much more complicated problem, since Fair k-Division of Indivisible Goods (which arises naturally as a special case for an edgeless conflict graph G) is trivial for k = 1 and only weakly NP-hard for k ≥ 2 (see Observation 1). 

Division Under Conflicts problem. The arrow from a class G1 to a class G2 means that every graph in G1 is also in G2. Label 'PP' means that the problem is solvable in pseudo-polynomial time for each fixed k in the given class, label 'sNPc' means that the problem is strongly NP-complete for all fixed k ≥ 2. For all graph classes in the figure, the problem is solvable in strongly polynomial time for k = 1, as it coincides with the weighted independent set problem.

In this contribution we first introduce a general concept of extendable graph families and show that for every such graph class G in which Independent Set is NP-complete, the decision version of our Fair k-Division Under Conflicts is strongly NP-complete when the conflict graphs are in G (Sect. 2.1). By a similar reasoning we can also reach a strong inapproximability result for our problem. For bipartite conflict graphs as well as their line graphs Fair k-Division Under Conflicts can be shown to be strongly NP-hard (Sect. 2.2) although the corresponding Independent Set problem is polynomial-time solvable. On the other hand, for the relevant special case of biconvex bipartite graphs (cf. [16, 17] ), Fair k-Division Under Conflicts can be solved by a pseudo-polynomial time algorithm. This result is based on an insightful pseudo-polynomial algorithm for the problem on a cocomparability conflict graph (Sect. 3). See Fig. 1 for a summary of these results. Many proofs had to be omitted for lack of space. They can be found in the extended version of this paper posted on http://arxiv.org/abs/ 2003.11313.

Observation 2 shows that Fair k-Division Under Conflicts is strongly NPhard even for k = 1 for general graphs, while Observation 1 shows the weak NP-hardness of the problem for constant k ≥ 2 in the absence of conflicts. In what follows, we show that Fair k-Division Under Conflicts is strongly NP-hard also for all k ≥ 2, for various well-known graph classes.

We start with the following general property of graph classes. Let us call a class of graphs G sustainable if every graph in the class can be enlarged to a graph in the class by adding to it one vertex. More formally, G is sustainable if for every graph G ∈ G there exists a graph G ∈ G and a vertex v ∈ V (G ) such that G − v = G. Clearly, any class of graphs closed under adding isolated vertices, or under adding universal vertices is sustainable. This property is shared by many well known graph classes, including planar graphs, bipartite graphs, chordal graphs, perfect graphs, etc. Furthermore, all graph classes defined by a single nontrivial forbidden induced subgraph are sustainable.

For an example of a non-sustainable graph class G closed under vertex deletion, consider the family of all cycles and their induced subgraphs. Then every cycle is in G but cannot be extended to a larger graph in G. The importance of sustainable graph classes for Fair k-Division Under Conflicts is evident from the following theorem.

Since the Independent Set problem is a special case of the Fair 1-Division Under Conflicts, Theorem 3 immediately implies the following.

Set is NP-complete. Then, for every k ≥ 1, the decision version of Fair k-Division Under Conflicts with conflict graphs from G is strongly NPcomplete.

It is known (see, e.g., [2] ) that for every graph H that has a component that is not a path or a subdivision of the claw, Independent Set is NP-complete on Hfree graphs. Thus, for every such graph H, Lemma 1 and Corollary 1 imply that for every k ≥ 1, Fair k-Division Under Conflicts (decision version) with H-free conflict graphs is strongly NP-complete. By using a similar argument, we even get a strong inapproximability result for general graphs.

Theorem 4. For every k ≥ 1 and every ε > 0, it is NP-hard to approximate Fair k-Division Under Conflicts within a factor of |V (G)| 1−ε , even for unit profit functions.

In this section we show that for all k ≥ 2, Fair k-Division Under Conflicts is NP-hard in two classes of graphs where the Independent Set problem is solvable in polynomial time: the class of bipartite graphs and the class of line graphs of bipartite graphs. Recall that for a given graph G, its line graph has a vertex for each edge of G, with two distinct vertices adjacent in the line graph if and only if the corresponding edges share an endpoint in G.

The proof for bipartite graphs shows strong NP-hardness even for the case when all the profit functions are equal.

Under Conflicts is strongly NP-complete in the class of bipartite graphs.

Proof. We use a reduction from the decision version of the Clique problem: Given a graph G and an integer , does G contain a clique of size ? Consider an instance (G, ) of Clique such that 2 ≤ < n := |V (G)|. We define an instance of Fair k-Division Under Conflicts (decision version) consisting of a bipartite conflict graph G , profit functions p 1 , . . . , p k , and a lower bound q on the required satisfaction level. The graph G = (A ∪ B, E ) has a vertex for each vertex of the graph G as well as for each edge of G and k new vertices x 1 , . . . , x k . It is defined as follows:

The lower bound q on the satisfaction level is defined by setting q = n 4 + 2 n + (n − ). For ease of notation we set N 1 = n 4 and we furthermore introduce a second integer N 2 such that q = N 2 + m − 2 n, where m = |E(G)|. (Note that N 2 ≥ n 3 .) With this, the profit functions p i : V (G ) → Z + , for all i ∈ {1, . . . , k}, are defined as

Note that all the profits introduced as well as the number of vertices and edges of G are polynomial in n. To complete the proof, we show that G has a clique of size if and only if G has a partial k-coloring with satisfaction level at least q. First assume that G has a clique C of size . We construct a partial k-coloring c = (X 1 , . . . , X k ) of G by setting

Observe that the partial k-coloring c gives rise to the corresponding profit profile with all entries equal to q, which establishes one of the two implications.

Suppose now that there exists a partial k-coloring c = (X 1 , . . . , X k ) of G for which the profit profile has all entries ≥ q. Since for each i ∈ {1, . . . , k}, the total profit of the set V (G) ∪ E(G) is only mn + n < n 4 , the partial coloring c must use exactly one of the k vertices x 1 , . . . , x k in each color class. We may assume without loss of generality that x i ∈ X i for all i ∈ {1, . . . , k}. Let U be the set of uncolored vertices in G w.r.t. the partial coloring c. Since for each of the profit functions p i , the difference between the overall sum of the profits of vertices of G and k · q is equal to , we clearly have v∈U p i (v) ≤ < n, which implies that U ⊆ V (G). Next, observe that every vertex of E(G) belongs to either X 1 or to X 2 , since otherwise we would have p 1 (X 1 ) + p 2 (X 2 ) < 2q, contrary to the assumption that the satisfaction level of c is at least q.

Consider the sets W = X 1 ∩ V (G) and F = X 1 ∩ E(G). Then X 1 = {x 1 } ∪ W ∪ F and, since v∈X1 p 1 (v) ≥ q = N 1 + 2 n + (n − ), it follows that X 1 contains exactly 2 vertices from E(G) (if |F | > 2 , then p 2 (X 2 ) < q) and at least n − vertices from V (G). Let C denote the set of all vertices of G with a neighbor in F . By the construction of G and since |F | = 2 , it follows that C is of cardinality at least . Furthermore, since X 1 is independent, we have C ∩ W = ∅. Consequently, n = |V (G)| ≥ |C| + |W | ≥ + (n − ) = n, hence equalities must hold throughout. In particular, C is a clique of size in G.

The proof is based on a reduction from the following problem, shown to be NP-complete by Pálvölgi (see [19] ): Given a bipartite graph G and an integer q, does G contain a perfect matching and a disjoint matching of size q?

As shown in Theorem 5, for each k ≥ 2, Fair k-Division Under Conflicts is strongly NP-complete in the class of bipartite graphs. This rules out the existence of a pseudo-polynomial time algorithm for the problem in the class of bipartite graphs, unless P = NP. In this section we show that for every k there is a pseudopolynomial time algorithm for the Fair k-Division Under Conflicts in a subclass of bipartite graphs, the class of biconvex bipartite graphs. The algorithm reduces the problem to the class of bipartite permutation graphs. To solve the problem in the class of bipartite permutation graphs, we develop a solution in a more general class of graphs, the class of cocomparability graphs. A graph G = (V, E) is a comparability graph if it has a transitive orientation, that is, if each of the edges {u, v} of G can be replaced by exactly one of the ordered pairs (u, v) and (v, u) so that the resulting set A of directed edges is transitive (that is, for every three vertices x, y, z ∈ V , if (x, y) ∈ A and (y, z) ∈ A, then (x, z) ∈ A). A graph G is a cocomparability graph if its complement is a comparability graph. Comparability graphs and cocomparability graphs are well-known subclasses of perfect graphs. The class of cocomparability graphs is a common generalization of the classes of interval graphs, permutation graphs, and trapezoid graphs (see, e.g., [10, 15] ). Since every bipartite graph is a comparability graph, Theorem 5 implies that for each k ≥ 2, Fair k-Division Under Conflicts is strongly NP-complete in the class of comparability graphs. For cocomparability graphs, we prove that the problem is solvable in pseudo-polynomial time. The key result in this direction is the following lemma, which will also be used in our proof of Theorem 8. The proof is based on a directed acyclic graph representing a transitive orientation of the complement of G.

Lemma 2 implies the following.

For every k ≥ 1, Fair k-Division Under Conflicts is solvable in time O(n k+2 (Q + 1) k ) for cocomparability conflict graphs G, where Q = max 1≤j≤k p j (V (G)).

Recall from Theorem 5 that Fair k-Division Under Conflicts is strongly NP-hard for bipartite conflict graphs. Thus, we consider in the following the more restricted case of biconvex bipartite conflict graphs. Recall that a bipartite graph G = (A ∪ B, E) is biconvex if it has a biconvex ordering, that is, an ordering of A and B such that for every vertex a ∈ A (resp. b ∈ B) the neighborhood N (a) (resp. N (b)) is a consecutive interval in the ordering of B (resp. ordering of A).

It is known that a connected biconvex bipartite graph G can always be ordered in such a way that the first and last vertices on one side have a special structure . Fix a biconvex ordering of G, say A = (a 1 , . . . , a s ) and  B = (b 1 , . . . , b t ) . Define a L (resp. a R ) as the vertex in N (b 1 ) (resp. N (b t )) whose neighborhood is not properly contained in any other neighborhood set (see [1, Def. 8] ). In case of ties, a L is the smallest such index (and a R the largest). We always assume that a L ≤ a R , otherwise the ordering in A could be mirrored. Under these assumptions, the neighborhoods of vertices appearing in the ordering before a L and after a R are nested. [1] ). Let G = (A ∪ B, E) be a connected biconvex graph. Then there exists a biconvex ordering of the vertices of G such that:

Property (iii) can be put in context with Theorem 7. Indeed, it is known that permutation graphs are a subclass of cocomparability graphs (see, e.g., [10] ). This gives rise to the following result that Fair k-Division Under Conflicts on biconvex graphs is indeed easier (from the complexity point of view) than on general bipartite graphs. It should be pointed out that the contribution of Theorem 8 is the identification of the complexity status of the problem, but not a practically relevant algorithm, since the pseudo-polynomial running time will be prohibitive in practice. The high-level idea of the algorithm is illustrated in Algorithm 1. Proof. Assuming at first that G is connected, Lemma 3 is applied for obtaining from G the cocomparability graph G . However, we have to consider also the vertex sets A L := {a 1 , . . . , a L−1 } and A R := {a R+1 , . . . , a s }. This is done by considering assignments of vertices in A L ∪ A R to the k subsets of a partial k-coloring of G in an efficient way as follows.

For every j ∈ {1, . . . , k}, we guess, by going through all possibilities, the largest index vertex a j ∈ A L (resp. smallest index a j ∈ A R ) inserted in X j . One can add an artificial vertex a 0 (resp. a s+1 ) to represent the case that no vertex from A L (resp. A R ) is inserted in X j . Thus, every guess is represented by a 2k-tuple σ = (a 1 , . . . , a k , a 1 , . . . , a k ) . The total number of such guesses (i.e., iterations) is bounded by (n + 1) k for each of A L and A R , i.e., O(n 2k ) selections to be considered in total.

For each such guess σ we perform the following computations. For every j ∈ {1, . . . , k} the vertices in the neighborhood N (a j ) ⊆ B (and N (a j ) ⊆ B) of the chosen index must be excluded from insertion into the corresponding set X j . This can be easily realized by setting to 0 the profits p j of all vertices in N (a j ) (resp. N (a j )). With these slight modifications of the profits we can apply Lemma 2 for the cocomparability graph G and the modified profit functions p σ j to obtain the set Π σ of all (pseudo-polynomially many) profit profiles (q 1 , . . . , q k ) of partial k-colorings of G with respect to p σ . Every entry q j of a profit profile in Π σ is increased by p j (a j ) + p j (a j ), to account for inclusion of the vertices selected by the guess σ.

In every guess there are the two vertices a j and a j permanently assigned to X j for every j and their neighborhoods N (a j ) and N (a j ) are excluded from X j . Now it follows from properties (i) and (ii) of Lemma 3 that for each vertex a ∈ A L with a < a j (resp. a ∈ A R with a > a j ) the neighborhood N (a ) is a subset of N (a j ) (resp. N (a j )). Thus, these vertices a could also be inserted in X j without any violation of the conflict structure. Therefore, we can start from the set Π σ of profit profiles computed for (G , p σ ) and consider iteratively (in arbitrary order) the addition of a vertex a ∈ A L to one of the color classes X j , as is usually done in dynamic programming. Each a is considered as an addition to every profit profile (q 1 , . . . , q k ) ∈ Π σ and for every index j with a < a j yielding new profit profiles (q 1 , . . . , q j−1 , q j + p j (a ), q j+1 , . . . , q k ) to be added to Π σ . An analogous procedure is performed for all vertices a ∈ A R where the addition is restricted to indices j with a > a j .

For every guess σ, the running time is dominated by the effort of computing the O((Q + 1) k ) profit profiles of (G , p σ ) according to Lemma 2, since adding any of the O(n) vertices a requires only k operations for each profit profile.

In this way, we construct the set Π σ of all profit profiles of partial k-colorings of G for each guess σ. It remains to identify the optimal solution in the set Π := σ Π σ similarly as in the proof of Theorem 7. Going over all O(n 2k ) guesses σ, the total running time can be given from Lemma 2 as O(n 3k+2 (Q + 1) k ).

In this paper we introduced the Fair k-Division Under Conflicts and studied it from a computational complexity point of view, with respect to various restrictions on the conflict graph. In particular, we could show that the problem is strongly NP-hard on general bipartite conflict graphs, but it can be solved in pseudo-polynomial time on biconvex bipartite graphs. The latter also contains the class of bipartite permutation graphs. There are other graph classes sandwiched between the two classes of our results, for which the complexity of Fair k-Division Under Conflicts is still open. In particular, we can derive open problems from the following sequence of inclusions: biconvex bipartite ⊆ convex bipartite ⊆ interval bigraph ⊆ chordal bipartite ⊆ bipartite. We believe that a result for convex bipartite graphs should be the next attempt. Outside this chain of inclusions, we pose the complexity of the problem for planar bipartite conflict graphs as another interesting open question.

Beside the results given in this work we can also derive pseudo-polynomial algorithms for Fair k-Division Under Conflicts if the conflict graph is chordal or if its treewidth or clique-width is bounded. These results will be described in a future publication.

Biconvex graphs: ordering and algorithms

The effect of local constraints on the complexity of determination of the graph independence number

Combinatorial algorithm for restricted max-min fair allocation

On-line machine covering

The Santa Claus problem

Minimax relations for the partial q-colorings of a graph

Allocating indivisible goods

On the complexity of scheduling incompatible jobs with unit-times

Fair allocation of indivisible goods

Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications

Paths, trees and matchings under disjunctive constraints

Scheduling to maximize the minimum processor finish time in a multiprocessor system

Scheduling with conflicts: online and offline algorithms

Max-min fair allocation of indivisible goods

Algorithmic Graph Theory and Perfect Graphs

PTAS for ordered instances of resource allocation problems

Restricted max-min fair allocations with inclusionfree intervals

Algorithms for the bin packing problem with conflicts

Partitioning to three matchings of given size is NP-complete for bipartite graphs

The knapsack problem with conflict graphs

Approximation of knapsack problems with conflict and forcing graphs

Packing independent sets and transversals

Acknowledgements. The work of this paper was done in the framework of a bilateral project between University of Graz and University of Primorska, financed by the OeAD