Complexities of some interesting problems on spanning trees

This paper deals with the complexity issues of some new interesting spanning tree problems. Here we define some new spanning tree problems by imposing various constraints and restrictions on graph parameters and present relevant results. Also we introduce a new notion of “set version” of some decision problems having integer K<|V| as a parameter in the input instance, where we replace K by a set X⊆|V|. For example, the set version of Maximum Leaf Spanning Tree problem asks whether there exists a spanning tree in G that contains X as a subset of the leaf set. We raise the issue of whether the set versions of NP-complete problems are as hard as the original problems and prove that although in some cases the set versions are easier to solve, this is not necessarily true in general.     

Structural Gröbner Basis Detection

 We determine the computational complexity of deciding whether m polynomials in n variables have relatively prime leading terms with respect to some term order. This problem in NP-complete in general, but solvable in polynomial time in two different situations, when m is fixed and when n−m is fixed. Our new algorithm for the second case determines a candidate set of leading terms by solving a maximum matching problem. This reduces the problem to linear programming. Received: May 9, 1996; revised version: December 19, 1996     

High parallelism and a proof procedure I: Theoretical considerations

This paper presents the theoretical basis of a proof procedure, which allows a high degree of parallel processing. The theoretical method is based upon the works of Prawitz's improved proof procedure and Robinson's unification algorithm. The input to the method is a set of clauses (or alternatively, well-formed formulae). The output of the method is the solution to the problem, if it exists. To overcome the inefficiency of the theoretical approach, we outline the main steps of a practical proof procedure. Besides parallel processing, the proof procedure works with bit manipulation rather than symbol manipulation as found in most of the existing proof mechanisms.     

Optimal code parallelization using unimodular transformations

Lamport's parallelization algorithm (cf. [7]) is generalized to a broader class of loops, and the complexity of the transformation process has been estimated. It is shown that every loop can be parallelized using methods similar to those in [7]; moreover, they also have the property that all their inner loops are devoid of data dependencies, and so are fully parallelizable. Unfortunately, without restricting the nature of the loop to be parallelized, the negative solution to Hilbert's tenth problem (cf. [3]) can be applied to show that the parallelizing transformations are not computable. The class of affine loops was therefore introduced. This class is more general than that considered by Lamport, and it is shown that parallelizing transformations for affine loops are computable. In general, however, the complexity estimates for finding such loops suggest that the parallelization procedure will take longer than executing the original loop sequentially. It is further shown that, if the loop satisfies an additional, nondegeneracy condition, then the loop can be efficiently transformed.

Finally, although more generally applicable, these methods are best applied to vectorization problems.     

Maximizing pin alignment by pin permutations

The problem considered here is that of permuting the pins of modules in order to maximize the number of connections which can be achieved in the polysilicon level. Using a graph-theoretic formulation, the problem is shown to be equivalent to that of removing fewest edges in a certain graph to break all cycles. The problem is proved to be NP-complete. A heuristic based on branch-and-bound is proposed.     

Hardness results for covering arrays avoiding forbidden edges and error-locating arrays

Covering arrays avoiding forbidden edges (CAFEs) are used in testing applications (software, networks, circuits, drug interaction, material mixtures, etc.) where certain combinations of parameter values are forbidden. Danziger et al. (2009) [8] have studied this problem and shown some computational complexity results. Around the same time, Martinez et al. (2009) [19] defined and studied error-locating arrays (ELAs), which are closely related to CAFEs. Both papers left some computational complexity questions. In particular, these papers showed polynomial-time solvability of the existence of CAFEs and ELAs for binary alphabets (g=2), and the NP-hardness of these problems for g≥5. In this paper, we prove that optimizing CAFEs and ELAs is indeed NP-hard even when restricted to the case of binary alphabets, using a reduction from edge clique covers of graphs (ECCs). We also provide a hardness of approximation result. We explore important relationships between ECCs and CAFEs and give some new bounds for uniform ECCs and CAFEs.     

Error Compensation in Leaf Power Problems

The k-Leaf Power recognition problem is a particular case of graph power problems: For a given graph it asks whether there exists an unrooted tree—the k-leaf root—with leaves one-to-one labeled by the graph vertices and where the leaves have distance at most k iff their corresponding vertices in the graph are connected by an edge. Here we study "error correction" versions of k-Leaf Power recognition—that is, adding or deleting at most l edges to generate a graph that has a k-leaf root. We provide several NP-completeness results in this context, and we show that the NP-complete Closest 3-Leaf Power problem (the error correction version of 3-Leaf Power) is fixed-parameter tractable with respect to the number of edge modifications or vertex deletions in the given graph. Thus, we provide the seemingly first nontrivial positive algorithmic results in the field of error compensation for leaf power problems with k > 2. To this end, as a result of independent interest, we develop a forbidden subgraph characterization of graphs with 3-leaf roots.     

Generalizations of matched CNF formulas

A CNF formula is called matched if its associated bipartite graph (whose vertices are clauses and variables) has a matching that covers all clauses. Matched CNF formulas are satisfiable and can be recognized efficiently by matching algorithms. We generalize this concept and cover clauses by collections of bicliques (complete bipartite graphs). It turns out that such generalization indeed gives rise to larger classes of satisfiable CNF formulas which we term biclique satisfiable. We show, however, that the recognition of biclique satisfiable CNF formulas is NP-complete, and remains NP-hard if the size of bicliques is bounded. A satisfiable CNF formula is called var-satisfiable if it remains satisfiable under arbitrary replacement of literals by their complements. Var-satisfiable CNF formulas can be viewed as the best possible generalization of matched CNF formulas as every matched CNF formula and every biclique satisfiable CNF formula is var-satisfiable. We show that recognition of var-satisfiable CNF formulas is _P ² P-complete, answering a question posed by Kleine Büning and Zhao.     

Exact 3-satisfiability is decidable in time <Emphasis Type="Italic">O</Emphasis>(2<Superscript>0.16254<Emphasis Type="Italic">n</Emphasis></Superscript>)

Let F=C ₁C _m be a Boolean formula in conjunctive normal form over a set V of n propositional variables, s.t. each clause C _i contains at most three literals l over V. Solving the problem exact 3-satisfiability (X3SAT) for F means to decide whether there is a truth assignment setting exactly one literal in each clause of F to true (1). As is well known X3SAT is NP-complete [6]. By exploiting a perfect matching reduction we prove that X3SAT is deterministically decidable in time O(2^0.18674n ). Thereby we improve a result in [2,3] stating X3SATO(2^0.2072n ) and a bound of O(2^0.200002n ) for the corresponding enumeration problem #X3SAT stated in a preprint [1]. After that by a more involved deterministic case analysis we are able to show that X3SATO(2^0.16254n ).