In a public goods game, every player chooses whether or not to buy a good that all neighboring players will have access to. We consider a setting in which the good is indivisible, neighboring players are out-neighbors in a directed graph, and there is a capacity constraint on their number, k, that can benefit from the good. This means that each player makes a two-pronged decision: decide whether or not to buy and, conditional on buying, choose which k out-neighbors to share access. We examine both pure and mixed Nash equilibria in the model from the perspective of existence, computation, and efficiency. We perform a comprehensive study for these three dimensions with respect to both sharing capacity (k) and the network structure (the underlying directed graph), and establish sharp complexity dichotomies for each.

A digraph is semicomplete if it has no pair of non-adjacent vertices. It is complete if every pair of distinct vertices induces a 2-cycle. A digraph is semicomplete multipartite if it can be obtained from a semicomplete digraph D by choosing a collection of vertex-disjoint subsets X1,…,Xc of V(D) and then deleting all arcs both of whose end-vertices lie inside some Xi. We can also think of a semicomplete digraph as being obtained from a semicomplete multipartite digraph on the same vertex set and partite sets V1,…,Vc by adding the arcs of a semicomplete digraph Di on Vi for each partite set Vi. It is well known that both the hamiltonian path and the hamiltonian cycle problem can be solved in polynomial time for semicomplete multipartite digraphs. In this paper we study the complexity of finding a hamiltonian path or cycle in a semicomplete digraph S which is obtained as above from a semicomplete multipartite digraph D and semicomplete digraphs Di=(Vi,Ai), i∈[c] such that the path or cycle uses as few arcs of A1∪…Ac as possible. We obtain a number of results for the case when each Di is a complete digraph. Already this case is highly nontrivial in the cycle case and the complexity is still open. We show how to find a Hamiltonian path which uses as few arcs from the Di’s as possible in polynomial time and obtain a number of results, both structural and algorithmic on hamiltonian cycles that use the minimum or close to the minimum number of arcs from the Di’s. Our results imply the polynomial solvability of some special cases of the NP-complete {0,1}-TSP problem. Finally we show that two natural questions about properties of quasi-hamiltonian cycles, that is, cycles meeting all partite sets in semicomplete multipartite digraphs are NP-complete.

Abstract. We obtain lower and upper bounds for the maximum weight of a directed cut in the classes of weighted digraphs and weighted acyclic digraphs as well as in some of their subclasses. We compare our results with those obtained for the maximum size of a directed cut in unweighted digraphs. In particular, we show that a lower bound obtained by Alon, Bollobás, Gyárfás, Lehel, and Scott [ J. Graph Theory, 55 (2007), pp. 1–13] for unweighted acyclic digraphs can be extended to weighted digraphs with the maximum length of a cycle being bounded by a constant and the weight of every arc being at least one. We state a number of open problems.

We investigate the difficulty of finding economically efficient solutions to coordination problems on graphs. Our work focuses on two forms of coordination problem: pure-coordination games and anti-coordination games. We consider three objectives in the context of simple binary-action polymatrix games: (i) maximizing welfare, (ii) maximizing potential, and (iii) finding a welfare-maximizing Nash equilibrium. We introduce an intermediate, new graph-partition problem, termed MWDP, which is of independent interest, and we provide a complexity dichotomy for it. This dichotomy, among other results, provides as a corollary a dichotomy for Objective (i) for general binary-action polymatrix games. In addition, it reveals that the complexity of achieving these objectives varies depending on the form of the coordination problem. Specifically, Objectives (i) and (ii) can be efficiently solved in pure-coordination games, but are NP-hard in anti-coordination games. Finally, we show that objective (iii) is NP-hard even for simple non-trivial pure-coordination games.

Gerke et al. (2019) introduced a game-theoretic model to study public good provision in social networks when there are constraints on sharing. This model generates a purely graph-theoretic problem termed exact capacitated domination. In the problem we are given a capacitated graph, a graph with a parameter defined on each vertex that is interpreted as the capacity of that vertex. The objective is to find a DP-Nash subgraph: a spanning bipartite subgraph with partite sets D and P, called the D-set and P-set respectively, such that no vertex in P is isolated and that each vertex in D is adjacent to a number of vertices equal to its capacity. We show that whether a capacitated graph has a unique DP-Nash subgraph can be decided in polynomial time. However, we also show that the closely related problem of deciding whether a capacitated graph has a unique D-set is co-NP-complete.

A graph H is a clique graph if H is a vertex-disjoin union of cliques. Abu-Khzam (2017) introduced the (a,d)-Cluster Editing problem, where for fixed natural numbers a,d, given a graph G and vertex-weights a∗:V(G)→{0,1,…,a} and d∗:V(G)→{0,1,…,d}, we are to decide whether G can be turned into a cluster graph by deleting at most d∗(v) edges incident to every v∈V(G) and adding at most a∗(v) edges incident to every v∈V(G). Results by Komusiewicz and Uhlmann (2012) and Abu-Khzam (2017) provided a dichotomy of complexity (in P or NP-complete) of (a,d)-Cluster Editing for all pairs a,d apart from a=d=1. Abu-Khzam (2017) conjectured that (1,1)-Cluster Editing is in P. We resolve Abu-Khzam’s conjecture in affirmative by (i) providing a series of five polynomial-time reductions to C3-free and C4-free graphs of maximum degree at most 3, and (ii) designing a polynomial-time algorithm for solving (1,1)-Cluster Editing on C3-free and C4-free graphs of maximum degree at most 3.

Abstract. While there have been many results on lower bounds for Max Cut in unweighted graphs, the only lower bound for noninteger weights is that by Poljak and Turzík [ Discrete Math., 58 (1986), pp. 99–104]. In this paper, we launch an extensive study of lower bounds for Max Cut in weighted graphs. We introduce a new approach for obtaining lower bounds for Weighted Max Cut. Using it, the probabilistic method, Vizing’s chromatic index theorem, and other tools, we obtain several lower bounds for arbitrary weighted graphs, weighted graphs of bounded girth, and triangle-free weighted graphs. We pose conjectures and open questions.

Abstract. The transversal number [Formula: see text] of a hypergraph [Formula: see text] is the minimum number of vertices that intersect every edge of [Formula: see text]. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [ Discuss. Math. Graph Theory, 22 (2002), pp. 199–210] conjectured that if [Formula: see text] is a 3-regular 6-uniform hypergraph of order [Formula: see text], then [Formula: see text]. In this paper we prove this conjecture, which has become known as the Tuza–Vestergaard conjecture.

As usual λ(G) denotes the edge-connectivity of the graph G. It was shown in [2] that every graph G contains a spanning (λ(G)+1)-partite subgraph H such that λ(H)=λ(G) and one can find such a spanning subgraph in polynomial time. We determine the complexity of deciding, for given positive integers r,k whether a graph contains a spanning r-colourable subgraph which is k-edge-connected. We show that the problem is polynomially solvable when r>k and NP-complete otherwise. In fact, combined with the result from [2] above, this means that the problem is polynomially solvable precisely when r is such that every k-edge-connected graph has a spanning r-colourable subgraph which is k-edge-connected. One can show that all graphs whose edge set decomposes into k edge-disjoint spanning trees are 2k-colourable. We consider the problem of deciding whether a given graph G has a collection of k edge-disjoint spanning trees whose union forms an r-colourable spanning subgraph H of G. We show that this problem is polynomially solvable when r≥2k and NP-complete for all other values of r. We also determine the complexity of the analogous problem of deciding whether a digraph D has a collection of k arc-disjoint out-branchings such that the spanning subdigraph formed by the union of the arcs in the branchings is r-colourable.

An instance I of the Stable Matching Problem (SMP) is given by a bipartite graph with a preference list of neighbors for every vertex. A swap in I is the exchange of two consecutive vertices in a preference list. A swap can be viewed as a smallest perturbation of I. Boehmer et al. (2021) designed a polynomial-time algorithm for finding the minimum number of swaps required to turn a given maximal matching into a stable matching. We generalize this result to the many-to-many version of SMP. We do so first by introducing a new representation of SMP as an extended bipartite graph and subsequently by reducing the problem to submodular minimization. It is a natural problem to establish the computational complexity of deciding whether at most k swaps are enough to turn I into an instance where one of the maximum matchings is stable. Using a hardness result of Gupta et al. (2020), we prove that this problem is NP-hard and, moreover, this problem parameterised by k is W[1]-hard. We also obtain a lower bound on the running time for solving the problem using the Exponential Time Hypothesis.

Abstract A directed graph D is semicomplete if for every pair x, y of vertices of D, there is at least one arc between x and y. Thus, a tournament is a semicomplete digraph. In the Directed Component Order Connectivity (DCOC) problem, given a digraph $$D=(V,A)$$ D = ( V , A ) and a pair of natural numbers k and $$\ell $$ ℓ , we are to decide whether there is a subset X of V of size k such that the largest strongly connected component in $$D-X$$ D - X has at most $$\ell $$ ℓ vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for $$\ell =1.$$ ℓ = 1 . We study the parameterized complexity of DCOC for general and semicomplete digraphs with the following parameters: $$k, \ell ,\ell +k$$ k , ℓ , ℓ + k and $$n-\ell $$ n - ℓ . In particular, we prove that DCOC with parameter k on semicomplete digraphs can be solved in time $$O^*(2^{16k})$$ O ∗ ( 2 16 k ) but not in time $$O^*(2^{o(k)})$$ O ∗ ( 2 o ( k ) ) unless the Exponential Time Hypothesis (ETH) fails. The upper bound $$O^*(2^{16k})$$ O ∗ ( 2 16 k ) implies the upper bound $$O^*(2^{16(n-\ell )})$$ O ∗ ( 2 16 ( n - ℓ ) ) for the parameter $$n-\ell .$$ n - ℓ . We complement the latter by showing that there is no algorithm of time complexity $$O^*(2^{o({n-\ell })})$$ O ∗ ( 2 o ( n - ℓ ) ) unless ETH fails. Finally, we improve (in dependency on $$\ell $$ ℓ ) the upper bound of Göke, Marx and Mnich (2019) for the time complexity of DCOC with parameter $$\ell +k$$ ℓ + k on general digraphs from

Let G be a graph on n vertices. For i ∈ {0,1} and a connected graph G, a spanning forest F of G is called an i-perfect forest if every tree in F is an induced subgraph of G and exactly i vertices of F have even degree (including zero). An i-perfect forest of G is proper if it has no vertices of degree zero. Scott (2001) showed that every connected graph with even number of vertices contains a (proper) 0-perfect forest. We prove that one can find a 0-perfect forest with minimum number of edges in polynomial time, but it is NP-hard to obtain a 0-perfect forest with maximum number of edges. We also prove that for a prescribed edge e of G, it is NP-hard to obtain a 0-perfect forest containing e, but we can find a 0-perfect forest not containing e in polynomial time. It is easy to see that every graph with odd number of vertices has a 1-perfect forest. It is not the case for proper 1-perfect forests. We give a characterization of when a connected graph has a proper 1-perfect forest.

A directed graph D is semicomplete if for every pair x,y of vertices of D, there is at least one arc between x and y. Thus, a tournament is a semicomplete digraph. In the Directed Component Order Connectivity (DCOC) problem, given a digraph D = (V,A) and a pair of natural numbers k and 𝓁, we are to decide whether there is a subset X of V of size k such that the largest strong connectivity component in D-X has at most 𝓁 vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for 𝓁 = 1. We study parameterized complexity of DCOC for general and semicomplete digraphs with the following parameters: k, 𝓁, 𝓁+k and n-𝓁. In particular, we prove that DCOC with parameter k on semicomplete digraphs can be solved in time O^*(2^(16k)) but not in time O^*(2^o(k)) unless the Exponential Time Hypothesis (ETH) fails. The upper bound O^*(2^(16k)) implies the upper bound O^*(2^(16(n-𝓁))) for the parameter n-𝓁. We complement the latter by showing that there is no algorithm of time complexity O^*(2^o(n-𝓁)) unless ETH fails. Finally, we improve (in dependency on 𝓁) the upper bound of Göke, Marx and Mnich (2019) for the time complexity of DCOC with parameter 𝓁+k on general digraphs from O^*(2^O(k𝓁 log (k𝓁))) to O^*(2^O(klog (k𝓁))). Note that Drange, Dregi and van 't Hof (2016) proved that even for the undirected version of DCOC on split graphs there is no algorithm of running time O^*(2^o(klog 𝓁)) unless ETH fails and it is a long-standing problem to decide whether Directed Feedback Vertex Set admits an algorithm of time complexity O^*(2^o(klog k)).

Let $H = (V,E)$ be a hypergraph with vertex set $V$ and edge set $E$ of order ${n_{_H}} = |V|$ and size ${m_{_H}} = |E|$. The hypergraph $H$ is $k$-uniform if every edge of $H$ has size $k$. Two vertices in $H$ are adjacent if they belong to a common edge in $H$. A transversal in $H$ is a subset of vertices in $H$ that has a nonempty intersection with every edge of $H$. A total transversal in $H$ is a transversal $T$ in $H$ with the additional property that every vertex in $T$ is adjacent to some other vertex of $T$. The total transversal number $\tau_t(H)$ of $H$ is the minimum cardinality of a total transversal in $H$. For $k \ge 2$, let $b_k = \sup_{H \in {\cal H}_k} \, {\tau_t}(H) / ({n_{_H}} + {m_{_H}})$, where ${\cal H}_k$ denotes the class of all $k$-uniform hypergraphs containing no isolated vertices or isolated edges or multiple edges. It is known that $b_2 = 2/5$, $b_3 = 1/3$, $b_4 \le 1/3$, and $b_5 \le 2/7$. In this paper, we show that $b_4 = 2/7$ and $b_6 \le 1/4$. Further, for $k \ge 7$, we show that $b_7 \le 2/9$. These results on total transversals have applications in total domination in hypergraphs. A total dominating set in $H$ is a subset of vertices $D \subseteq V$ such that every vertex in $H$ is adjacent to some vertex in $D$. The total domination number $\gamma_t(H)$ is the minimum cardinality of a total dominating set in $H$. The following relationship between the total transversal number and the total domination number of uniform hypergraphs is known: For $k \ge 3$ and $H \in {\cal H}_k$, we have ${\gamma_t}(H) \le ( \max \{ \frac{2 }{k+1}, b_{k-1} \} ) \times {n_{_H}}$. As a consequence of our results on the total transversal number, for $k \in \{2,3,4,5,6,7,8\}$ and a hypergraph $H \in {\cal H}_k$, we have ${\gamma_t}(H) \le 2{n_{_H}}/(k+1)$.

A workflow specification defines a set of steps and the order in which these steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of these steps. A workflow specification is said to be satisfiable if there exists an assignment of users to workflow steps that satisfies all the constraints. An algorithm for determining whether such an assignment exists is important, both as a static analysis tool for workflow specifications and for the construction of runtime reference monitors for workflow management systems. Finding such an assignment is a hard problem in general, but work by Wang and Li [2010] using the theory of parameterized complexity suggests that efficient algorithms exist under reasonable assumptions about workflow specifications. In this article, we improve the complexity bounds for the workflow satisfiability problem. We also generalize and extend the types of constraints that may be defined in a workflow specification and prove that the satisfiability problem remains fixed-parameter tractable for such constraints. Finally, we consider preprocessing for the problem and prove that in an important special case, in polynomial time, we can reduce the given input into an equivalent one where the number of users is at most the number of steps. We also show that no such reduction exists for two natural extensions of this case, which bounds the number of users by a polynomial in the number of steps, provided a widely accepted complexity-theoretical assumption holds.

A workflow specification defines a set of steps and the order in which those steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of those steps. A workflow specification is said to be satisfiable if there exists an assignment of users to workflow steps that satisfies all the constraints. An algorithm for determining whether such an assignment exists is important, both as a static analysis tool for workflow specifications, and for the construction of run-time reference monitors for workflow management systems. Finding such an assignment is a hard problem in general, but work by Wang and Li in 2010 using the theory of parameterized complexity suggests that efficient algorithms exist under reasonable assumptions about workflow specifications. In this paper, we improve the complexity bounds for the workflow satisfiability problem. We also generalize and extend the types of constraints that may be defined in a workflow specification and prove that the satisfiability problem remains fixed-parameter tractable for such constraints.

Thomassen [Combinatorica, 3 (1983), pp. 393–396] proved that every digraph with minimum out-degree at least three has two vertex disjoint cycles. There are examples of 3-regular digraphs where all pairs of vertex disjoint cycles have the same length. In this paper we raise the conjectures that all 3-regular bipartite digraphs and all digraphs with minimum degree at least four have two vertex disjoint cycles of different length. We give support for our conjectures by proving that all 4-regular digraphs do indeed have two vertex disjoint cycles of different length. We furthermore discuss consequences of our results and conjectures as well as arc-weighted versions of our conjecture.

In the parameterized problem MaxLin2-AA[$k$], we are given a system with variables x_1,...,x_n consisting of equations of the form Product_{i in I}x_i = b, where x_i,b in {-1, 1} and I is a nonempty subset of {1,...,n}, each equation has a positive integral weight, and we are to decide whether it is possible to simultaneously satisfy equations of total weight at least W/2+k, where W is the total weight of all equations and k is the parameter (if k=0, the possibility is assured). We show that MaxLin2-AA[k] has a kernel with at most O(k^2 log k) variables and can be solved in time 2^{O(k log k)}(nm)^{O(1)}. This solves an open problem of Mahajan et al. (2006). The problem Max-r-Lin2-AA[k,r] is the same as MaxLin2-AA[k] with two differences: each equation has at most r variables and r is the second parameter. We prove a theorem on Max-$r$-Lin2-AA[k,r] which implies that Max-r-Lin2-AA[k,r] has a kernel with at most (2k-1)r variables, improving a number of results including one by Kim and Williams (2010). The theorem also implies a lower bound on the maximum of a function f that maps {-1,1}^n to the set of reals and whose Fourier expansion (which is a multilinear polynomial) is of degree r. We show applicability of the lower bound by giving a new proof of the Edwards-Erdös bound (each connected graph on n vertices and m edges has a bipartite subgraph with at least m/2 +(n-1)/4 edges) and obtaining a generalization.

We present an exact algorithm that decides, for every fixed r ≥ 2 in time O(m) + 2O(k2) whether a given set of m clauses of size r admits a truth assignment that satisfies at least ((2r – 1)m + k)/2r clauses. Thus Max-r-Sat is fixed-parameter tractable when parameterized by the number of satisfied clauses above the tight lower bound (1 − 2−r)m. This solves an open problem of Mahajan, Raman and Sikdar (J. Comput. System Sci., 75, 2009). Our algorithm is based on a polynomial-time data reduction procedure that reduces a problem instance to an equivalent algebraically represented problem with O(k2) variables. This is done by representing the instance as an appropriate polynomial, and by applying a probabilistic argument combined with some simple tools from Harmonic analysis to show that if the polynomial cannot be reduced to one of size O(k2), then there is a truth assignment satisfying the required number of clauses. Combining another probabilistic argument with tools from graph matching theory and signed graphs, we show that if an instance of Max-2-Sat with m clauses has at least 3k variables after application of certain polynomial time reduction rules to it, then there is a truth assignment that satisfies at least (3m + k)/4 clauses. We also outline how the fixed-parameter tractability result on Max-r-Sat can be extended to a family of Boolean Constraint Satisfaction Problems.

Let H be a 3-uniform hypergraph of order n and size m, and let T be a subset of vertices of H. The set T is a strong transversal in H if T contains at least two vertices from every edge of H. The strong transversal number $\tau_s(H)$ of H is the minimum size of a strong transversal in H. We show that $7\tau_s(H)\leq4n+2m$, and we characterize the hypergraphs that achieve equality in this bound. In particular, we show that the Fano plane is the only connected 3-uniform hypergraph H of order $n\geq6$ and size m that achieves equality in this bound. A set S of vertices in a graph G is a double total dominating set of G if every vertex of G is adjacent to at least two vertices in S. The minimum cardinality of a double total dominating set of G is the double total domination number $\gamma_{\times2,t}(G)$ of G. Let G be a connected graph of order n with minimum degree at least three. As an application of our hypergraph results, we show that $\gamma_{\times2,t}(G)\leq6n/7$ with equality if and only if G is the Heawood graph (equivalently, the incidence bipartite graph of the Fano plane). Further if G is not the Heawood graph, we show that $\gamma_{\times2,t}(G)\leq11n/13$, while if G is a cubic graph different from the Heawood graph, we show that $\gamma_{\times2,t}(G)\leq5n/6$, and this bound is sharp.

The {\sc Multicut In Trees} problem consists in deciding, given a tree, a set of requests (i.e. paths in the tree) and an integer $k$, whether there exists a set of $k$ edges cutting all the requests. This problem was shown to be FPT by Guo and Niedermeyer (2005). They also provided an exponential kernel. They asked whether this problem has a polynomial kernel. This question was also raised by Fellows (2006). We show that {\sc Multicut In Trees} has a polynomial kernel.

We survey results and open questions on complexity of parameterized problems on digraphs. The problems include the feedback vertex and arc set problems, induced subdigraph problems and directed k-leaf problems. We also prove some new results on the topic. Most of these new results are on parameterizations of the backward paired comparison problem.

For digraphs D and H, a mapping $f:V(D)\rightarrow V(H)$ is a homomorphism of D to H if $uv\in A(D)$ implies $f(u)f(v)\in A(H)$. If, moreover, each vertex $u\in V(D)$ is associated with costs $c_i(u)$, $i\in V(H)$, then the cost of the homomorphism f is $\sum_{u\in V(D)}c_{f(u)}(u)$. For each fixed digraph H, we have the minimum cost homomorphism problem for H. The problem is to decide, for an input graph D with costs $c_i(u)$, $u\in V(D)$, $i\in V(H)$, whether there exists a homomorphism of D to H and, if one exists, to find one of minimum cost. Minimum cost homomorphism problems encompass (or are related to) many well-studied optimization problems. We describe a dichotomy of the minimum cost homomorphism problem for semicomplete bipartite digraphs H. This solves an open problem from an earlier paper. To obtain the dichotomy of this paper, we introduce and study a new notion, a k-Min-Max ordering of digraphs.

We consider the problem of finding a strongly connected spanning subdigraph with the minimum number of arcs in a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the Hamiltonian cycle problem. We show that the problem is polynomially solvable for quasi-transitive digraphs. We describe the minimum number of arcs in such a spanning subdigraph of a quasi-transitive digraph in terms of the path covering number. Our proofs are based on a number of results (some of which are new and interesting in their own right) on the structure of cycles and paths in quasi-transitive digraphs and in extended semicomplete digraphs. In particular, we give a new characterization of the longest cycle in an extended semicomplete digraph. Finally, we point out that our proofs imply that the MSSS problem is solvable in polynomial time for all digraphs that can be obtained from strong semicomplete digraphs on at least two vertices by replacing each vertex with a digraph belonging to a family of digraphs whose path covering number can be decided in polynomial time.

We introduce two new classes of graphs which we call convex-round, respectively concave-round graphs. Convex-round (concave-round) graphs are those graphs whose vertices can be circularly enumerated so that the (closed) neighborhood of each vertex forms an interval in the enumeration. Hence the two classes transform into each other by taking complements. We show that both classes of graphs have nice structural properties. We observe that the class of concave-round graphs properly contains the class of proper circular arc graphs and, by a result of Tucker [ Pacific J. Math., 39 (1971), pp. 535--545], is properly contained in the class of general circular arc graphs. We point out that convex-round and concave-round graphs can be recognized in O(n+m) time (here n denotes the number of vertices and m the number of edges of the graph in question). We show that the chromatic number of a graph which is convex-round (concave-round) can be found in time O(n+m) (O(n 2 )). We describe optimal O(n+m) time algorithms for finding a maximum clique, a maximum matching, and a Hamiltonian cycle (if one exists) for the class of convex-round graphs. Finally, we pose a number of open problems and conjectures concerning the structure and algorithmic properties of the two new classes and a related third class of graphs.