Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs ?
Many NP-complete problems on planar graphs are fixed-parameter tractable: Recent theoretical work provided tree decomposition-based fixed-parameter algorithms exactly solving various parameterized problems on planar graphs, among others VERTEX COVER, in time O ( c k n ) . Here, c c is some constant depending on the graph problem to be solved, n n is the number of graph vertices, and k k is the problem parameter (for VERTEX COVER this is the size of the vertex cover). In this paper, we present an experimental study for such tree decomposition-based algorithms focusing on VERTEX COVER. We demonstrate that the tree decomposition-based approach provides a valuable way of exactly solving VERTEX COVER on planar graphs. Doing so, we also demonstrate the impressive power of the so-called Nemhauser/Trotter theorem which provides a VERTEX COVER-specific, extremely useful data reduction through polynomial time preprocessing. Altogether, this underpins the practical importance of the underlying theory.
vertex cover planar graphs fixed-parameter tractability algorithm engineering tree decomposition of graphs exact algorihms