We study the problem of fair allocation of indivisible goods that form a graph and the bundles that are distributed to agents are connected subgraphs of this graph. We focus on the proportional and the maximin share fairness criteria. It is well-known that allocations satisfying these criteria may not exist for many graphs including complete graphs and cycles. Therefore, it is natural to look for approximate allocations, i.e., allocations guaranteeing each agent a certain portion of the value that is satisfactory to her. In this paper we consider the class of graphs of goods which do not contain a star with d+1 edges (where d > 1) as an induced subgraph. This is a large class of graphs containing graphs with the maximum degree bounded by d. For this class of graphs we show a theorem which specifies what fraction of the proportional share can be guaranteed to each of n agents if the values of single goods for the agents are bounded by a given fraction of this share. Furthermore, an allocation ensuring such a guarantee can be computed in polynomial time. This theorem can be viewed as analogous to a result by Hill in1987, who solved a similar problem for proportional allocations without connectivity constraints. Moreover, for the same class of graphs of goods, we prove that there is an allocation assigning each of n agents a connected bundle of value at least n/(d(n-1)+1) > 1/d of her maximin share, and this allocation can be computed in polynomial time.

We study the problem of fair division of a set of indivisible goods with connectivity constraints. Specifically, we assume that the goods are represented as vertices of a connected graph, and sets of goods allocated to the agents are connected subgraphs of this graph. We focus on the widely-studied maximin share criterion of fairness. It has been shown that an allocation satisfying this criterion may not exist even without connectivity constraints, i.e., if the graph of goods is complete. In view of this, it is natural to seek approximate allocations that guarantee each agent a connected bundle of goods with value at least a constant fraction of the maximin share value to the agent. It is known that for some classes of graphs, such as complete graphs, cycles, and d-claw-free graphs for any fixed d, such approximate allocations indeed exist. However, it is an open problem whether they exist for the class of all graphs. In this paper, we continue the systematic study of the existence of approximate allocations on restricted graph classes. In particular, we show that such allocations exist for several well-studied classes, including block graphs, cacti, complete multipartite graphs, and split graphs.

We study the problem of fair allocation of indivisible goods that form a graph and the bundles that are distributed to agents are connected subgraphs of this graph. We focus on the maximin share and the proportional fairness criteria. It is well-known that allocations satisfying these criteria may not exist for many graphs including complete graphs and cycles. Therefore, it is natural to look for approximate allocations, i.e., allocations guaranteeing each agent a certain portion of the value that is satisfactory to her. In this paper we consider the class of graphs of goods which do not contain a star with d+1 edges (where d > 1) as an induced subgraph. For this class of graphs we prove that there is an allocation assigning each agent a connected bundle of value at least 1/d of her maximin share. Moreover, for the same class of graphs of goods, we show a theorem which specifies what fraction of the proportional share can be guaranteed to each agent if the values of single goods for the agents are bounded by a given fraction of this share.

For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). In the H-Coloring problem the graph H is fixed and we ask whether an instance graph G admits an H-coloring. A generalization of this problem is H-ColoringExt, where some vertices of G are already mapped to vertices of H and we ask if this partial mapping can be extended to an H-coloring. We study the complexity of variants of H-Coloring in F-free graphs, i.e., graphs excluding a fixed graph F as an induced subgraph. For integers a,b,c ⩾ 1, by S_{a,b,c} we denote the graph obtained by identifying one endvertex of three paths on a+1, b+1, and c+1 vertices, respectively. For odd k ⩾ 5, by W_k we denote the graph obtained from the k-cycle by adding a universal vertex. As our main algorithmic result we show that W_5-ColoringExt is polynomial-time solvable in S_{2,1,1}-free graphs. This result exhibits an interesting non-monotonicity of H-ColoringExt with respect to taking induced subgraphs of H. Indeed, W_5 contains a triangle, and K_3-Coloring, i.e., classical 3-coloring, is NP-hard already in claw-free (i.e., S_{1,1,1}-free) graphs. Our algorithm is based on two main observations: 1) W_5-ColoringExt in S_{2,1,1}-free graphs can be in polynomial time reduced to a variant of the problem of finding an independent set intersecting all triangles, and 2) the latter problem can be solved in polynomial time in S_{2,1,1}-free graphs. We complement this algorithmic result with several negative ones. In particular, we show that W_5-Coloring is NP-hard in P_t-free graphs for some constant t and W_5-ColoringExt is NP-hard in S_{3,3,3}-free graphs of bounded degree. This is again uncommon, as usually problems that are NP-hard in S_{a,b,c}-free graphs for some constant a,b,c are already hard in claw-free graphs

The problem of fair division of indivisible goods is a fundamental problem of resource allocation in multi-agent systems, also studied extensively in social choice. Recently, the problem was generalized to the case when goods form a graph and the goal is to allocate goods to agents so that each agent’s bundle forms a connected subgraph. For the maximin share fairness criterion, researchers proved that if goods form a tree, an allocation offering each agent a bundle of at least her maximin share value always exists. Moreover, it can be found in polynomial time. In this paper we consider the problem of maximin share allocations of goods on a cycle. Despite the simplicity of the graph, the problem turns out to be significantly harder than its tree version. We present cases when maximin share allocations of goods on cycles exist and provide in this case results on allocations guaranteeing each agent a certain fraction of her maximin share. We also study algorithms for computing maximin share allocations of goods on cycles.

The problem of fair division of indivisible goods is a fundamental problem of social choice. Recently, the problem was extended to the setting when goods form a graph and the goal is to allocate goods to agents so that each agent's bundle forms a connected subgraph. Researchers proved that, unlike in the original problem (which corresponds to the case of the complete graph in the extended setting), in the case of the goods-graph being a tree, allocations offering each agent a bundle of or exceeding her maximin share value always exist. Moreover, they can be found in polynomial time. We consider here the problem of maximin share allocations of goods on a cycle. Despite the simplicity of the graph, the problem turns out be significantly harder than its tree version. We present cases when maximin share allocations of goods on cycles exist and provide results on allocations guaranteeing each agent a certain portion of her maximin share. We also study algorithms for computing maximin share allocations of goods on cycles.

In this note we present a corrected version of Lemma 4.9 and two corollaries implied by this lemma, from our paper [Bondy, Lonc, and Rzaͅżewski, SIAM J. Discrete Math., 30 (2016), pp. 452--464].

A $k$-radius sequence over an $n$-element alphabet $A$ is a sequence in which every two elements of $A$ appear within distance at most $k$ (where the distance is defined as the difference of indices). By a $k$-radius sequence over an $n$-element alphabet $A$ we mean a sequence in which every two elements of $A$ appear within distance at most $k$. The problem of constructing shortest possible $k$-radius sequences, motivated by some problems occurring in large data transfer, has been studied by several authors recently. In this paper we present an explicit construction of “short” $k$-radius sequences for some values of $k$ and $n$. This construction allows us to find 2-radius sequences of the shortest possible length for all but very special values of $n$. For all $n$ we construct 2-radius sequences whose length differs from the length of the shortest one only by a constant. Moreover, we construct shortest possible $k$-radius sequences when $n=2k^2+2k+1$ and $k$ is a power of a prime. Our construction depends on the existence of some other sequences that we call $k$-perfect and $k$-additive. We investigate these sequences as they seem to be interesting in themselves.

We propose and study algorithms to compute minimal models, stable models and answer sets of $t$ -CNF theories, and normal and disjunctive $t$ -programs. We are especially interested in algorithms with non-trivial worst-case performance bounds. The bulk of the paper is concerned with the classes of 2- and 3-CNF theories, and normal and disjunctive 2- and 3-programs, for which we obtain significantly stronger results than those implied by our general considerations. We show that one can find all minimal models of 2-CNF theories and all answer sets of disjunctive 2-programs in time $O(m1\mbox{.}4422\mbox{..}^n)$ . Our main results concern computing stable models of normal 3-programs, minimal models of 3-CNF theories and answer sets of disjunctive 3-programs. We design algorithms that run in time $O(m1\mbox{.}6701\mbox{..}^n)$ , in the case of the first problem, and in time $O(mn^2 2\mbox{.}2782\mbox{..}^n)$ , in the case of the latter two. All these bounds improve by exponential factors the best algorithms known previously. We also obtain closely related upper bounds on the number of minimal models, stable models and answer sets a $t$ -CNF theory, a normal $t$ -program or a disjunctive $t$ -program may have.

We study algorithms for computing stable models of logic programs and derive estimates on their worst-case performance that are asymptotically better than the trivial bound of $O(m 2^n)$ , where $m$ is the size of an input program and $n$ is the number of its atoms. For instance, for programs whose clauses consist of at most two literals (counting the head) we design an algorithm to compute stable models that works in time $O(m\times 1.44225^n)$ . We present similar results for several broader classes of programs. Finally, we study the applicability of the techniques developed in the paper to the analysis of the performance of smodels.

A decision problem is called parameterized if its input is a pair of strings. One of these strings is referred to as a parameter . The following problem is an example of a parameterized decision problem with k serving as a parameter: given a propositional logic program P and a nonnegative integer k , decide whether P has a stable model of size no more than k . Parameterized problems that are NP-complete often become solvable in polynomial time if the parameter is fixed. The problem to decide whether a program P has a stable model of size no more than k , where k is fixed and not a part of input, can be solved in time O ( mn k ), where m is the size of P and n is the number of atoms in P . Thus, this problem is in the class P. However, algorithms with the running time given by a polynomial of order k are not satisfactory even for relatively small values of k .The key question then is whether significantly better algorithms (with the degree of the polynomial not dependent on k ) exist. To tackle it, we use the framework of fixed-parameter complexity. We establish the fixed-parameter complexity for several parameterized decision problems involving models, supported models, and stable models of logic programs. We also establish the fixed-parameter complexity for variants of these problems resulting from restricting attention to definite Horn programs and to purely negative programs. Most of the problems considered in the paper have high fixed-parameter complexity. Thus, it is unlikely that fixing bounds on models (supported models, stable models) will lead to fast algorithms to decide the existence of such models.

Abstract Letgk(n) [respectively,fk(n)] be the maximum number of spanning trees in directed circulant graphs (respectively, regular directed graphs) withnvertices and out‐degrees equal tok> 1. We show thatgk(n) =kn(1+o(1))andfk(n) =kn(1+o(1)). Moreover, we prove thatg2(n) = ⌊(2n+ 1)/3⌋. © 2001 John Wiley & Sons, Inc.

Let H be a complete n-uniform hypergraph, the edges of which are colored with c colors. A subhypergraph of H is called monochromatic if all its edges are colored with the same color. We prove that, for fixed n, c, and k, the problem of deciding whether H admits a partition of its vertex set into subsets inducing complete monochromatic subhypergraphs of order at least k is polynomial.

The well-founded semantics is one of the most widely studied and used semantics of logic programs with negation. In the case of finite propositional programs, it can be computed in polynomial time, more specifically, in O([mid ]At(P)[mid ] × size(P)) steps, where size(P) denotes the total number of occurrences of atoms in a logic program P. This bound is achieved by an algorithm introduced by Van Gelder and known as the alternating-fixpoint algorithm. Improving on the alternating-fixpoint algorithm turned out to be difficult. In this paper we study extensions and modifications of the alternating-fixpoint approach. We then restrict our attention to the class of programs whose rules have no more than one positive occurrence of an atom in their bodies. For programs in that class we propose a new implementation of the alternating-fixpoint method in which false atoms are computed in a top-down fashion. We show that our algorithm is faster than other known algorithms and that for a wide class of programs it is linear and so, asymptotically optimal.

The following asymptotic estimation of the maximum number of spanning trees fk(n) in 2k-regular circulant graphs (k > 1) on n vertices is the main result of this paper: fk(n) = ((2k)/(rk))n(1+o(1)), where © 1997 John Wiley & Sons, Inc. Networks 30:47–56, 1997