In several recent papers some concepts of convex analysis were extended to discrete sets. The present paper is one more step in this direction. It is well known that a local minimum of a convex function is always its global minimum. We study some discrete objects that share this property and provide several examples of convex families related to graphs and to two-person games in normal form.

We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense.

For the classical backward induction algorithm, the input is an arbitrary |$n$|-person positional game with perfect information modelled by a finite acyclic directed graph (digraph) and the output is a profile |$(x_1, \ldots , x_n)$| of pure positional strategies that form some special subgame perfect Nash equilibrium (NE). We extend this algorithm to work with digraphs that may have directed cycles. Each digraph admits a unique partition into strongly connected (SC) components, which will be treated as the outcomes of a game. Such games will be called deterministic graphical multistage (DGMS) games. If we merge the outcomes corresponding to all SC components, except terminals, we obtain the so-called deterministic graphical (DG) games, which are frequent in the literature. The outcomes of a DG game are all terminals and one special outcome |$c$| that is assigned to all infinite plays. We modify the backward induction procedure to adapt it for the DG and DGMS games. Yet, we have to pay the price for this extension. The new algorithm always outputs an NE only when |$n = 2$| and, even in this case, the obtained NE may be not subgame perfect. (Although in the zero-sum case it is.) The lack of these two properties is not a fault of the algorithm, just (subgame perfect) NEs in pure positional strategies may fail to exist in the considered game.

We consider finite Markov decision processes (MDPs) with undiscounted total effective payoff. We show that there exist uniformly optimal pure stationary strategies that can be computed by solving a polynomial number of linear programs. We apply this result to two-player zero-sum stochastic games with perfect information and undiscounted total effective payoff, and derive the existence of a saddle point in uniformly optimal pure stationary strategies.

Let G=(V,E) be an undirected graph, and let B⊆V×V be a collection of vertex pairs. We give an incremental polynomial time algorithm to generate all minimal edge sets X⊆E such that every pair (s,t)∈B of vertices is disconnected in (V,E ∖ X), generalizing well-known efficient algorithms for generating all minimal s-t cuts, for a given pair s,t of vertices. We also present an incremental polynomial time algorithm for generating all minimal subsets X⊆E such that no (s,t)∈B is a bridge in (V,X∪B). Both above problems are special cases of a more general problem that we call generating cut conjunctions for matroids: given a matroid M on ground set S=E∪B, generate all minimal subsets X⊆E such that no element b∈B is spanned by E ∖ X. Unlike the above special cases, corresponding to the cycle and cocycle matroids of the graph (V,E∪B), the more general problem of generating cut conjunctions for vectorial matroids turns out to be NP-hard.

We consider the problems of enumerating all minimal strongly connected subgraphs and all minimal dicuts of a given strongly connected directed graph G=(V,E). We show that the first of these problems can be solved in incremental polynomial time, while the second problem is NP-hard: given a collection of minimal dicuts for G, it is NP-hard to tell whether it can be extended. The latter result implies, in particular, that for a given set of points $\mathcal{A}\subseteq\mathbb{R}^{n}$ , it is NP-hard to generate all maximal subsets of $\mathcal{A}$ contained in a closed half-space through the origin. We also discuss the enumeration of all minimal subsets of $\mathcal{A}$ whose convex hull contains the origin as an interior point, and show that this problem includes as a special case the well-known hypergraph transversal problem.

We show that generating all negative cycles of a weighted graph is a hard enumeration problem, in both the directed and undirected cases. More precisely, given a family of negative (directed) cycles, it is an NP-complete problem to decide whether this family can be extended or there are no other negative (directed) cycles in the graph, implying that (directed) negative cycles cannot be generated in polynomial output time, unless P=NP. As a corollary, we solve in the negative two well-known generating problems from linear programming: (i) Given an infeasible system of linear inequalities, generating all minimal infeasible subsystems is hard. Yet, for generating maximal feasible subsystems the complexity remains open. (ii) Given a feasible system of linear inequalities, generating all vertices of the corresponding polyhedron is hard. Yet, in the case of bounded polyhedra the complexity remains open. Equiva lently, the complexity of generating vertices and extreme rays of polyhedra remains open.

Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A→ℝ+ and two terminals s,t∈V, our goal is to destroy all short directed paths from s to t in G by eliminating some arcs of A. This is known as the short paths interdiction problem. We consider several versions of it, and in each case analyze two subcases: total limited interdiction, when a fixed number k of arcs can be removed, and node-wise limited interdiction, when for each node v∈V a fixed number k(v) of out-going arcs can be removed. Our results indicate that the latter subcase is always easier than the former one. In particular, we show that the short paths node-wise interdiction problem can be efficiently solved by an extension of Dijkstra’s algorithm. In contrast, the short paths total interdiction problem is known to be NP-hard. We strengthen this hardness result by deriving the following inapproximability bounds: Given k, it is NP-hard to approximate within a factor c<2 the maximum s–t distance d(s,t) obtainable by removing (at most) k arcs from G. Furthermore, given d, it is NP-hard to approximate within a factor $c<10\sqrt{5}-21\approx1.36$ the minimum number of arcs which has to be removed to guarantee d(s,t)≥d. Finally, we also show that the same inapproximability bounds hold for undirected graphs and/or node elimination.

Let M be a matroid defined by an independence oracle on ground set S, and let $A\subseteq S$. We present an incremental polynomial-time algorithm for enumerating all minimal (maximal) subsets of S which span (do not span) A. Special cases of these problems include the generation of bases, circuits, hyperplanes, flats of given rank, circuits through a given element, generalized Steiner trees, and multiway cuts in graphs, as well as some other applications. We also consider some tractable and NP-hard generation problems related to systems of polymatroid inequalities and (generalized) packing and spanning in matroids.

We consider the problem of enumerating all minimal integer solutions of a monotone system of linear inequalities. We first show that, for any monotone system of r linear inequalities in n variables, the number of maximal infeasible integer vectors is at most rn times the number of minimal integer solutions to the system. This bound is accurate up to a polylog(r) factor and leads to a polynomial-time reduction of the enumeration problem to a natural generalization of the well-known dualization problem for hypergraphs, in which dual pairs of hypergraphs are replaced by dual collections of integer vectors in a box. We provide a quasi-polynomial algorithm for the latter dualization problem. These results imply, in particular, that the problem of incrementally generating all minimal integer solutions to a monotone system of linear inequalities can be done in quasi-polynomial time.

We consider two generalizations of the notion of transversal to a finite hypergraph, the so-called multiple and partial transversals. Multiple transversals naturally arise in 0-1 programming, while partial transversals are related to data mining and machine learning. We show that for an arbitrary hypergraph the families of multiple and partial transversals are both dual-bounded in the sense that the size of the corresponding dual hypergraph is bounded by a polynomial in the cardinality and the length of description of the input hypergraph. Our bounds are based on new inequalities of extremal set theory and threshold Boolean logic, which may be of independent interest. We also show that the problems of generating all multiple and all partial transversals for a given hypergraph are polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i.e., to the well-known dualization problem for hypergraphs. As a corollary, we obtain incremental quasi-polynomial-time algorithms for both of the above problems, as well as for the generation of all the minimal binary solutions for an arbitrary monotone system of linear inequalities.