Inapproximability of the Tutte polynomial

The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: take as input a graph G, and output a value which is a good approximation to T(G;x,y). Jaeger et al. have completely mapped the complexity of exactly computing the Tutte polynomial. They have shown that this is #P-hard, except along the hyperbola (x-1)(y-1)=1 and at four special points. We are interested in determining for which points (x,y) there is a fully polynomial randomised approximation scheme (FPRAS) for T(G;x,y). Under the assumption RP≠NP, we prove that there is no FPRAS at (x,y) if (x,y) is in one of the half-planes x<-1 or y<-1 (excluding the easy-to-compute cases mentioned above). Two exceptions to this result are the half-line x<-1,y=1 (which is still open) and the portion of the hyperbola (x-1)(y-1)=2 corresponding to y<-1 which we show to be equivalent in difficulty to approximately counting perfect matchings. We give further intractability results for (x,y) in the vicinity of the origin. A corollary of our results is that, under the assumption RP≠NP, there is no FPRAS at the point (x,y)=(0,1-λ) when λ>2 is a positive integer. Thus, there is no FPRAS for counting nowhere-zero λ flows for λ>2. This is an interesting consequence of our work since the corresponding decision problem is in P for example for λ=6. Although our main concern is to distinguish regions of the Tutte plane that admit an FPRAS from those that do not, we also note that the latter regions exhibit different levels of intractability. At certain points (x,y), for example the integer points on the x-axis, or any point in the positive quadrant, there is a randomised approximation scheme for T(G;x,y) that runs in polynomial time using an oracle for an NP predicate. On the other hand, we identify a region of points (x,y) at which even approximating T(G;x,y) is as hard as #P.     

Checking If There Exists a Monotonic Function That Is Consistent with the Measurements: An Efficient Algorithm

In many problems in science and engineering ranging from astrophysics to geosciences to financial analysis, we know that a physical quantity y depends on the physical quantity x, i.e., y = f(x) for some function f(x), and we want to check whether this dependence is monotonic. Specifically, finitely many measurements of x_i and y = f(x) have been made, and we want to check whether the results of these measurements are consistent with the monotonicity of f(x). An efficient parallelizable algorithm is known for solving this problem when the values x_i are known precisely, while the values y_i are known with interval uncertainty. In this paper, we extend this algorithm to a more general (and more realistic) situation when both x_i and y_i are known with interval uncertainty.     

The kernel strategy and its use for the study of combinatory logic

Barendregt defines combinatory logic as an equational system satisfying the combinatorsS andK with ((Sx)y)z=(xz)(yz) and (Kx)y=x; the set consisting ofS andK provides abasis for all of combinatory logic. Rather than studying all of the logic, logicians often focus onfragments of the logic, subsets whose basis is obtained by replacingS orK or both by other combinators. In this article, we present a powerful new strategy, called thekernel strategy, for studying fragments in the context of questions concerned with fixed point properties. Interest in such properties rests in part with their relation to normal forms and paradoxes. We show how the kernel strategy was used to answer a number of open questions, offering abundant evidence that the availability of the kernel strategy marks a singular advance for automated reasoning. In all of our experiments with this strategy applied by an automated reasoning program, the rate of success has been impressively high and the CPU time to obtain the desired information startlingly small. For each fragment we study, we use the kernel strategy to attempt to determine whether the strong or the weak fixed point property holds. WhereA is a given fragment with basisB, the strong fixed point property holds forA if and only if there exists a combinatory such that, for all combinatorsx,yx=x(yx), wherey is expressed purely in terms of elements ofB. The weak fixed point property holds forA if and only if for all combinatorsx there exists a combinatory such thaty=xy, wherey is expressed purely in terms of the elements ofB and the combinatorx. Because the use of the kernel strategy is so effective in addressing questions focusing on either fixed point property, its formulation marks an important advance for combinatory logic. Perhaps of especial interest to logicians is an infinite class of infinite sets of tightly coupled fixed point combinators (presented here), whose unexpected discovery resulted directly from the application of the strategy by an automated reasoning program. We also offer various open questions for possible research and focus on an automated reasoning program and input files that may prove useful for such research.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

On the moore test for coupled equations

In this paper an improved Moore test for the coupled system:f(x, y)=0,g(x, y)=0 is described: x⁺ is calculated from x and y in a forward-substep, and we use x⁺ and y to compute y⁺ in a backward-substep. It is shown that, if x⁺ ? x, y⁺ ? y, then a solution of the coupled system (x*,y*) ∈ (x⁺, y⁺) exists. On this foundation, we prove convergence of a point iterative algorithm for solving coupled systems.     

A sufficient condition for pancyclic graphs

In 2005, Rahman and Kaykobad proved that if G is a connected graph of order n such that d(x)+d(y)+d(x,y)n+1 for each pair x, y of distinct nonadjacent vertices in G, where d(x,y) is the length of a shortest path between x and y in G, then G has a Hamiltonian path [Inform. Process. Lett. 94 (2005) 37–41]. In 2006 Li proved that if G is a 2-connected graph of order n3 such that d(x)+d(y)+d(x,y)n+2 for each pair x,y of nonadjacent vertices in G, then G is pancyclic or G=K_n/2,n/2 where n4 is an even integer [Inform. Process. Lett. 98 (2006) 159–161]. In this work we prove that if G is a 2-connected graph of order n such that d(x)+d(y)+d(x,y)n+1 for all pairs x, y of distinct nonadjacent vertices in G, then G is pancyclic or G belongs to one of four specified families of graphs.     

Inapproximability of the Tutte polynomial of a planar graph

The Tutte polynomial of a graph G is a two-variable polynomial T(G; x, y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: given as input a planar graph G, determine T(G; x, y). Vertigan completely mapped the complexity of exactly computing the Tutte polynomial of a planar graph. He showed that the problem can be solved in polynomial time if (x, y) is on the hyperbola H _q given by (x ? 1)(y ? 1) = q for q = 1 or q = 2 or if (x, y) is one of the two special points (x, y) = (?1, ?1) or (x, y) = (1, 1). Otherwise, the problem is #P-hard. In this paper, we consider the problem of approximating T(G; x, y), in the usual sense of “fully polynomial randomized approximation scheme” or FPRAS. Roughly speaking, an FPRAS is required to produce, in polynomial time and with high probability, an answer that has small relative error. Assuming that NP is different from RP, we show that there is no FPRAS for the Tutte polynomial in a large portion of the (x, y) plane. In particular, there is no FPRAS if x > 1, y < ?1 or if y > 1, x < ?1 or if x < 0, y < 0 and q > 5. Also, there is no FPRAS if x < 1, y < 1 and q = 3. For q > 5, our result is intriguing because it shows that there is no FPRAS at (x, y) =?(1 ? q/(1 + ε), ?ε) for any positive ε but it leaves open the limit point ε =?0, which corresponds to approximately counting q-colorings of a planar graph.     

Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes

A bipartite graph is bipancyclic if it contains a cycle of every even length from 4 to |V(G)| inclusive. It has been shown that Q_n is bipancyclic if and only if n?2. In this paper, we improve this result by showing that every edge of Q_n−E′ lies on a cycle of every even length from 4 to |V(G)| inclusive where E′ is a subset of E(Q_n) with |E′|?n−2. The result is proved to be optimal. To get this result, we also prove that there exists a path of length l joining any two different vertices x and y of Q_n when h(x,y)?l?|V(G)|−1 and l−h(x,y) is even where h(x,y) is the Hamming distance between x and y.     

Evolutionary multiobjective optimization using an outranking-based dominance generalization

One aspect that is often disregarded in the current research on evolutionary multiobjective optimization is the fact that the solution of a multiobjective optimization problem involves not only the search itself, but also a decision making process. Most current approaches concentrate on adapting an evolutionary algorithm to generate the Pareto frontier. In this work, we present a new idea to incorporate preferences into a multi-objective evolutionary algorithm (MOEA). We introduce a binary fuzzy preference relation that expresses the degree of truth of the predicate “x is at least as good as y”. On this basis, a strict preference relation with a reasonably high degree of credibility can be established on any population. An alternative x is not strictly outranked if and only if there does not exist an alternative y which is strictly preferred to x. It is easy to prove that the best solution is not strictly outranked. For validating our proposed approach, we used the non-dominated sorting genetic algorithm II (NSGA-II), but replacing Pareto dominance by the above non-outranked concept. So, we search for the non-strictly outranked frontier that is a subset of the Pareto frontier. In several instances of a nine-objective knapsack problem our proposal clearly outperforms the standard NSGA-II, achieving non-outranked solutions which are in an obviously privileged zone of the Pareto frontier.     

Polynomial time algorithms for sentences over number fields

We call a sentence if and only if ρ is logically equivalent to a sentence of the form xyψ(x, y), where ψ(x, y) is a quantifier free formula constructed with logical and arithmetical symbols. Now let be a sentence in conjunctive or disjunctive normal form. We show that given an arbitrary algebraic number field K there is a polynomial time algorithm to decide whether is true in K or not. We also show that ther are polynomial time algorithms to decide whether or not is true in every algebraic number field or every radical extension field of Q.     

Mining predecessor–successor rules from DAG data

Data mining extracts implicit, previously unknown, and potentially useful information from databases. Many approaches have been proposed to extract information, and one of the most important ones is finding association rules. Although a large amount of research has been devoted to this subject, none of it finds association rules from directed acyclic graph (DAG) data. Without such a mining method, the hidden knowledge, if any, cannot be discovered from the databases storing DAG data such as family genealogy profiles, product structures, XML documents, task precedence relations, and course structures. In this article, we define a new kind of association rule in DAG databases called the predecessor–successor rule, where a node x is a predecessor of another node y if we can find a path in DAG where x appears before y. The predecessor–successor rules enable us to observe how the characteristics of the predecessors influence the successors. An approach containing four stages is proposed to discover the predecessor–successor rules. © 2006 Wiley Periodicals, Inc. Int J Int Syst 21: 621–637, 2006.     

A new universal approximation result for fuzzy systems,which reflects CNF DNF duality

There are two main fuzzy system methodologies for translating expert rules into a logical formula: In Mamdani's methodology, we get a DNF formula (disjunction of conjunctions), and in a methodology which uses logical implications, we get, in effect, a CNF formula (conjunction of disjunctions). For both methodologies, universal approximation results have been proven which produce, for each approximated function f(x), two different approximating relations R_DNF(x, y) and R_CNF(x, y). Since, in fuzzy logic, there is a known relation F_CNF(x) ≤ F_DNF(x) between CNF and DNF forms of a propositional formula F, it is reasonable to expect that we would be able to prove the existence of approximations for which a similar relation R_CNF(x, y) ≤ R_DNF(x, y) holds. Such existence is proved in our paper. © 2002 Wiley Periodicals, Inc.     

The complete inclusion structure of leaf power classes

Let k≥2 be an integer and G=(V,E) be a finite simple graph. A tree T is a k-leaf root of G, if V is the set of leaves of T and, for any two distinct x,yV, the distance between x and y in T is at most k if and only if xyE. We say that G is a k-leaf power if there is a k-leaf root of G. The main result of this paper is that, for all 2≤k<k^′, the classes of k- and k^′-leaf powers are inclusion-incomparable, if and only if k^′≤2k−3 and k^′−k is an odd number. With this result, an open problem from the literature about the inclusion structure of these graph classes is solved completely. In addition, the intersection of the smallest pair of inclusion-incomparable classes is studied.     

Panconnectivity of Cartesian product graphs

A graph G of order n (≥2) is said to be panconnected if for each pair (x,y) of vertices of G there exists an xy-path of length ℓ for each ℓ such that d _G (x,y)≤ℓ≤n−1, where d _G (x,y) denotes the length of a shortest xy-path in G. In this paper, we consider the panconnectivity of Cartesian product graphs. As a consequence of our results, we prove that the n-dimensional generalized hypercube Q _n (k ₁,k ₂,…,k _n ) is panconnected if and only if k _i ≥3 (i=1,…,n), which generalizes a result of Hsieh et al. that the 3-ary n-cube Q³_nQ^{3}_{n} is panconnected.     

On a family of copulas constructed from the diagonal section

We characterize the class of copulas that can be constructed from the diagonal section by means of the functional equation C(x,y)+|x−y|=C(x∨y,x∨y), for all (x,y) in the unit square such that C(x,y)>0. Some statistical properties of this class are given.     

The panconnectivity and the pancycle-connectivity of the generalized base-<Emphasis Type="Italic">b</Emphasis> hypercube

The interconnection network considered in this paper is the generalized base-b hypercube that is an attractive variant of the well-known hypercube. The generalized base-b hypercube is superior to the hypercube in many criteria, such as diameter, connectivity, and fault diameter. In this paper, we study the panconnectivity and pancycle-connectivity of the generalized base-b hypercube. We show that a generalized base-b hypercube is panconnected for b≥3. That is, for each pair of distinct vertices x and y of the n-dimensional generalized base-b hypercube GH(b,n) and for any integer l, where Dist(x,y)≤l≤N−1, there exists a path of the length l joining x and y, where N is the order of the graph GH(b,n) and Dist(x,y) is the distance between x and y. We also show that a generalized base-b hypercube is pancycle-connected for b≥3. That is, every two distinct vertices x and y of the graph GH(b,n) are contained by a cycle of every length ranging from the length of the smallest cycle that contains x and y to N.     

Computational-Complexity of Arithmetical Sentences

Arithmetical sentences are the sentences containing usual logical symbols and arithmetical symbols +, ·, and constants of Z. An arithmetical sentence φ is called an sentence if and only if φ is logically equivalent to a sentence of the form x yψ(x, y) where ψ(x, y) is a quantifier free formula. It is shown that the decision problems of determining sentences true in N or Z, respectively, are co-NP-complete, whereas the decision problem of determining sentences true in Q is in P. Consequently, the decision problems of determining sentences true in N or Z, respectively, are NP-complete. Also, the decision problem of determining sentences true in Q is in P.     

Range Estimation Is NP-Hard for ε2 Accuracy and Feasible for ε2−δ

The basic problem of interval computations is: given a function f(x ₁,..., x _n) and n intervals [x _i, x _i], find the (interval) range yof the given function on the given intervals. It is known that even for quadratic polynomials f(x ₁,..., x _n), this problem is NP-hard. In this paper, following the advice of A. Neumaier, we analyze the complexity of asymptotic range estimation, when the bound on the width of the input intervals tends to 0. We show that for small c > 0, if we want to compute the range with an accuracy c ₂, then the problem is still NP-hard; on the other hand, for every > 0, there exists a feasible algorithm which asymptotically, estimates the range with an accuracy c ^2–.     

Vanquishing the XCB Question: The Methodological Discovery of the Last Shortest Single Axiom for the Equivalential Calculus

With the inclusion of an effective methodology, this article answers in detail a question that, for a quarter of a century, remained open despite intense study by various researchers. Is the formula XCB=e(x,e(e(e(x,y),e(z,y)),z)) a single axiom for the classical equivalential calculus when the rules of inference consist of detachment (modus ponens) and substitution Where the function e represents equivalence, this calculus can be axiomatized quite naturally with the formulas e(x,x), e(e(x,y),e(y,x)), and e(e(x,y),e(e(y,z),e(x,z))), which correspond to reflexivity, symmetry, and transitivity, respectively. (We note that e(x,x) is dependent on the other two axioms.) Heretofore, thirteen shortest single axioms for classical equivalence of length eleven had been discovered, and XCB was the only remaining formula of that length whose status was undetermined. To show that XCB is indeed such a single axiom, we focus on the rule of condensed detachment, a rule that captures detachment together with an appropriately general, but restricted, form of substitution. The proof we present in this paper consists of twenty-five applications of condensed detachment, completing with the deduction of transitivity followed by a deduction of symmetry. We also discuss some factors that may explain in part why XCB resisted relinquishing its treasure for so long. Our approach relied on diverse strategies applied by the automated reasoning program OTTER. Thus ends the search for shortest single axioms for the equivalential calculus.     

Automating Pólya Theory: The Computational Complexity of the Cycle Index Polynomial

In this paper we investigate the computational difficulty of evaluating and approximately evaluating Pólya′s cycle index polynomial. We start by investigating the difficulty of determining a particular coefficient of the cycle index polynomial. In particular, we consider the following problem, in which i is taken to be a fixed positive integer: Given a set of generators for a permutation group G whose degree, n, is a multiple of i, determine the coefficient of x^n/i_i in the cycle index polynomial of G. We show that this problem is #P-hard for every fixed i >1. Next, we consider the evaluation problem. Let y₁, y₂, ... stand for an arbitrary fixed sequence of non-negative real numbers. The cycle index evaluation problem that is associated with this sequence is the following: Given a set of generators for a degree n permutation group G, evaluate the cycle index polynomial of G at the point (y₁, ..., y_n). We show that if there exists an i such that y_i ≠ yⁱ₁ and y_i ≠ 0 then the evaluation problem associated with y₁, y₂, ..., is #P-hard. We observe that the evaluation problem is solvable in polynomial time if y_j = y^j₁ for every positive integer j and that it is solvable in polynomial time if y_j = 0 for every integer j >1. Finally, we consider the approximate evaluation problem. We show that it is NP-hard to approximately solve the evaluation problem if there exists an i such that y_i > yⁱ₁. Furthermore, we show that it is NP-hard to approximately solve the evaluation problem if y₁ = y₂ = ··· = y for some positive non-integer y. We derive some corollaries of our results which deal with the computational difficulty of counting equivalence classes of combinatorial structures.     

If we measure a number,we get an interval. What if we measure a function or an operator?

Assume that we measure a physical quantityx with a measuring device whose accuracy isδ (i.e., whose producers guarantee that the difference $x--\bar x$ between the actual valuex and the measured value $\bar x$ does not exceedδ). If the result of this measurement is $\bar x$ , then possible values ofx form an interval $[\bar x - \delta ,\bar x + \delta ]$ . Suppose now that we know that a physical quantityy is a function of the physical quantityx (in other words, we know thaty=f (x) for some functionf (x)), but we do not knowf. How to determinef? We can measure only finitely many values, with finite precision, so, after finitely many measurements, we get a set of possible functionsf(x). This set can be called afunction interval (function intervals were first analyzed by R. Moore himself). The situation can become even more complicated. For example, if we analyze how physical fields evolve, then in addition to functions, we must describeoperators, i.e., mappings that transform a function (current value $f(\bar x)$ of a physical field) into a function (predicted future value of this field). Again, since we can perform only finitely many measurements, at any moment of time, our measurement results are consistent with the whole bunch of different operators. So, at any moment of time, we have a set of operators; we can call it anoperator interval. One can apply different ideas to describe function intervals, operator intervals, etc. But it is desirable to develop a general formalism that would cover all these cases. In this paper, we propose and justify such a formalism.