Hard problems in graph theory
June 13th, 2006Despite my usual resistance to applied maths, yesterday’s BICS seminar sounded worthwhile, and turned out to be very good- Keith Briggs of BT gave a talk entitled Some practical experiences of hard graph problems. Graph Theory isn’t part of our syllabus, which seems a shame, as the concepts are simple- colouring, cliques etc. - but the questions difficult.
Much of the talk discussed the validity of results on infinite graphs when applied to smaller (and hence computationally feasible) ones: in particular, obtaining good bounds on clique and chromatic numbers. Towards the end, the reduction of graph problems to the satisfiability problem in propositional logic was mentioned. Obviously, the possibility of such reductions is a defining characteristic of NP-hard problems (and one I’ve recently been studying), but it’s good to see that this is of practical merit rather than simply theoretical interest.