Performance-Driven Layer Assignment by Integer Linear Programming and Path-Constrained Hypergraph Partitioning

Performance-driven physical layout design is becoming increasingly important for both high speed integrated circuits and printed circuit boards. This paper studies the problem of assigning wire segments into two layers so as to minimize the number of vias, while taking into account performance constraints such as layer preference and circuit timing. We show that using the Elmore delay model, three timing problems in synchronous digital circuits—the long path problem, the short path problem and the time skew problem—can be formulated as a set of linear inequalities. We use the model of signed hypergraph to represent two-layer routings and formulate the performance-driven optimum layer assignment problem as the path-constrained maximum balance problem in a signed hypergraph. Two solution methods are developed and implemented. First, an integer linear programming formulation is derived for finding exact solutions. Second, a local-search heuristic for hypergraph partitioning is extended to cope with path-inequality constraints. Experimental results on a set of layer-assignment benchmarks demonstrated that the path-constrained local-search heuristic achieves optimum or near-optimum solutions with several orders of magnitude faster than the integer linear programming approach.     

Computing minimum multiway cuts in hypergraphs

The hypergraph $k$-cut problem is the problem of finding a minimum capacity set of hyperedges whose removal divides a given hypergraph into at least $k$ connected components. We present an algorithm for this problem, that runs in strongly polynomial time if both $k$ and the maximum size of the hyperedges are constants. Our algorithm extends the algorithm proposed by Thorup (2008) for computing minimum $k$-cuts of graphs from greedy packings of spanning trees.     

The union of minimal hitting sets: Parameterized combinatorial bounds and counting

A k-hitting set in a hypergraph is a set of at most k vertices that intersects all hyperedges. We study the union of all inclusion-minimal k-hitting sets in hypergraphs of rank r (where the rank is the maximum size of hyperedges). We show that this union is relevant for certain combinatorial inference problems and give worst-case bounds on its size, depending on r and k. For r=2 our result is tight, and for each r3 we have an asymptotically optimal bound and make progress regarding the constant factor. The exact worst-case size for r3 remains an open problem. We also propose an algorithm for counting all k-hitting sets in hypergraphs of rank r. Its asymptotic runtime matches the best one known for the much more special problem of finding one k-hitting set. The results are used for efficient counting of k-hitting sets that contain any particular vertex.     

Lines in hypergraphs

One of the De Bruijn-Erd?s theorems deals with finite hypergraphs where every two vertices belong to precisely one hyperedge. It asserts that, except in the perverse case where a single hyperedge equals the whole vertex set, the number of hyperedges is at least the number of vertices and the two numbers are equal if and only if the hypergraph belongs to one of simply described families, near-pencils and finite projective planes. Chen and Chvátal proposed to define the line uv in a 3-uniform hypergraph as the set of vertices that consists of u, v, and all w such that {u;v;w} is a hyperedge. With this definition, the De Bruijn-Erd?s theorem is easily seen to be equivalent to the following statement: If no four vertices in a 3-uniform hypergraph carry two or three hyperedges, then, except in the perverse case where one of the lines equals the whole vertex set, the number of lines is at least the number of vertices and the two numbers are equal if and only if the hypergraph belongs to one of two simply described families. Our main result generalizes this statement by allowing any four vertices to carry three hyperedges (but keeping two forbidden): the conclusion remains the same except that a third simply described family, complements of Steiner triple systems, appears in the extremal case.     

Weakly union-free twofold triple systems

In this paper, we settle a problem of Frankl and Füredi, which is a special case of a problem of Erdös, determining the maximum number of hyperedges in a 3-uniform hypergraph in which no two pairs of distinct hyperedges have the same union. The extremal case corresponds to the existence of weakly union-free twofold triple systems, which is settled here with six definite and four possible exceptions. An application to group testing is also given.     

Asymptotic packing via a branching process

It is shown that under certain side conditions the natural random greedy algorithm almost always provides an asymptotically optimal packing of disjoint hyperedges from a hypergraph H.     

Clustering by hypergraphs and dimensionality of cluster systems

In the present paper we discuss a new clustering procedure in the case where instead of a single metric we have a family of metrics. In this case we can obtain a partially ordered graph of clusters which is not necessarily a tree. We discuss a structure of a hypergraph above this graph. We propose two definitions of dimension for hyperedges of this hypergraph and show that for the multidimensional p-adic case both dimensions are reduced to the number of p-adic parameters.We discuss the application of the hypergraph clustering procedure to the construction of phylogenetic graphs in biology. In this case the dimension of a hyperedge will describe the number of sources of genetic diversity.     

3一致完全超图的彩色哈密顿圈

假设c是一个小于1/1152的常数,证明：对于每个充分大的偶数n,如果一个具有n个顶点的3一致完全超图的边着色满足每种颜色出现的次数不超过[cn],那么必含有一个每条边颜色都不一样的彩色哈密顿圈。     

A note on the maximum size of Berge-C4-free hypergraphs

In this paper, we consider maximum possible value for the sum of cardinalities of hyperedges of a hypergraph without a Berge 4-cycle. We significantly improve the previous upper bound provided by Gerbner and Palmer. Furthermore, we provide a construction that slightly improves the previous lower bound.     

Using Homogeneous Weights for Approximating the Partial Cover Problem

In this paper we consider the natural generalizations of two fundamental problems, the Set-Cover problem and the Min-Knapsack problem. We are given a hypergraph, each vertex of which has a nonnegative weight, and each edge of which has a nonnegative length. For a given threshold , our objective is to find a subset of the vertices with minimum total cost, such that at least a length of of the edges is covered. This problem is called the partial set cover problem. We present an O(|V|² + |H|)-time, Δ_E-approximation algorithm for this problem, where Δ_E ≥ 2 is an upper bound on the edge cardinality of the hypergraph and |H| is the size of the hypergraph (i.e., the sum of all its edges cardinalities). The special case where Δ_E = 2 is called the partial vertex cover problem. For this problem a 2-approximation was previously known, however, the time complexity of our solution, i.e., O(|V|²), is a dramatic improvement.We show that if the weights are homogeneous (i.e., proportional to the potential coverage of the sets) then any minimal cover is a good approximation. Now, using the local-ratio technique, it is sufficient to repeatedly subtract a homogeneous weight function from the given weight function.     

Linear and quadratic programming approaches for the general graph partitioning problem

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.     

Efficiently Recognizing the P 4-Structure of Trees and of Bipartite Graphs Without Short Cycles

A 4-uniform hypergraph represents the P ₄-structure of a graph G if its hyperedges are the vertex sets of the P ₄'s in G. By using the weighted 2-section graph of the hypergraph we propose a simple efficient algorithm to decide whether a given 4-uniform hypergraph represents the P ₄-structure of a bipartite graph without 4-cycle and 6-cycle. For trees, our algorithm is different from that given by G. Ding and has a better running time namely O(n ²) where n is the number of vertices. Revised: February 18, 1998     

An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation

Given a finite set V, and a hypergraph H⊆2^V, the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618-628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time.More generally, we consider a monotone property π over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50-63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying π and all maximal subsets not satisfying π, for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties π.     

On packing and coloring hyperedges in a cycle

Given a hypergraph and k different colors, we study the problem of packing and coloring a subset of the hyperedges of the hypergraph as paths in a cycle such that the total profit of the hyperedges selected is maximized, where each physical link e_j on the cycle is used at most c_j times, each hyperedge h_i has its profit p_i and any two paths, each spanning all nodes of its corresponding hyperedge, must be assigned different colors if they share a common physical link. This new problem arises in optical communication networks, and it is called the Maximizing Profits when Packing and Coloring Hyperedges in a Cycle problem (MPPCHC).In this paper, we prove that the MPPCHC problem is NP-hard and then present an algorithm with approximation ratio 2 for this problem. For the special case where each hyperedge has the same profit 1 and each link e_j has same capacity k, we propose an algorithm with approximation ratio .     

A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.     

The poset of hypergraph quasirandomness

Chung and Graham began the systematic study of k‐uniform hypergraph quasirandom properties soon after the foundational results of Thomason and Chung‐Graham‐Wilson on quasirandom graphs. One feature that became apparent in the early work on k‐uniform hypergraph quasirandomness is that properties that are equivalent for graphs are not equivalent for hypergraphs, and thus hypergraphs enjoy a variety of inequivalent quasirandom properties. In the past two decades, there has been an intensive study of these disparate notions of quasirandomness for hypergraphs, and an open problem that has emerged is to determine the relationship between them. Our main result is to determine the poset of implications between these quasirandom properties. This answers a recent question of Chung and continues a project begun by Chung and Graham in their first paper on hypergraph quasirandomness in the early 1990's. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,762–800, 2015     

Embedding Factorizations for 3‐Uniform Hypergraphs

In this article, two results are obtained on a hypergraph embedding problem. The proof technique is itself of interest, being the first time amalgamations have been used to address the embedding of hypergraphs. The first result finds necessary and sufficient conditions for the embedding a hyperedge‐colored copy of the complete 3‐uniform hypergraph of order m, , into an r‐factorization of , providing that . The second result finds necessary and sufficient conditions for an embedding when not only are the colors of the hyperedges of given, but also the colors of all the “pieces” of hyperedges on these m vertices are prescribed (the “pieces” of hyperedges are eventually extended to hyperedges of size 3 in by adding new vertices to the hyperedges of size 1 and 2 during the embedding process). Both these results make progress toward settling an old question of Cameron on completing partial 1‐factorizations of hypergraphs. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 216–224, 2013     

On Steiner trees and minimum spanning trees in hypergraphs

The bottleneck of the state-of-the-art algorithms for geometric Steiner problems is usually the concatenation phase, where the prevailing approach treats the generated full Steiner trees as edges of a hypergraph and uses an LP-relaxation of the minimum spanning tree in hypergraph (MSTH) problem. We study this original and some new equivalent relaxations of this problem and clarify their relations to all classical relaxations of the Steiner problem. In an experimental study, an algorithm of ours which is designed for general graphs turns out to be an efficient alternative to the MSTH approach.