An algorithm and upper bounds for the weighted maximal planar graph problem

In this paper, we investigate the weighted maximal planar graph (WMPG) problem. Given a complete, edge-weighted, simple graph, the WMPG problem involves finding a subgraph with the highest sum of edge weights that is maximal planar, namely, it can be embedded in the plane without any of its edges intersecting, and no additional edge can be added to the subgraph without violating its planarity. We present a new integer linear programming (ILP) model for this problem. We then develop a cutting-plane algorithm to solve the WMPG problem based on the proposed ILP model. This algorithm enables the problem to be solved more efficiently than previously reported algorithms. New upper bounds are also provided, which are useful in evaluating the quality of heuristic solutions or in generating initial solutions for meta-heuristics. Computational results are reported for a set of 417 test instances of size varying from 6 to 100 nodes including 105 instances from the literature and 312 randomly generated instances. The computational results indicate that instances with up to 24 nodes can be solved optimally in reasonable computational time and the new upper bounds for larger instances significantly improve existing upper bounds.     

A 1-tough nonhamiltonian maximal planar graph

We construct a maxima' planar graph which is 1-tough but nonhamiltonian. The graph is an answer to Chvátal's question on the existence of such a graph.     

Integer programming formulations for the minimum weighted maximal matching problem

Given an undirected graph, the problem of finding a maximal matching that has minimum total weight is NP-hard. This problem has been studied extensively from a graph theoretical point of view. Most of the existing literature considers the problem in some restricted classes of graphs and give polynomial time exact or approximation algorithms. On the contrary, we consider the problem on general graphs and approach it from an optimization point of view. In this paper, we develop integer programming formulations for the minimum weighted maximal matching problem and analyze their efficacy on randomly generated graphs. We also compare solutions found by a greedy approximation algorithm, which is based on the literature, against optimal solutions. Our results show that our integer programming formulations are able to solve medium size instances to optimality and suggest further research for improvement.     

Semidefinite programming relaxations for graph coloring and maximal clique problems

The semidefinite programming formulation of the Lovász theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number χ(G) or the clique number ω(G) of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either χ(G) or ω(G) by adding several types of cutting planes. We explore several such strengthenings, and show that some of them can be computed with the same effort as the theta number. We also investigate computational simplifications for graphs with rich automorphism groups. Partial support by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438, is gratefully acknowledged.     

Maximum andk-th maximal spanning trees of a weighted graph

LetA be a maximum spanning tree andP be an arbitrary spanning tree of a connected weighted graphG. Then we prove that there exists a bijectionψ fromA/P intoP/A such that for any edgea∈A/P, (P/ψ(a)) ∪a is a spanning tree ofG whose weight is greater than or equal to that ofP. We apply this theorem to some problems concerning spanning trees of a weighted graph.     

On the number of hamiltonian cycles in a maximal planar graph

We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on p vertices. In particular, we construct a p-vertex maximal planar graph containing exactly four Hamiltonian cycles for every p ≥ 12. We also prove that every 4-connected maximal planar graph on p vertices contains at least p/(log₂ p) Hamiltonian cycles.     

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.     

Linear programming for weighted deviation problems using compact basis techniques

Weighted deviation problems are linear programs in which weights (or penalties) are attached to deviations from upper and lower bounds on particular linear expressions. In turn the deviations may be bracketed by secondary bounds. These problems include statistical problems of minimizing weighted sums of absolute deviations, standard and extended “goal programming” problems, problems with upper bounds on absolute values of linear affine functions, problems with arbitrarily bounded variables, and combinations of these.Previous specialized linear programming methods for related problems have been restricted to specialized cases that involve only a single basis configuration, or else, by means of “extended GUB” techniques, accommodate a diverse variety of basis structures at the cost of substantially increased computation. We show that, of the several basis configurations that can arise for this problem, precisely three are essential. Special rules are identified to allow transitions between these three structures, to yield valid compact versions of both the primal and the dual simplex methods. Finally, we show how these results lead to improved efficiency as well as reduced problem size.     

Each maximal planar graph with exactly two separating triangles is Hamiltonian

A classical result of Whitney states that each maximal planar graph without separating triangles is Hamiltonian, where a separating triangle is a triangle whose removal separates the graph. Chen [Any maximal planar graph with only one separating triangle is Hamiltonian J. Combin. Optim. 7 (2003) 79-86] proved that any maximal planar graph with only one separating triangle is still Hamiltonian. In this paper, it is shown that the conclusion of Whitney's Theorem still holds if there are exactly two separating triangles.     

On the number of cycles of length 4 in a maximal planar graph

Let p and C₄ (G) be the number of vertices and the number of 4-cycles of a maximal planar graph G, respectively. Hakimi and Schmeichel characterized those graphs G for which C₄ (G) = 1/2(p² + 3p - 22). This characterization is correct if p ≥ 9. However, for p = 7 or 8, there is exactly one other graph which violates the theorem in the sense that the upper bound of C₄ (G) is also attained.     

On the number of cycles of length k in a maximal planar graph

Let G be a maximal planar graph with p vertices, and let C_k(G) denote the number of cycles of length k in G. We first present tight bounds for C₃(G) and C₄(G) in terms of p. We then give bounds for C_k(G) when 5 ≤ k ≤ p, and consider in particular bounds for C_p(G), in terms of p. Some conjectures and unsolved problems are stated.     

An upper bound on the length of a Hamiltonian walk of a maximal planar graph

A Hamiltonian walk of a connected graph is a shortest closed walk that passes through every vertex at least once, and the length of a Hamiltonian walk is the total number of edges traversed by the walk. We show that every maximal planar graph with p(≥ 3) vertices has a Hamiltonian cycle or a Hamiltonian walk of length ≤ 3(p - 3)/2.     

Sharp weighted inequalities for the vector-valued maximal function

We prove in this paper some sharp weighted inequalities for the vector-valued maximal function of Fefferman and Stein defined by

where is the Hardy-Littlewood maximal function. As a consequence we derive the main result establishing that in the range there exists a constant such that

Furthermore the result is sharp since cannot be replaced by . We also show the following endpoint estimate

where is a constant independent of .

     

On the tightness conditions for maximal planar graphs

We characterize the tight structure of a vertex-accumulation-free maximal planar graph with no separating triangles. Together with the result of Halin who gave an equivalent form for such graphs, this yields that a tight structure always exists in every 4-connected maximal planar graph with one end.     

A characterization of some weighted inequalities for the vector-valued weighted maximal function

We give in this paper a necessary and sufficient condition of weighted weak and strong type norm inequalities for the vector-valued weighted maximal function.     

Linear programming based algorithms for preemptive and non-preemptive RCPSP

In this paper, the RCPSP (resource constrained project scheduling problem) is solved using a linear programming model. Each activity may or may not be preemptive. Each variable is associated to a subset of independent activities (antichains). The properties of the model are first investigated. In particular, conditions are given that allow a solution of the linear program to be a feasible schedule. From these properties, an algorithm based on neighbourhood search is derived. One neighbour solution is obtained through one Simplex pivoting, if this pivoting preserves feasibility. Methods to get out of local minima are provided. The solving methods are tested on the PSPLIB instances in a preemptive setting and prove efficient. They are used when preemption is forbidden with less success, and this difference is discussed.     

Linear programming based decomposition methods for inventory distribution systems

We consider an inventory distribution system consisting of one warehouse and multiple retailers. The retailers face random demand and are supplied by the warehouse. The warehouse replenishes its stock from an external supplier. The objective is to minimize the total expected replenishment, holding and backlogging cost over a finite planning horizon. The problem can be formulated as a dynamic program, but this dynamic program is difficult to solve due to its high dimensional state variable. It has been observed in the earlier literature that if the warehouse is allowed to ship negative quantities to the retailers, then the problem decomposes by the locations. One way to exploit this observation is to relax the constraints that ensure the nonnegativity of the shipments to the retailers by associating Lagrange multipliers with them, which naturally raises the question of how to choose a good set of Lagrange multipliers. In this paper, we propose efficient methods that choose a good set of Lagrange multipliers by solving linear programming approximations to the inventory distribution problem. Computational experiments indicate that the inventory replenishment policies obtained by our approach can outperform several standard benchmarks by significant margins.     

Unprovability threshold for the planar graph minor theorem

This note is part of the implementation of a programme in foundations of mathematics to find exact threshold versions of all mathematical unprovability results known so far, a programme initiated by Weiermann. Here we find the exact versions of unprovability of the finite graph minor theorem with growth rate condition restricted to planar graphs, connected planar graphs and graphs embeddable into a given surface, assuming an unproved conjecture (*): ‘there is a number a>0 such that for all k≥3, and all n≥1, the proportion of connected graphs among unlabelled planar graphs of size n omitting the k-element circle as minor is greater than a’. Let γ be the unlabelled planar growth constant (27.2269≤γ<30.061). Let P(c) be the following first-order arithmetical statement with real parameter c: “for every K there is N such that whenever G₁,G₂,…,G_N are unlabelled planar graphs with |G_i|<K+c⋅log₂i then for some i<j≤N, G_i is isomorphic to a minor of G_j”. Then

1.

for every , P(c) is provable in IΔ₀+exp;

2.

for every , P(c) is unprovable in .

We also give proofs of some upper and lower bounds for unprovability thresholds in the general case of the finite graph minor theorem.     

Sharp weighted logarithmic bound for maximal operators

The paper contains the study of sharp weighted logarithmic estimates for maximal operators on probability spaces equipped with a tree-like structure. These inequalities can be regarded as LlogL versions of the classical estimates of Fefferman and Stein. The proof exploits the existence of a certain special function, enjoying appropriate majorization and concavity conditions.