An effective multilevel tabu search approach for balanced graph partitioning

Graph partitioning is one of the fundamental NP-complete problems which is widely applied in many domains, such as VLSI design, image segmentation, data mining, etc. Given a graph G=(V,E), the balanced k-partitioning problem consists in partitioning the vertex set V into k disjoint subsets of about the same size, such that the number of cutting edges is minimized. In this paper, we present a multilevel algorithm for balanced partition, which integrates a powerful refinement procedure based on tabu search with periodic perturbations. Experimental evaluations on a wide collection of benchmark graphs show that the proposed approach not only competes very favorably with the two well-known partitioning packages METIS and CHACO, but also improves more than two thirds of the best balanced partitions ever reported in the literature.     

Maximum concurrent flows and minimum cuts

In many applications, we need to find a minimum cost partition of a network separating a given pair of nodes. A classical example is the Max-Flow Min-Cut Theorem, where the cost of the partition is defined to be the sum of capacities of arcs connecting the two parts. Other similar concepts such as minimum weighted sparsest cut and flux cut have also been introduced. There is always a cost associated with a cut, and we always seek the min-cost cut separating a given pair of nodes. A natural generalization from the separation of a given pair is to find all minimum cost cuts separating all \(\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array} } \right)\) pairs of nodes, with arbitrary costs associated with all 2^n?1 — 1 cuts. In the present paper, we show thatn — 1 minimum cost cuts are always sufficient to separate all \(\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array} } \right)\) pairs of nodes. A further generalization is to considerk-way partitions rather than two-way partitions. An interesting relationship exists betweenk-way partitions, the multicommodity flow problem, and the minimum weighted sparsest cut. Namely, if the staturated arcs in a multicommodity flow problem form ak-way partition (k ≤ 4), then thek-way partition contains a two-way partition. This two-way partition is the minimum weight sparsest cut.     

Graphs with maximum degree 6 are acyclically 11-colorable

An acyclic k-coloring of a graph G is a proper vertex coloring of G, which uses at most k colors, such that the graph induced by the union of every two color classes is a forest. In this note, we prove that every graph with maximum degree six is acyclically 11-colorable, thus improving the main result of Yadav et al. (2009) [11].     

On the oriented chromatic number of grids

In this paper, we focus on the oriented coloring of graphs. Oriented coloring is a coloring of the vertices of an oriented graph G without symmetric arcs such that (i) no two neighbors in G are assigned the same color, and (ii) if two vertices u and v such that (u,v)∈A(G) are assigned colors c(u) and c(v), then for any (z,t)∈A(G), we cannot have simultaneously c(z)=c(v) and c(t)=c(u). The oriented chromatic number of an unoriented graph G is the smallest number k of colors for which any of the orientations of G can be colored with k colors.The main results we obtain in this paper are bounds on the oriented chromatic number of particular families of planar graphs, namely 2-dimensional grids, fat trees and fat fat trees.     

Some results on acyclic edge coloring of plane graphs

An acyclic edge coloring of a graph is a proper edge coloring without bichromatic cycles. The acyclic chromatic index of a graph G, denoted by α^′(G), is the minimum number k such that G admits an acyclic edge coloring using k colors. Let G be a plane graph with maximum degree Δ and girth g. In this paper, we prove that α^′(G)=Δ(G) if one of the following conditions holds: (1) Δ?8 and g?7; (2) Δ?6 and g?8; (3) Δ?5 and g?9; (4) Δ?4 and g?10; (5) Δ?3 and g?14. We also improve slightly a result of A. Fiedorowicz et al. (2008) [7] by showing that every triangle-free plane graph admits an acyclic edge coloring using at most Δ(G)+5 colors.     

On constructing an optimal consensus clustering from multiple clusterings

Computing a suitable measure of consensus among several clusterings on the same data is an important problem that arises in several areas such as computational biology and data mining. In this paper, we formalize a set-theoretic model for computing such a similarity measure. Roughly speaking, in this model we have k>1 partitions (clusters) of the same data set each containing the same number of sets and the goal is to align the sets in each partition to minimize a similarity measure. For k=2, a polynomial-time solution was proposed by Gusfield (Information Processing Letters 82 (2002) 159-164). In this paper, we show that the problem is MAX-SNP-hard for k=3 even if each partition in each cluster contains no more than 2 elements and provide a -approximation algorithm for the problem for any k.     

Multiset rewriting over Fibonacci and Tribonacci numbers

We show how techniques from the formal logic, can be applied directly to the problems studied completely independently in the world of combinatorics, the theory of integer partitions. We characterize equinumerous partition ideals in terms of the minimal elements generating the complementary order filters. Here we apply a general rewriting methodology to the case of filters having overlapping minimal elements. In addition to a ‘bijective proof ’ for Zeckendorf-like theorems – that every positive integer is uniquely representable within the Fibonacci, Tribonacci and k-Bonacci numeration systems, we establish ‘bijective proofs’ for a new series of partition identities related to Fibonacci, Tribonacci and k-step Fibonacci numbers. The main result is proved with the help of a multiset rewriting system such that the system itself and the system consisting of its reverse rewriting rules, both have the Church–Rosser property, which provides an explicit bijection between partitions of two different types (represented by the two normal forms).     

Multilevelk-way Partitioning Scheme for Irregular Graphs

In this paper, we present and study a class of graph partitioning algorithms that reduces the size of the graph by collapsing vertices and edges, we find ak-way partitioning of the smaller graph, and then we uncoarsen and refine it to construct ak-way partitioning for the original graph. These algorithms compute ak-way partitioning of a graphG= (V,E) inO(|E|) time, which is faster by a factor ofO(logk) than previously proposed multilevel recursive bisection algorithms. A key contribution of our work is in finding a high-quality and computationally inexpensive refinement algorithm that can improve upon an initialk-way partitioning. We also study the effectiveness of the overall scheme for a variety of coarsening schemes. We present experimental results on a large number of graphs arising in various domains including finite element methods, linear programming, VLSI, and transportation. Our experiments show that this new scheme produces partitions that are of comparable or better quality than those produced by the multilevel bisection algorithm and requires substantially smaller time. Graphs containing up to 450,000 vertices and 3,300,000 edges can be partitioned in 256 domains in less than 40 s on a workstation such as SGI's Challenge. Compared with the widely used multilevel spectral bisection algorithm, our new algorithm is usually two orders of magnitude faster and produces partitions with substantially smaller edge-cut.     

On edge covering colorings of graphs

An edge covering coloring of a graph G is an edge-coloring of G such that each color appears at each vertex at least one time. The maximum integer k such that G has an edge covering coloring with k colors is called the edge covering chromatic index of G and denoted by . It is known that for any graph G with minimum degree δ(G), it holds that . Based on the subgraph of G induced by the vertices of minimum degree, we find a new sufficient condition for a graph G to satisfy . This result substantially extends a result of Wang et al. in 2006.     

On the k-tuple domination of generalized de Brujin and Kautz digraphs

A vertex u in a digraph G = (V, A) is said to dominate itself and vertices v such that (u, v) ∈ A. For a positive integer k, a k-tuple dominating set of G is a subset D of vertices such that every vertex in G is dominated by at least k vertices in D. The k-tuple domination number of G is the minimum cardinality of a k-tuple dominating set of G. This paper deals with the k-tuple domination problem on generalized de Bruijn and Kautz digraphs. We establish bounds on the k-tuple domination number for the generalized de Bruijn and Kautz digraphs and we obtain some conditions for the k-tuple domination number attaining the bounds.     

Block-graph width

Let G be a class of graphs. A graph G has G-width k if there are k independent sets N₁,…,N_k in G such that G can be embedded into a graph H∈G such that for every edge e in H which is not an edge in G, there exists an i such that both endvertices of e are in N_i. For the class B of block graphs we show that graphs with B-width at most 4 are perfect. We also show that B-width is NP-complete and show that it is fixed-parameter tractable. For the class C of complete graphs, similar results are also obtained.     

A k-server problem with parallel requests and unit distances

In this paper we consider k-server problems with parallel requests where several servers can also be located on one point. We will distinguish the surplus-situation where the request can be completely fulfilled by means of the k servers and the scarcity-situation where the request cannot be completely met. We use the method of the potential function by Bartal and Grove [2] in order to prove that a corresponding Harmonic algorithm is competitive for the more general k-server problem in the case of unit distances. For this purpose we partition the set of points in relation to the online and offline servers? positions and then use detailed considerations related to sets of certain partitions.     

Comparison of initial partitioning methods for multilevel direct k-way graph partitioning with fixed vertices

In scientific computing, load balancing is a crucial step conditioning the performance of large-scale applications. In this case, an efficient decomposition of the workload to a number of processors is highly necessary. A common approach to solve this problem is to use graph representation and perform a graph partitioning in k-parts using the multilevel framework and the recursive bisection (RB) paradigm. However, in graph instances where fixed vertices are used to model additional constraints, RB often produces partitions of poor quality.In this paper, we investigate the difficulties of RB to handle fixed vertices and we compare its results with two different alternatives. The first one, called kgggp is a direct k-way greedy graph growing partitioning that properly handles fixed vertices while the second one, introduced in kPaToH, uses RB and a post-processing technique to correct the obtained partition. Finally, experimental results on graphs that represent real-life numerical simulations show that both alternative methods provide improved partitions compared to RB.     

Occupancy Problems with Pairwise Exclusion Constraints—An Aspect of Gait Enumeration

Abstract

Occupancy problems generally relate to ordered partitions of a set of objects. Often such partitions are subject to constraints which prevent certain types of objects from being placed in the same block of the partition. This paper is addressed to a particular problem of this type in which pairwise exclusion constraints are imposed. Specifically, what is sought is an enumeration of all possible partitions of a set of k pairs of objects such that no partition block contains two elements from the same pair. The results obtained are generally in the form of recursion relations. These relations have been solved completely for k ≤ 4 and partially for larger values of k. Numerical results are presented in the form of tables. An application of these tables to an enumeration of the theoretically possible gaits of bipeds, tripeds, and quadrupeds concludes the paper. It is found that the total number of such gaits is somewhat larger than previously suspected.     

On the Grundy and b-Chromatic Numbers of a Graph

The Grundy number of a graph G, denoted by Γ(G), is the largest k such that G has a greedy k-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertexes of G. The b-chromatic number of a graph G, denoted by χ _b (G), is the largest k such that G has a b-colouring with k colours, that is a colouring in which each colour class contains a b-vertex, a vertex with neighbours in all other colour classes. Trivially χ _b (G),Γ(G)≤Δ(G)+1. In this paper, we show that deciding if Γ(G)≤Δ(G) is NP-complete even for a bipartite graph G. We then show that deciding if Γ(G)≥|V(G)|?k or if χ _b (G)≥|V(G)|?k are fixed parameter tractable problems with respect to the parameter k.     

The Parameterized Complexity of Stabbing Rectangles

The NP-complete geometric covering problem Rectangle Stabbing is defined as follows: Given a set R of axis-parallel rectangles in the plane, a set L of horizontal and vertical lines in the plane, and a positive integer k, select at most k of the lines such that every rectangle is intersected by at least one of the selected lines. While it is known that the problem can be approximated in polynomial time within a factor of two, its parameterized complexity with respect to the parameter k was open so far. Giving two fixed-parameter reductions, one from the W[1]-complete problem Multicolored Clique and one to the W[1]-complete problem Short Turing Machine Acceptance, we prove that Rectangle Stabbing is W[1]-complete with respect to the parameter k, which in particular means that there is no hope for an algorithm running in f(k)?|R∪L| ^O(1) time. Our reductions also show the W[1]-completeness of the more general problem Set Cover on instances that “almost have the consecutive-ones property”, that is, on instances whose matrix representation has at most two blocks of 1s per row. We also show that the special case of Rectangle Stabbing where all rectangles are squares of the same size is W[1]-hard. The case where the input consists of non-overlapping rectangles was open for some time and has recently been shown to be fixed-parameter tractable (Heggernes et al., Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009). By giving an algorithm running in (2k) ^k ?|R∪L| ^O(1) time, we show that Rectangle Stabbing is fixed-parameter tractable in the still NP-hard case where both these restrictions apply, that is, in the case of disjoint squares of the same size. This algorithm is faster than the one in Heggernes et al. (Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009) for the disjoint rectangles case. Moreover, we show fixed-parameter tractability for the restrictions where the rectangles have bounded width or height or where each horizontal line intersects only a bounded number of rectangles.     

An algorithm for computing simple k-factors

A k-factor of graph G is defined as a k-regular spanning subgraph of G. For instance, a 2-factor of G is a set of cycles that span G. 2-factors have multiple applications in Graph Theory, Computer Graphics, and Computational Geometry. We define a simple 2-factor as a 2-factor without degenerate cycles. In general, simple k-factors are defined as k-regular spanning subgraphs where no edge is used more than once. We propose a new algorithm for computing simple k-factors for all values of k?2.     

Compatibility of t-norms with the concept of ?-partition

In this paper we study the behaviour of a kind of partitions formed by fuzzy sets, the ?-partitions, with respect to three important operations: refinement, union and product of partitions. In the crisp set theory, the previous operations lead to new partitions: every refinement of a partition is also a partition; the union of partitions of disjoint sets is a partition of the union set; the product of two partitions of two sets is a partition of the intersection of the partitioned sets. It has been proven that ?-partitions extend the three previous properties when the intersection of fuzzy sets is defined by the minimum t-norm and the union by the maximum t-conorm. In this paper we consider any t-norm defining the intersection of fuzzy sets and we characterize those t-norms for which refinements, unions and products of ?-partitions are ?-partitions. We pay special attention to these characterizations in the case of continuous t-norms.