Computational Combinatorics

Best Practices for Backtrack Search Algorithms

Almost every algorithm I implement these days is a combinatorial search, which is a fancy way of saying a backtrack search to find combinatorial objects. A recursive algorithm determines a set of choices to make, selects one, and deepens the search. After all options are exhausted, the algorithm steps “up” a level of the search tree and makes a different choice.

Today, I want to discuss a few patterns I have developed in order to make such a backtracking search very error-proof and to make development streamlined. These concepts are particularly helpful when using TreeSearch.
Read the rest of this entry »

Best Practices for Scientific Computing

The following tweet found its way into my Twitter newsfeed.

I thought it would be appropriate to take the advice found in this article and apply them specifically to computational combinatorics. In particular, they identify and outline eight best practices, which I will discuss individually. Further, during the discussion I will include how I apply (or will apply) these concepts during my own development process. Below, I have simply copied their “Summary of Best Practices”. You can investigate each item in more detail in the original article. I’ll add my own ideas under each main topic.

Caveat: I showed this paper to a software engineer (my wife) and she thought all of these items would be obvious to anyone with even a basic understanding of software engineering. However, as the original paper is written for biologists and this blog is written for mathematicians, I find it appropriate to cover these ideas.
Read the rest of this entry »

Finding Cliques and Independent Sets in Circulant Graphs

We recently discussed cliquer, a “fast” algorithm for finding and counting maximum cliques in a graph. Today, I would like to discuss a modification of this algorithm when applied to graphs that have a very restrictive form of symmetry. Specifically, we will discuss circulant graphs and interval subgraphs of distance graphs. These graphs are particularly important for discovering the independence ratio of distance graphs, as discussed in the recently submitted paper, On the independence ratio of distance graphs with James Carraher, David Galvin, Stephen Hartke, and Jamie Radcliffe.

All code and data discussed is available at the distance graph page.
Read the rest of this entry »

Finding and Counting Cliques with cliquer

For a graph G, a clique is a set S \subseteq V(G) such that all pairs of vertices in S are adjacent in G. Determining the maximum size of a clique in a graph is a classic NP-Complete problem, but sometimes you just need to find or count cliques anyway.

Today, we discuss the cliquer algorithm, as designed by Niskanen and Östergård. Their very efficient implementation is available on their cliquer homepage. The entire implementation is very succinct and can be used as a library. In fact, Sage uses cliquer for its backend for clique algorithms. The main algorithm computes the maximum (weighted) clique and also can count maximum or maximal (weighted) cliques. We focus on the unweighted case.
Read the rest of this entry »

Updates to the Manickam-Miklós-Singhi Conjecture

It has been a busy year for the Manickam-Miklós-Singhi Conjecture. (See the earlier post on this topic for the important definitions.) Several new papers have appeared online or on the arXiv. Here is a brief discussion of these recent developments (organized by time of submission, as far as I can tell).
Read the rest of this entry »

Introduction to the Nullstellensatz/Linear Algebra Method

We have spent a lot of time discussing how to generate objects, but in order for us to generate them they must exist! This idea of showing existence versus non-existence is central to the computational complexity classes of NP and coNP: the difference is whether you use an existential quantifier or a universal quantifier. So, nonexistence problems can be phrased as “All objects do not have this property” and are not suited well to proof by certificate. We can demonstrate existence by finding and presenting the object, but nonexistence is harder to prove.

Today, we discuss Computing Infeasibility Certificates for Combinatorial Problems through Hilbert’s Nullstellensatz by Jesús A. De Loera, Jon Lee, Peter N. Malkin, and Susan Margulies, where they develop what I will call the Nullstellensatz/Linear Algebra Method, or NulLA for short. Their method starts with a set of polynomials whose common roots correspond to the goal object and they build a Nullstellensatz certificate that demonstrates that a set of polynomials have no common root. The certificate is built by solving a set of linear equations. This method is greatly improved by using symmetry to reduce the size of the linear system. The authors’ main idea is to use these certificates to prove certain graphs are not 3-colorable, but I believe this can be used to prove nonexistence of combinatorial objects.
Read the rest of this entry »

Spring Happenings

It has been a month and a half since my last post, which was not intentional. However, there are a couple pretty good reasons why.

1. The semester came to a close, and together my two classes had six exams (midterms, make-ups, and finals) in a span of three weeks.

2. My wife and I accepted tenure-track jobs at Iowa State University and have been working hard making plans for the move this summer.

Thanks for your patience and I hope to be back on topic very soon.

Computational Combinatorics Roundup: March 2013

I was thinking that this month was lacking any new computational combinatorics papers, but then three papers arrived in my feed within a couple days of each other, followed by several others to finish out the month. Read on to learn about them, and as always send me an email whenever you see a relevant research article or news story.
Read the rest of this entry »

3-Uniform Friendship Hypergraphs

A very brief welcome to EXCILL2 participants. Thanks for visiting!

Today we discuss On a question of Sós about 3-uniform friendship hypergraphs by Hartke and Vandenbussche. These authors presented several new examples of friendship hypergraphs exhibiting a property that was not known to be possible. Their method applies careful use of integer programming as a black box. First, a careful construction of an integer linear program discovered some examples (and non-existence of examples) for small orders. Then, by making some symmetry assumptions, they constructed some larger integer programs that found larger examples, hinting towards an infinite family. The existence of larger examples remains open, although Lia, van Reesa, Seoa, and Singhi recently proved some structure theorems that apply to the examples found by Hartke and Vandenbussche.
Read the rest of this entry »

A Branch-and-Cut Strategy for the Manickam-Miklós-Singhi Conjecture

Stephen Hartke and I recently uploaded our paper, A Branch-and-Cut Strategy for the Manickam-Miklós-Singhi Conjecture to the arXiv. We build a computational method to verify a conjecture involving the number of nonnegative k-sums in a nonnegative sum of n real numbers. With this method, we proved a stronger statement than the conjecture for all k\leq 7 and formed a stronger conjecture.

The method makes use of linear programming techniques and software, so begins our discussion of linear and integer programming methods. Read on to discover the method and also to figure out what is going on with the picture below.
MMS-Layers5
Read the rest of this entry »