BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Endre Boros

Endre Boros appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Discrete Mathematicsmath.COComputer Science and Game Theorymath.OCComputational ComplexityComputer VisionArtificial IntelligenceData Structures and AlgorithmsDatabasesecon.THLogic in Computer ScienceOther Computer Science

Catalog footprint

What is connected

16works
12topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2023arXiv

Hypergraph Horn functions

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 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.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Matroid Horn functions

Hypergraph Horn functions were introduced as a subclass of Horn functions that can be represented by a collection of circular implication rules. These functions possess distinguished structural and computational properties. In particular, their characterizations in terms of implicate-duality and the closure operator provide extensions of matroid duality and the Mac Lane-Steinitz exchange property of matroid closure, respectively. In the present paper, we introduce a subclass of hypergraph Horn functions that we call matroid Horn functions. We provide multiple characterizations of matroid Horn functions in terms of their canonical and complete CNF representations. We also study the Boolean minimization problem for this class, where the goal is to find a minimum size representation of a matroid Horn function given by a CNF representation. While there are various ways to measure the size of a CNF, we focus on the number of circuits and circuit clauses. We determine the size of an optimal representation for binary matroids, and give lower and upper bounds in the uniform case. For uniform matroids, we show a strong connection between our problem and Turán systems that might be of independent combinatorial interest.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal Layered Defense For Site Protection

We present a model for layered security with applications to the protection of sites such as stadiums or large gathering places. We formulate the problem as one of maximizing the capture of illegal contraband. The objective function is indefinite and only limited information can be gained when the problem is solved by standard convex optimization methods. In order to solve the model, we develop a dynamic programming approach, and study its convergence properties. Additionally, we formulate a version of the problem aimed at addressing intelligent adversaries who can adjust their direction of attack as they observe changes in the site security. Furthermore, we also develop a method for the solution of the latter model. Finally, we perform computational experiments to demonstrate the use of our methods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Envy-free Relaxations for Goods, Chores, and Mixed Items

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 prove that an EFX allocation of chores always exists. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Generating clause sequences of a CNF formula

Given a CNF formula $Φ$ with clauses $C_1,\ldots,C_m$ and variables $V=\{x_1,\ldots,x_n\}$, a truth assignment $a:V\rightarrow\{0,1\}$ of $Φ$ leads to a clause sequence $σ_Φ(a)=(C_1(a),\ldots,C_m(a))\in\{0,1\}^m$ where $C_i(a) = 1$ if clause $C_i$ evaluates to $1$ under assignment $a$, otherwise $C_i(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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the degree sequences of dual graphs on surfaces

Given two graphs $G$ and $G^*$ with a one-to-one correspondence between their edges, when do $G$ and $G^*$ form a pair of dual graphs realizing the vertices and countries of a map embedded in a surface? A criterion was obtained by Jack Edmonds in 1965. Furthermore, let $\boldsymbol{d}=(d_1,\ldots,d_n)$ and $\boldsymbol{t}=(t_1,\ldots,t_m)$ be their degree sequences. Then, clearly, $\sum_{i=1}^n d_i = \sum_{j=1}^m t_j = 2\ell$, where $\ell$ is the number of edges in each of the two graphs, and $χ= n - \ell + m$ is the Euler characteristic of the surface. Which sequences $\boldsymbol{d}$ and $\boldsymbol{t}$ satisfying these conditions still cannot be realized as the degree sequences? We make use of Edmonds' criterion to obtain several infinite series of exceptions for the sphere, $χ= 2$, and projective plane, $χ= 1$. We conjecture that there exist no exceptions for $χ\leq 0$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Unique key Horn functions

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\rightarrow v$ is an implicate of $h$. If $K$ is a key of the database, then $K\rightarrow 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. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Convex Programming-based Algorithm for Mean Payoff Stochastic Games with Perfect Information

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph $G = (V, E)$, with local rewards $r: E \to \ZZ$, and three types of positions: black $V_B$, white $V_W$, and random $V_R$ forming a partition of $V$. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, even when $|V_R|=0$. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this short note, we show that BWR-games can be solved via convex programming in pseudo-polynomial time if the number of random positions is a constant.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Nested Family of $k$-total Effective Rewards for Positional Games

We consider Gillette's two-person zero-sum stochastic games with perfect information. For each $k \in \ZZ_+$ we introduce an effective reward function, called $k$-total. For $k = 0$ and $1$ this function is known as {\it mean payoff} and {\it total reward}, respectively. We restrict our attention to the deterministic case. For all $k$, we prove the existence of a saddle point which can be realized by uniformly optimal pure stationary strategies. We also demonstrate that $k$-total reward games can be embedded into $(k+1)$-total reward games.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Potential Reduction Algorithm for Two-person Zero-sum Mean Payoff Stochastic Games

We suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real $ε$, let us call a stochastic game $ε$-ergodic, if its values from any two initial positions differ by at most $ε$. The proposed new algorithm outputs for every $ε>0$ in finite time either a pair of stationary strategies for the two players guaranteeing that the values from any initial positions are within an $ε$-range, or identifies two initial positions $u$ and $v$ and corresponding stationary strategies for the players proving that the game values starting from $u$ and $v$ are at least $ε/24$ apart. In particular, the above result shows that if a stochastic game is $ε$-ergodic, then there are stationary strategies for the players proving $24ε$-ergodicity. This result strengthens and provides a constructive version of an existential result by Vrieze (1980) claiming that if a stochastic game is $0$-ergodic, then there are $ε$-optimal stationary strategies for every $ε> 0$. The suggested algorithm is based on a potential transformation technique that changes the range of local values at all positions without changing the normal form of the game.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Equistarable bipartite graphs

Recently, Milanič and Trotignon introduced the class of equistarable graphs as graphs without isolated vertices admitting positive weights on the edges such that a subset of edges is of total weight $1$ if and only if it forms a maximal star. Based on equistarable graphs, counterexamples to three conjectures on equistable graphs were constructed, in particular to Orlin's conjecture, which states that every equistable graph is a general partition graph. In this paper we characterize equistarable bipartite graphs. We show that a bipartite graph is equistarable if and only if every $2$-matching of the graph extends to a matching covering all vertices of degree at least $2$. As a consequence of this result, we obtain that Orlin's conjecture holds within the class of complements of line graphs of bipartite graphs. We also connect equistarable graphs to the triangle condition, a combinatorial condition known to be necessary (but in general not sufficient) for equistability. We show that the triangle condition implies general partitionability for complements of line graphs of forests, and construct an infinite family of triangle non-equistable graphs within the class of complements of line graphs of bipartite graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Hardness Results for Approximate Pure Horn CNF Formulae Minimization

We study the hardness of approximation of clause minimum and literal minimum representations of pure Horn functions in $n$ Boolean variables. We show that unless P=NP, it is not possible to approximate in polynomial time the minimum number of clauses and the minimum number of literals of pure Horn CNF representations to within a factor of $2^{\log^{1-o(1)} n}$. This is the case even when the inputs are restricted to pure Horn 3-CNFs with $O(n^{1+\varepsilon})$ clauses, for some small positive constant $\varepsilon$. Furthermore, we show that even allowing sub-exponential time computation, it is still not possible to obtain constant factor approximations for such problems unless the Exponential Time Hypothesis turns out to be false.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Quadratization of Symmetric Pseudo-Boolean Functions

A pseudo-Boolean function is a real-valued function $f(x)=f(x_1,x_2,\ldots,x_n)$ of $n$ binary variables; that is, a mapping from $\{0,1\}^n$ to $\mathbb{R}$. For a pseudo-Boolean function $f(x)$ on $\{0,1\}^n$, we say that $g(x,y)$ is a quadratization of $f$ if $g(x,y)$ is a quadratic polynomial depending on $x$ and on $m$ auxiliary binary variables $y_1,y_2,\ldots,y_m$ such that $f(x)= \min \{g(x,y) : y \in \{0,1\}^m \}$ for all $x \in \{0,1\}^n$. By means of quadratizations, minimization of $f$ is reduced to minimization (over its extended set of variables) of the quadratic function $g(x,y)$. This is of some practical interest because minimization of quadratic functions has been thoroughly studied for the last few decades, and much progress has been made in solving such problems exactly or heuristically. A related paper \cite{ABCG} initiated a systematic study of the minimum number of auxiliary $y$-variables required in a quadratization of an arbitrary function $f$ (a natural question, since the complexity of minimizing the quadratic function $g(x,y)$ depends, among other factors, on the number of binary variables). In this paper, we determine more precisely the number of auxiliary variables required by quadratizations of symmetric pseudo-Boolean functions $f(x)$, those functions whose value depends only on the Hamming weight of the input $x$ (the number of variables equal to $1$).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On CIS Circulants

A circulant is a Cayley graph over a cyclic group. A well-covered graph is a graph in which all maximal stable sets are of the same size, or in other words, they are all maximum. A CIS graph is a graph in which every maximal stable set and every maximal clique intersect. It is not difficult to show that a circulant G is a CIS graph if and only if G and its complement are both well-covered and the product of the independence and the clique numbers of G is equal to the number of vertices. It is also easy to demonstrate that both families, the circulants and the CIS graphs, are closed with respect to the operations of taking the complement and lexicographic product. We study the structure of the CIS circulants. It is well-known that all P_4-free graphs are CIS. In this paper, in addition to the simple family of the P_4-free circulants, we construct a non-trivial sparse but infinite family of CIS circulants. We are not aware of any CIS circulant that could not be obtained from graphs in this family by the operations of taking the complement and lexicographic product.

0 citations0 reviewsNo code linkedOpen access