In this paper we consider k-meet-semidistributive lattices and we are interested in the computation of the set-colored poset associated to an implicational base. The parameter k is of interest since for any finite lattice there exists an integer k for which is k-meet-semidistributive. When
they are known as meet-semidistributive lattices.
We first give a polynomial time algorithm to compute an implicational base of a k-meet-semidistributive lattice from its associated colored poset. In other words, for a fixed k, finding a minimal implicational base of a k-meet-semidistributive lattice L from a context (FCA literature) of L can be done not just in output-polynomial time (which is open in the general case) but in polynomial time in the size of the input. This result generalizes that in . Second, we derive an algorithm to compute a set-colored poset from an implicational base which is based on the enumeration of minimal transversals of a hypergraph and turns out to be in polynomial time for k-meet-semidistributive lattices , . Finally, we show that checking whether a given implicational base describes a k-meet-semidistributive lattice can be done in polynomial time.
For any integer k>2, we consider the following decision problem. Given a simple graph, does there exist a partition of its vertices into two disjoint sets such that every simple k-cycle of G contains vertices in both of these sets? This problem is NP-hard because it admits a polynomial reduction from NAE 3-SAT. We construct a reduction that is polynomial both in the length of the instance and in k, which answers a recent question of Karpinski.
The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle and Vertex k-colorability. In particular, we discover the first two boundary classes for the Hamiltonian cycle problem and prove that for any k > 3 there is a continuum of boundary classes for Vertex k-colorability.
We consider the problems of computing the maximal and the minimal non-empty suffixes of substrings of a longer text of length . n. For the minimal suffix problem we show that for every . τ, . 1≤τ≤logn, there exists a linear-space data structure with . O(τ) query time and . O(nlogn/τ) preprocessing time. As a sample application, we show that this data structure can be used to compute the Lyndon decomposition of any substring of the text in . O(kτ) time, where . k is the number of distinct factors in the decomposition. For the maximal suffix problem, we give a linear-space structure with . O(1) query time and . O(n) preprocessing time. In other words, we simultaneously achieve both the optimal query time and the optimal construction time. © 2015 Elsevier B.V.
Dualization of a monotone Boolean function on a finite lattice can be represented by transforming the set of its minimal 1 values to the set of its maximal 0 values. In this paper we consider finite lattices given by ordered sets of their meet and join irreducibles (i.e., as a concept lattice of a formal context). We show that in this case dualization is equivalent to the enumeration of so-called minimal hypotheses. In contrast to usual dualization setting, where a lattice is given by the ordered set of its elements, dualization in this case is shown to be impossible in output polynomial time unless P = NP. However, if the lattice is distributive, dualization is shown to be possible in subexponential time.
In statistical learning the excess risk of empirical risk minimization (ERM) is controlled by (COMPn(F)n)α, where n is a size of a learning sample, COMPn(F) is a complexity term associated with a given class F and α∈[12,1] interpolates between slow and fast learning rates. In this paper we introduce an alternative localization approach for binary classificationthat leads to a novel complexity measure: fixed points of the local empirical entropy. We show that this complexity measure gives a tight control over COMPn(F) in the upper bounds under bounded noise. Our results are accompanied by a minimax lower bound that involves the same quantity. In particular, we practically answer the question of optimality of ERM under bounded noise for general VC classes.
Weighted independent domination is an NP-hard graph problem, which remains computationally intractable in many restricted graph classes. In particular, the problem is NP-hard in the classes of sat-graphs and chordal graphs. We strengthen these results by showing that the problem is NP-hard in a proper subclass of the intersection of sat-graphs and chordal graphs. On the other hand, we identify two new classes of graphs where the problem admits polynomial-time solutions.
Octal games are a well-defined family of two-player games played on heaps of counters, in which the players remove alternately a certain number of counters from a heap, sometimes being allowed to split a heap into two nonempty heaps, until no counter can be removed anymore.
We extend the definition of octal games to play them on graphs: heaps are replaced by connected components and counters by vertices. Thus, playing an octal game on a path
is equivalent to playing the same octal game on a heap of n counters.
We study one of the simplest octal games, called 0.33, in which the players can remove one vertex or two adjacent vertices without disconnecting the graph. We study this game on trees and give a complete resolution of this game on subdivided stars and bistars.
Let G be a simple graph whose vertices are partitioned into two subsets, called ‘filled’ vertices and ‘empty’ vertices. A vertex v is said to be forced by a filled vertex u if v is a unique empty neighbor of u. If we can fill all the vertices of G by repeatedly filling the forced ones, then we call an initial set of filled vertices a forcing set. We discuss the so-called failed forcing number of a graph, which is the largest cardinality of a set which is not forcing. Answering the recent question of Ansill, Jacob, Penzellna, Saavedra, we prove that this quantity is NP-hard to compute. Our proof also works for a related graph invariant which is called the skew failed forcing number.
We consider a propositional language for describing parameterized ceteris paribus preferences over atomic conjunctions. Such preferences are only required to hold when the alternatives being compared agree on a specified subset of propositional variables. Regarding the expressivity of the language in question, we show that a parameterized preference statement is equivalent to a conjunction of an exponential number of classical, non-parameterized, ceteris paribus statements. Next, we present an inference system for parameterized statements and prove that the problem of checking the semantic consequence relation for such statements is coNP-complete. We propose an approach based on formal concept analysis to learning preferences from data by showing that ceteris paribus preferences valid in a particular model correspond to implications of a special formal context derived from this model. The computation of a complete preference set is then reducible to the computation of minimal hypergraph transversals. Finally, we adapt a polynomial-time algorithm for abduction using Horn clauses represented by their characteristic models to the problem of determining preferences over new alternatives from preferences over given alternatives (with ceteris paribus preferences as the underlying model).
The graph partitioning problem is to partition the vertex set of a graph into a number of nonempty subsets so that the total weight of edges connecting distinct subsets is minimized. Previous research requires the input of cardinalities of subsets or the number of subsets for equipartition. In this paper, the problem is formulated as a zero-one quadratic programming problem without the input of cardinalities. We also present three equivalent zero-one linear integer programming reformulations. Because of its importance in data biclustering, the bipartite graph partitioning is also studied. Several new methods to determine the number of subsets and the cardinalities are presented for practical applications. In addition, hierarchy partitioning and partitioning of bipartite graphs without reordering one vertex set, are studied.