dc.contributor |
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
dc.contributor.author |
Nishimura, Naomi |
dc.contributor.author |
Ragde, Prabhakar |
dc.contributor.author |
Thilikos Touloupas, Dimitrios |
dc.date |
2001-09 |
dc.identifier.citation |
Nishimura, N., Ragde, P., Thilikos, D. "Fast fixed-parameter tractable algorithms for (nontrivial) generalizations of vertex cover". 2001. |
dc.identifier.uri |
http://hdl.handle.net/2117/97846 |
dc.language.iso |
eng |
dc.relation |
LSI-01-39-R |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.subject |
Àrees temàtiques de la UPC::Informàtica::Aplicacions de la informàtica |
dc.subject |
Fast algorithms |
dc.subject |
Graphs class recognition |
dc.subject |
Graphs minors |
dc.subject |
Vertex covers |
dc.subject |
Obstructions |
dc.title |
Fast fixed-parameter tractable algorithms for (nontrivial) generalizations of vertex cover |
dc.type |
info:eu-repo/semantics/publishedVersion |
dc.type |
info:eu-repo/semantics/report |
dc.description.abstract |
Our goal in this paper is the development of fast algorithms for recognizing general classes of graphs. We seek algorithms whose complexity can be expressed as a linear function of the graph size plus an exponential function of k, a natural parameter describing the class. In particular, we consider the class W_k(G), where for each graph G in W_k(G), the removal of a set of at most k vertices from G results in a graph in the base graph class G. (If G is the class of edgeless graphs,
W_k(G) is the class of graphs with bounded vertex cover.)
When G is a minor-closed class such that each graph in G has bounded maximum degree, and all obstructions of G (minor-minimal graphs outside G) are connected, we obtain an O((g+k)|V(G)|+(fk)^k) recognition algorithm for W_k(G), where g and f are constants (modest and quantified) depending on the class G. If G is the class of graphs
with maximum degree bounded by D (not closed under minors),
we can still obtain a running time of O(|V(G)|(D+k)+k(D+k)^{k+3}) for recognition of graphs in W_k(G).
Our results are obtained by considering minor-closed classes for which
all obstructions are connected graphs, and showing that the size of any obstruction for W_k(G) is O(tk^7+t^7k^2), where t is a bound on the size of obstructions for G. A trivial corollary of this result is an upper bound of (k+1)(k+2) on the number of vertices in any obstruction of the class of graphs with vertex cover of size at most k. These results are of independent graph-theoretic interest. |