Given a hypergraph H⊆2V on a finite base set V, a vertex v∈V is called the private vertex of a hyperedge H∈H if H is the only hyperedge of H containing it. A hypergraph is called irredundant if every edge of it has a private vertex, and it is called redundant otherwise. Motivated by some graph domination problems, Uno (2015) posed the problems of generating all minimal redundant and maximal irredundant subhypergraphs of a given hypergraph. Here we prove that these are NP-hard generation problems, and present positive results for certain special cases.

Abstract. Horn functions form a subclass of Boolean functions possessing interesting structural and computational properties. These functions play a fundamental role in algebra, artificial intelligence, combinatorics, computer science, database theory, and logic. In the present paper, we introduce the subclass of hypergraph Horn functions that generalizes matroids and equivalence relations. We provide multiple characterizations of hypergraph Horn functions in terms of implicate-duality and the closure operator, which are, respectively, regarded as generalizations of matroid duality and the Mac Lane–Steinitz exchange property of matroid closure. We also study algorithmic issues on hypergraph Horn functions and show that the recognition problem (i.e., deciding if a given definite Horn CNF represents a hypergraph Horn function) and key realization (i.e., deciding if a given hypergraph is realized as a key set by a hypergraph Horn function) can be done in polynomial time, while implicate sets can be generated with polynomial delay.

In fair division problems, we are given a set S of m items and a set N of n agents with individual preferences, and the goal is to find an allocation of items among agents so that each agent finds the allocation fair. There are several established fairness concepts and envy-freeness is one of the most extensively studied ones. However envy-free allocations do not always exist when items are indivisible and this has motivated relaxations of envy-freeness: envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are two well-studied relaxations. We consider the problem of finding EF1 and EFX allocations for utility functions that are not necessarily monotone, and propose four possible extensions of different strength to this setting. In particular, we present a polynomial time algorithm for finding an EF1 allocation for two agents with arbitrary utility functions. An example is given showing that EFX allocations need not exist for two agents with non-monotone, non-additive, identical utility functions. However, when all agents have monotone (not necessarily additive) identical utility functions, we give a pseudo-polynomial time algorithm that always finds an EFX allocation of chores. As a step toward understanding the general case, we discuss two subclasses of utility functions: Boolean utilities that are {0,+1}-valued functions, and negative Boolean utilities that are {0,−1}-valued functions. For the latter, we give a polynomial time algorithm that finds an EFX allocation when the utility functions are identical.

Horn functions form an important subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependencies. Finding minimum sized representations for such functions with respect to most commonly used measures is a computationally hard problem admitting a $2^{\log^{1-o(1)}n}$ inapproximability bound. In this paper we consider the natural class of key Horn functions representing keys of relational databases. For this class, the minimization problems for most measures remain NP-hard. In this paper we provide logarithmic factor approximation algorithms for key Horn functions with respect to all such measures.

Given a relational database, a key is a set of attributes such that a value assignment to this set uniquely determines the values of all other attributes. The database uniquely defines a pure Horn function h, representing the functional dependencies. If the knowledge of the attribute values in set A determines the value for attribute v, then A→v is an implicate of h. If K is a key of the database, then K→v is an implicate of h for all attributes v. Keys of small sizes play a crucial role in various problems. We present structural and complexity results on the set of minimal keys of pure Horn functions. We characterize Sperner hypergraphs for which there is a unique pure Horn function with the given hypergraph as the set of minimal keys. Furthermore, we show that recognizing such hypergraphs is co-NP-complete already when every hyperedge has size two. On the positive side, we identify several classes of graphs for which the recognition problem can be decided in polynomial time. We also present an algorithm that generates the minimal keys of a pure Horn function with polynomial delay, improving on earlier results. By establishing a connection between keys and target sets, our approach can be used to generate all minimal target sets with polynomial delay when the thresholds are bounded by a constant. As a byproduct, our proof shows that the Minimum Key problem is at least as hard as the Minimum Target Set Selection problem with bounded thresholds.

Given a CNF formula Φ with clauses C1,…,Cm and variables V={x1,…,xn}, a truth assignment a:V→{0,1} of Φ leads to a clause sequence σΦ(a)=(C1(a),…,Cm(a))∈{0,1}m where Ci(a)=1 if clause Ci evaluates to 1 under assignment a, otherwise Ci(a)=0. The set of all possible clause sequences carries a lot of information on the formula, e.g. SAT, MAX-SAT and MIN-SAT can be encoded in terms of finding a clause sequence with extremal properties. We consider a problem posed at Dagstuhl Seminar 19211 “Enumeration in Data Management” (2019) about the generation of all possible clause sequences of a given CNF with bounded dimension. We prove that the problem can be solved in incremental polynomial time. We further give an algorithm with polynomial delay for the class of tractable CNF formulas. We also consider the generation of maximal and minimal clause sequences, and show that generating maximal clause sequences is NP-hard, while minimal clause sequences can be generated with polynomial delay.

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.

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.

Higher-order Markov Random Fields, which can capture important properties of natural images, have become increasingly important in computer vision. While graph cuts work well for first-order MRF's, until recently they have rarely been effective for higher-order MRF's. Ishikawa's graph cut technique [1], [2] shows great promise for many higher-order MRF's. His method transforms an arbitrary higher-order MRF with binary labels into a first-order one with the same minima. If all the terms are submodular the exact solution can be easily found; otherwise, pseudoboolean optimization techniques can produce an optimal labeling for a subset of the variables. We present a new transformation with better performance than [1], [2], both theoretically and experimentally. While [1], [2] transforms each higher-order term independently, we use the underlying hypergraph structure of the MRF to transform a group of terms at once. For n binary variables, each of which appears in terms with k other variables, at worst we produce n non-submodular terms, while [1], [2] produces O(nk). We identify a local completeness property under which our method perform even better, and show that under certain assumptions several important vision problems (including common variants of fusion moves) have this property. We show experimentally that our method produces smaller weight of non-submodular edges, and that this metric is directly related to the effectiveness of QPBO [3]. Running on the same field of experts dataset used in [1], [2] we optimally label significantly more variables (96 versus 80 percent) and converge more rapidly to a lower energy. Preliminary experiments suggest that some other higher-order MRF's used in stereo [4] and segmentation [5] are also locally complete and would thus benefit from our work.

We study a difficult real life scheduling problem encountered in oil and petrochemical industry, involving inventory and distribution operations, which requires integrated scheduling. The problem itself is NP-complete, however we show some special cases, and propose polynomial time solution methods. These could be used as a starting point for a heuristic making use of these simplified cases. This study proposes two alternative approaches for the main problem, one of them making use of one of the special cases using minimum cost flow formulation, and the other one using Bender’s Decomposition once the problem is reformulated to make it easier to handle. Both results show promising results and computation time. Bender’s Decomposition approach allows exact solutions to be found in a much faster fashion.

Abstract Motivated by challenges related to domination, connectivity, and information propagation in social and other networks, we initiate the study of the VECTOR CONNECTIVITY problem. This problem takes as input a graph G and an integer kv for every vertex v of G, and the objective is to find a vertex subset S of minimum cardinality such that every vertex v either belongs to S, or is connected to at least kv vertices of S by disjoint paths. If we require each path to be of length exactly 1, we get the well‐known VECTOR DOMINATION problem, which is a generalization of the famous DOMINATING SET problem and several of its variants. Consequently, our problem becomes NP‐hard if an upper bound on the length of the disjoint paths is also supplied as input. Due to the hardness of these domination variants even on restricted graph classes, like split graphs, VECTOR CONNECTIVITY seems to be a natural problem to study for drawing the boundaries of tractability for this type of problems. We show that VECTOR CONNECTIVITY can actually be solved in polynomial time on split graphs, in addition to cographs and trees. We also show that the problem can be approximated in polynomial time within a factor of on all n‐vertex graphs.Copyright © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 277–285 2014

Higher-order Markov Random Fields, which can capture important properties of natural images, have become increasingly important in computer vision. While graph cuts work well for first-order MRF's, until recently they have rarely been effective for higher-order MRF's. Ishikawa's graph cut technique [8, 9] shows great promise for many higher-order MRF's. His method transforms an arbitrary higher-order MRF with binary labels into a first-order one with the same minima. If all the terms are submodular the exact solution can be easily found; otherwise, pseudo-boolean optimization techniques can produce an optimal labeling for a subset of the variables. We present a new transformation with better performance than [8, 9], both theoretically and experimentally. While [8, 9] transforms each higher-order term independently, we transform a group of terms at once. For n binary variables, each of which appears in terms with k other variables, at worst we produce n non-submodular terms, while [8, 9] produces O(nk). We identify a local completeness property that makes our method perform even better, and show that under certain assumptions several important vision problems (including common variants of fusion moves) have this property. Running on the same field of experts dataset used in [8, 9] we optimally label significantly more variables (96% versus 80%) and converge more rapidly to a lower energy. Preliminary experiments suggest that some other higher-order MRF's used in stereo [20] and segmentation [1] are also locally complete and would thus benefit from our work.

Given the prime conjunctive normal form (CNF) representation $\phi$ of a monotone Boolean function $f:\{0,1\}^n\to\{0,1\}$, the dualization problem calls for finding the corresponding prime disjunctive normal form representation $\psi$ of f. A very simple method works by multiplying out the clauses of $\phi$ from left to right in some order, simplifying whenever possible by using the absorption law. We show that for any monotone CNF $\phi$, left-to-right multiplication can be done in subexponential time, and for many interesting subclasses of monotone CNFs such as those with bounded size, bounded degree, bounded intersection, bounded conformality, and read-once formula, it can be done in polynomial or quasi-polynomial time.

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.

Orthogonal forms of positive Boolean functions play an important role in reliability theory, since the probability that they take value 1 can be easily computed. However, few classes of disjunctive normal forms are known for which orthogonalization can be efficiently performed. An interesting class with this property is the class of shellable disjunctive normal forms (DNFs). In this paper, we present some new results about shellability. We establish that every positive Boolean function can be represented by a shellable DNF, we propose a polynomial procedure to compute the dual of a shellable DNF, and we prove that testing the so-called lexico-exchange (LE) property (a strengthening of shellability) is NP-complete.

Describes a new, logic-based methodology for analyzing observations. The key features of this “logical analysis of data” (LAD) methodology are the discovery of minimal sets of features that are necessary for explaining all observations and the detection of hidden patterns in the data that are capable of distinguishing observations describing “positive” outcome events from “negative” outcome events. Combinations of such patterns are used for developing general classification procedures. An implementation of this methodology is described in this paper, along with the results of numerical experiments demonstrating the classification performance of LAD in comparison with the reported results of other procedures. In the final section, we describe three pilot studies on applications of LAD to oil exploration, psychometric testing and the analysis of developments in the Chinese transitional economy. These pilot studies demonstrate not only the classification power of LAD but also its flexibility and capability to provide solutions to various case-dependent problems.

No abstract available.

We consider the problem of identifying an unknown Boolean function f by asking an oracle the functional values $f(a)$ for a selected set of test vectors $a \in \{0,1\}^{n}$. Furthermore, we assume that f is a positive (or monotone) function of n variables. It is not yet known whether or not the whole task of generating test vectors and checking if the identification is completed can be carried out in polynomial time in n and m, where $m=|\min T(f)| + |\max F(f)|$ and $\min T(f)$ (respectively, $\max F(f))$ denotes the set of minimal true (respectively, maximal false) vectors of f. To partially answer this question, we propose here two polynomial-time algorithms that, given an unknown positive function f of n variables, decide whether or not f is 2-monotonic and, if f is 2-monotonic, output both sets $\min T(f)$ and $\max F(f)$. The first algorithm uses $O(nm^{2} + n^{2}m)$ time and $O(nm)$ queries, while the second one uses $O(n^{3}m)$ time and $O(n^{3}m)$ queries.

This paper associates a linear programming problem (LP) to any conjunctive normal form $\phi $, and shows that the optimum value $Z(\phi )$ of this LP measures the complexity of the corresponding ${\textit{SAT}}$ (Boolean satisfiability) problem. More precisely, there is an algorithm for ${\textit{SAT}}$ that runs in polynomial time on the class of satisfiability problems satisfying $Z(\phi ) \leqslant 1 + \tfrac{{c\log n}}{n}$ for a fixed constant c, where c is the number of variables. In contrast, for any fixed $\beta < 1$, $SAT$ is still NP complete when restricted to the class of CNFs for which $Z(\phi ) \leqslant 1 + ({1 / {n^\beta }})$.

This paper addresses a prediction problem occurring frequently in practice. The problem consists in predicting the value of a function on the basis of discrete observational data that are incomplete in two senses. Only certain arguments of the function are observed, and the function value is observed only for certain combinations of values of these arguments. The problem is considered under a monotonicity condition that is natural in many applications. Applications to tax auditing, medicine, and real estate valuation are discussed. In particular, a special class of problems is identified for which the best monotone prediction can be found in polynomial time.

In this paper a new lower bound for unconstrained quadratic 0 – 1 minimization is investigated. It is shown that this bound can be computed by solving a linear programming problem of polynomial size in the number of variables; and it is shown that the polyhedron ${\text{S}}^{[3]} $, defined by the constraints of this LP formulation is precisely the first Chvátal closure of the polyhedron associated with standard linearization procedures. By rewriting the quadratic minimization problem as a balancing problem in a weighted signed graph, it can be seen that the polyhedron defined by the odd cycle inequalities is equivalent, in a certain sense, with ${\text{S}}^{[3]} $. As a corollary, a compact linear programming formulation is presented for the maximum cut problem for the case of weakly bipartite graphs.

Data flow machines whose task graphs are acyclic can be transformed into synchronous machines, thereby increasing pipelining and throughput. This is achieved by introducing delays or buffers on certain lines, so that the resulting graph is balanced, i.e., travel times along any two paths with common endpoints are the same. The buffer assignment problem is how to balance a rooted acyclic data flow graph with a minimum number of buffer units. Recently, an integer programming decomposition procedure was proposed for this problem. The decomposition was introduced in an attempt to circumvent the exponential blowup typical of integer programming algorithms. It is shown that the buffer assignment problem can in fact be solved to optimality in low-degree polynomial time. The result is obtained by a sequence of reformulations of the problem, leading to models to which simple and efficient network flow procedures can be successfully applied.>