Generating partitions of a graph into a fixed number of minimum weight cuts

In this paper, we present an algorithm for the generation of all partitions of a graph G with positive edge weights into k mincuts. The algorithm is an enumeration procedure based on the cactus representation of the mincuts of G. We report computational results demonstrating the efficiency of the algorithm in practice and describe in more detail a specific application for generating cuts in branch-and-cut algorithms for the traveling salesman problem.     

Some results on Hu's conjecture concerning binary trees

Given n weights, w₁, w₂,…, w_n, such that 0?w₁?w₂???w₁, we examine a property of permutation π¹, where π¹=(w₁, w_n, w₂, w_n?1,…), concerning alphabetical binary trees.For each permutation π of these n weights, there is an optimal alphabetical binary tree corresponding to π, we denote it's cost by V(π). There is also an optimal almost uniform alphabetical binary tree, corresponding to π, we denote it's cost by V_u(π).This paper asserts that V_u(π¹)?V_u(π)?V(π) for all π. This is a preliminary result concerning the conjecture of T.C. Hu. Hu's conjecture is V(π¹)?V(π) for all π.     

The group marriage problem

Let G be a permutation group acting on [n]={1,…,n} and V={Vi:i=1,…,n} be a system of n subsets of [n]. When is there an element g∈G so that g(i)∈Vi for each i∈[n]? If such a g exists, we say that G has a G-marriage subject to V. An obvious necessary condition is the orbit condition: for any nonempty subset Y of [n], there is an element g∈G such that the image of Y under g is contained in _?y∈YVy. Keevash observed that the orbit condition is sufficient when G is the symmetric group Sn; this is in fact equivalent to the celebrated Hall's Marriage Theorem. We prove that the orbit condition is sufficient if and only if G is a direct product of symmetric groups. We extend the notion of orbit condition to that of k-orbit condition and prove that if G is the cyclic group Cn where n?4 or G acts 2-transitively on [n], then G satisfies the (n−1)-orbit condition subject to V if and only if G has a G-marriage subject to V.     

Balanced Graph Partitions

We prove that the set of vertices V, |V| = rk, of a connected graph G can be split into r subsets of the same cardinality in such a way that the distance between any vertex of G and any subset of the partition is at most r.     

Multi-neighborhood tabu search for the maximum weight clique problem

Given an undirected graph G=(V,E) with vertex set V={1,??,n} and edge set E?V×V. Let w:V??Z ⁺ be a weighting function that assigns to each vertex i??V a positive integer. The maximum weight clique problem (MWCP) is to determine a clique of maximum weight. This paper introduces a tabu search heuristic whose key features include a combined neighborhood and a dedicated tabu mechanism using a randomized restart strategy for diversification. The proposed algorithm is evaluated on a total of 136 benchmark instances from different sources (DIMACS, BHOSLIB and set packing). Computational results disclose that our new tabu search algorithm outperforms the leading algorithm for the maximum weight clique problem, and in addition rivals the performance of the best methods for the unweighted version of the problem without being specialized to exploit this problem class.     

Minimum 2-tuple dominating set of permutation graphs

For a fixed positive integer k, a k-tuple dominating set of a graph G=(V,E) is a subset D?V such that every vertex in V is dominated by at least k vertex in D. The k-tuple domination number γ _×k (G) is the minimum size of a k-tuple dominating set of G. The special case when k=1 is the usual domination. The case when k=2 was called double domination or 2-tuple domination. A 2-tuple dominating set D ₂ is said to be minimal if there does not exist any D′?D ₂ such that D′ is a 2-tuple dominating set of G. A 2-tuple dominating set D ₂, denoted by γ _×2(G), is said to be minimum, if it is minimal as well as it gives 2-tuple domination number. In this paper, we present an efficient algorithm to find a minimum 2-tuple dominating set on permutation graphs with n vertices which runs in O(n ²) time.     

An optimal greedy routing algorithm for triangulated polygons

In this paper, we prove that a triangulated polygon G admits a greedy embedding into an appropriate semi-metric space such that using an appropriate distance definition, for any two vertices u and w in G, a most virtual distance decreasing path is always a minimum-edge path between u and w. Therefore, our greedy routing algorithm is optimal. The greedy embedding of G can be obtained in linear time. To the best of our knowledge, this is the first optimal greedy routing algorithm for a nontrivial subcategory of graphs.     

Partition into cliques for cubic graphs: Planar case, complexity and approximation

Given a graph G=(V,E) and a positive integer k, the partition into cliques (pic) decision problem consists of deciding whether there exists a partition of V into k disjoint subsets V₁,V₂,…,V_k such that the subgraph induced by each part V_i is a complete subgraph (clique) of G. In this paper, we establish both the NP-completeness of pic for planar cubic graphs and the Max SNP-hardness of pic for cubic graphs. We present a deterministic polynomial time -approximation algorithm for finding clique partitions in maximum degree three graphs.     

An improved rounding method and semidefinite programming relaxation for graph partition

Given an undirected graph G=(V,E) with |V|=n and an integer k between 0 and n, the maximization graph partition (MAX-GP) problem is to determine a subset S⊂V of k nodes such that an objective function w(S) is maximized. The MAX-GP problem can be formulated as a binary quadratic program and it is NP-hard. Semidefinite programming (SDP) relaxations of such quadratic programs have been used to design approximation algorithms with guaranteed performance ratios for various MAX-GP problems. Based on several earlier results, we present an improved rounding method using an SDP relaxation, and establish improved approximation ratios for several MAX-GP problems, including Dense-Subgraph, Max-Cut, Max-Not-Cut, and Max-Vertex-Cover. Received: March 10, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Extending a function on a graph

Let G be a graph with vertex set V, and let h be a function mapping a subset U of V into the real numbers R. If ? is a function from V to R, we define δ (?) to be the sum of ∥?(b)? ?(a)∥ over all edges {a, b} of G. A best extension of h is such a function ? with ?(x) = h(x) for X ∈ U and minimum δ (?). We show that such a best extension exists and derive an algorithm for obtaining such an extension. We also show that if instead we minimise the sum of (?(b)??(a))², there is generally a unique best extension, obtainable by solving a system of linear equations.     

Vertex Set Partitions Preserving Conservativeness

Let G be an undirected graph and ={X₁, …, X_n} be a partition of V(G). Denote by G/ the graph which has vertex set {X₁, …, X_n}, edge set E, and is obtained from G by identifying vertices in each class X_i of the partition . Given a conservative graph (G, w), we study vertex set partitions preserving conservativeness, i.e., those for which (G/ , w) is also a conservative graph. We characterize the conservative graphs (G/ , w), where is a terminal partition of V(G) (a partition preserving conservativeness which is not a refinement of any other partition of this kind). We prove that many conservative graphs admit terminal partitions with some additional properties. The results obtained are then used in new unified short proofs for a co-NP characterization of Seymour graphs by A. A. Ageev, A. V. Kostochka, and Z. Szigeti (1997, J. Graph Theory34, 357–364), a theorem of E. Korach and M. Penn (1992, Math. Programming55, 183–191), a theorem of E. Korach (1994, J. Combin. Theory Ser. B62, 1–10), and a theorem of A. V. Kostochka (1994, in “Discrete Analysis and Operations Research. Mathematics and its Applications (A. D. Korshunov, Ed.), Vol. 355, pp. 109–123, Kluwer Academic, Dordrecht).     

Resolvability in circulant graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.     

On rectilinear duals for vertex-weighted plane graphs

Let G=(V,E) be a plane triangulated graph where each vertex is assigned a positive weight. A rectilinear dual of G is a partition of a rectangle into |V| simple rectilinear regions, one for each vertex, such that two regions are adjacent if and only if the corresponding vertices are connected by an edge in E. A rectilinear dual is called a cartogram if the area of each region is equal to the weight of the corresponding vertex. We show that every vertex-weighted plane triangulated graph G admits a cartogram of constant complexity, that is, a cartogram where the number of vertices of each region is constant. Furthermore, such a rectilinear cartogram can be constructed in O(nlogn) time where n=|V|.     

Finding minimum dominating cycles in permutation graphs

A dominating cycle for a graph G = (V, E) is a subset C of V which has the following properties: (i) the subgraph of G induced by C has a Hamiltonian cycle, and (ii) every vertex of V is adjacent to some vertex of C. In this paper, we develop an O(n²) algorithm for finding a minimum cardinality dominating cycle in a permutation graph. We also show that a minimum cardinality dominating cycle in a permutation graph always has an even number of vertices unless it is isomorphic to C₃.     

Critically indecomposable graphs

An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a₁,b₁),(a₂,b₂),…,(a_m,b_m) such that G(V−{a_j1,b_j1,…,a_jk,b_jk}) is also an X-critical graph for arbitrary set of indices {j₁,…,j_k}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x₁,y₁),…,(x_t,y_t) such that x_i,y_i∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G.     

A vertex incremental approach for maintaining chordality

For a chordal graph G=(V,E), we study the problem of whether a new vertex u∉V and a given set of edges between u and vertices in V can be added to G so that the resulting graph remains chordal. We show how to resolve this efficiently, and at the same time, if the answer is no, specify a maximal subset of the proposed edges that can be added along with u, or conversely, a minimal set of extra edges that can be added in addition to the given set, so that the resulting graph is chordal. In order to do this, we give a new characterization of chordal graphs and, for each potential new edge uv, a characterization of the set of edges incident to u that also must be added to G along with uv. We propose a data structure that can compute and add each such set in O(n) time. Based on these results, we present an algorithm that computes both a minimal triangulation and a maximal chordal subgraph of an arbitrary input graph in O(nm) time, using a totally new vertex incremental approach. In contrast to previous algorithms, our process is on-line in that each new vertex is added without reconsidering any choice made at previous steps, and without requiring any knowledge of the vertices that might be added subsequently.     

Representation of group elements as subsequence sums

Let G be a finite (additive written) abelian group of order n. Let w₁,…,w_n be integers coprime to n such that w₁+w₂+?+w_n≡0 (mod n). Let I be a set of cardinality 2n-1 and let ξ={x_i:i∈I} be a sequence of elements of G. Suppose that for every subgroup H of G and every a∈G, ξ contains at most terms in a+H.Then, for every y∈G, there is a subsequence {y₁,…,y_n} of ξ such that y=w₁y₁+?+w_ny_n.Our result implies some known generalizations of the Erd?s-Ginzburg-Ziv Theorem.     

Complexity results related to monophonic convexity

The study of monophonic convexity is based on the family of induced paths of a graph. The closure of a subset X of vertices, in this case, contains every vertex v such that v belongs to some induced path linking two vertices of X. Such a closure is called monophonic closure. Likewise, the convex hull of a subset is called monophonic convex hull. In this work we deal with the computational complexity of determining important convexity parameters, considered in the context of monophonic convexity. Given a graph G, we focus on three parameters: the size of a maximum proper convex subset of G (m-convexity number); the size of a minimum subset whose closure is equal to V(G) (monophonic number); and the size of a minimum subset whose convex hull is equal to V(G) (m-hull number). We prove that the decision problems corresponding to the m-convexity and monophonic numbers are NP-complete, and we describe a polynomial time algorithm for computing the m-hull number of an arbitrary graph.     

On approximation of max-vertex-cover

We consider the max-vertex-cover (MVC) problem, i.e., find k vertices from an undirected and edge-weighted graph G=(V,E), where |V|=n⩾k, such that the total edge weight covered by the k vertices is maximized. There is a 3/4-approximation algorithm for MVC, based on a linear programming relaxation. We show that the guaranteed ratio can be improved by a simple greedy algorithm for k>(3/4)n, and a simple randomized algorithm for k>(1/2)n. Furthermore, we study a semidefinite programming (SDP) relaxation based approximation algorithms for MVC. We show that, for a range of k, our SDP-based algorithm achieves the best performance guarantee among the four types of algorithms mentioned in this paper.     

Independence numbers of graphs-an extension of the Koenig-Egervary theorem

Let G be an arbitrary finite, undirected graph with no loops nor multiple edges. In this paper the inequality β₀?n ? β₁ is investigated where β₀ is the independence number of G, n is the number of vertices, and β₁ is the cardinality of a maximum edge matching. The class of graphs for which equality holds is characterized. A polynomially-bounded algorithm is given which tests an arbitrary graph G for equality, and computes a maximum independent set of vertices when equality holds. Equality is “prevented” by the existence of a blossom-pair-a subgraph generated by a certain subset m_i of edges from a maximum edge matching M for G. It is shown that β₀ = n ?β₁?|R| where R is a minimum set oof representatives of the family {m_i} of blossom pair-generating subsets of M. Finally, apolynomially-bonded algorithm is given which partitions an arbitrary graph G into subgraphs G₀, G₁,…, G_q such that $\text{β}{}_0\text{(G) =}\text{∑}\text{i=0}\text{q}\text{β}{}_0\text{(G}{}_{\mathrm{i}}\text{)}$. Moreover, if arbitrary maximum independent subsets of vertices S₁, S₂,…, S_q are known, then a polynomially-bounded algorithm computes a maximum independent set S₀ for G₀ such that S=∪{S_i; i=0, 1,hellip;,q} is a maximum independent subset for G.