The Alcuin Number of a Graph and Its Connections to the Vertex Cover Number
Péter Csorba|Caj Cor Hurkens|Gerhard J. Woeginger
We consider a planning problem that generalizes Alcuin's river crossing to scenarios with arbitrary conflict graphs. This generalization leads the so-called Alcuin number of underlying graph. derive variety combinatorial, structural, algorithmical, and complexity theoretical results around number. Our technical main result is an NP-certificate for It turns out graph closely related size minimum vertex cover in graph, we unravel several surprising connections between these two parameters. provide hardness fixed parameter tractability computing Furthermore demonstrate chordal graphs, bipartite planar graphs substantially easier analyze than general
Siam Review