# FPT Algorithms for Diverse Collections of Hitting Sets
## 1 Introduction
While Dr. \(\mathcal{O}\)'s story is admittedly a made-up one, the Vertex Cover problem is in fact used to model _conflict resolution_ in far more realistic settings. In each case, there is a _conflict graph_\(G\) whose vertices correspond to entities between which one wishes to avoid a conflict of some kind. There is an edge between two vertices in \(G\) if and only if they could be in conflict, and finding and deleting a smallest vertex cover of \(G\) yields a largest conflict-free subset of entities. We describe three examples to illustrate the versatility of this model. In each case, it is intuitively clear, just like in Dr. \(\mathcal{O}\)'s problem, that formulating the problem as Vertex Cover results in a lot of significant side information being thrown away, and that while finding a smallest vertex cover in the conflict graph will give a _valid_ solution, it may not really help in finding a _best_ solution, _or even a reasonably good solution_. We list some side information that is lost in the modeling process; the reader should find it easy to come up with any amount of other side information that would be of interest, in each case. * **Air traffic control. ** Conflict graphs are used in the design of decision support tools for aiding Air Traffic Controllers (ATCs) in preventing untoward incidents involving aircraft [2,3]. Each node in the graph \(G\) in this instance is an aircraft, and there is an edge between two nodes if the corresponding aircraft are at risk of interfering with each other. A vertex cover of \(G\) corresponds to a set of aircraft that can be issued _resolution commands_ which ask them to change course, such that afterwards there is no risk of interference. In a situation involving a large number of aircraft, it is unlikely that _every_ choice of ten aircraft to redirect is _equally_ desirable. For instance, in general, it is likely that (i) it is better to ask smaller aircraft to change course in preference to larger craft, and (ii) it is better to ask aircraft which are cruising to change course, in preference to those which are taking off or landing. * **Wireless spectrum allocation. ** Conflict graphs are a standard tool in figuring out how to distribute wireless frequency spectrum among a large set of wireless devices so that no two devices whose usage could potentially interfere with each other are allotted the same frequencies [4; 5]. Each node in \(G\) is a user, and there is an edge between two nodes if (i) the users request the same frequency, and (ii) their usage of the same frequency has the potential to cause interference. A vertex cover of \(G\) corresponds to a set of users whose requests can be denied, such that afterwards there is no risk of interference. When there is large collection of devices vying for spectrum, it is unlikely that _every_ choice of ten devices to deny the spectrum is _equally_ desirable. For instance, it is likely that denying the spectrum to a remote-controlled toy car on the ground is preferable to denying the spectrum to a drone in flight. * **Managing inconsistencies in database integration. ** A database constructed by integrating data from different data sources may end up being inconsistent (that is, violating specified integrity constraints) even if the constituent databases are individually consistent. Handling these inconsistencies is a major challenge in database integration, and conflict graphs are central to various approaches for restoring consistency [6; 7; 8; 9]. Each node in \(G\) is a database item, and there is an edge between two nodes if the two items together form an inconsistency. A vertex cover of \(G\) corresponds to a set of database items in whose _absence_ the database achieves consistency. In a database of large size, it is unlikely that all data are created equal; some database items are likely to be of better relevance or usefulness than others, and so it is unlikely that _every_ choice of ten items to delete is _equally_ desirable.