Computational Combinatorics Roundup: February 2013

by Derrick Stolee

In this month’s roundup, we have an article about computation in mathematics, and four research papers on wildly different problems.

Online Resources

Natalie Wolchover, In Computers We Trust? Simons Foundation.
Wolchover discusses a lot of different perspectives on using computers to do mathematics. She begins by discussing Doron Zeilberger’s work in devising algorithms to prove theorems (the Wilf-Zielberger method), usually combinatorial identities. There is also discussion of Hales’ proof of the Kepler Conjecture. The article is balanced in that it mentions several mathematicians with opinions against computers, and the points they bring up are not to be overlooked. Some day, I will carefully express my opinions on this subject.

Research Papers

Mohammadreza Jooyandeh, Brendan D. McKay, Patric R. J. Östergård, Ville H. Pettersson, Carol T. Zamfirescu, Planar Hypohamiltonian Graphs on 40 Vertices, arXiv:1302.2698 [math.CO]
A graph is hypohamiltonian if it is not Hamiltonian, but when any vertex is removed the graph becomes Hamiltonian. The smallest previously-known planar hypohamiltonian graphs are of order 42. The authors here present a computaitonal approach to find planar hypohamiltonian graphs, and discover 25 such graphs of order 40. They also extend known families by showing there exists a planar hypohamiltonian graph of order n for all n at least 42 (leaving a gap at 41). They also consider the case for deleting multiple vertices from a planar graph to result in a Hamiltonian graph. Their algorithm starts by using plantri to generate all planar graphs with a fixed number of faces, and all faces of length at least 5, then “inserts 4-faces into paths of length 2” to generate potential hypohamiltonian graphs. Hence, this method is not complete and the lower bound on a planar hypohamiltonian graph of order n remains as n \geq 18.

Stefan Kratsch, On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility, arXiv:1302.3496 [math.CO]
A kernel is an algorithm that shrinks an input problem to a smaller, equivalent problem. The author points out that CPLEX is well-known for its presolver that dramatically improves the standard algorithms for solving integer programs. This paper first proves that polynomial-time kernels cannot exist for the Integer Linear Programming Feasibility problem unless certain conjectures in computational complexity are false. (Such a kernel would drastically improve the search for certain combinatorial objects.) Kernels are demonstrated for covering and packing problems, provided the constraint matrix is sufficiently sparse. This paper is very theoretical, but may have some implementable contributions.

Stephen G. Hartke, Derrick Stolee, A Branch-and-Cut Strategy for the Manickam-Miklós-Singhi Conjecture, arXiv:1302.3636 [math.CO]
The Manickam-Miklós-Singhi Conjecture is a statement on the number of partial k-sums in a nonnegative sum of n real numbers. Previous efforts proved the conjecture for k \leq 3, an this work extends the known values to k \leq 7 using a linear programming formulation and a branching algorithm.

Ryan A. Rossi, David F. Gleich, Assefaw H. Gebremedhin, Md. Mostofa Ali Patwary, A Fast Parallel Maximum Clique Algorithm for Large Sparse Graphs and Temporal Strong Components, arXiv:1302.6256 [cs.SI]
Finding maximum cliques in graphs is a hard problem, but it is of interest to those studying large graphs, such as social networks. Such large graphs cannot be investigated using a single computer simply due to the size of the graph. This paper develops a parallel algorithm that appears to scale well on these types of sparse graphs.