### Subexponential parameterized algorithms on bounded-genus graphs and $\textit{H}-minor-free$ graphsSubexponential parameterized algorithms on bounded-genus graphs and $\textit{H}-minor-free$ graphs

Access Restriction
Subscribed

 Author Demaine, Erik D. ♦ Fomin, Fedor V. ♦ Hajiaghayi, Mohammadtaghi ♦ Thilikos, Dimitrios M. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2005 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword (k,r)-center ♦ Domination ♦ Fixed-parameter algorithms ♦ Map graph ♦ Planar graph Abstract We introduce a new framework for designing fixed-parameter algorithms with subexponential running $time---2^{O(&kradic;)}$ $n^{O(1)}.$ Our results apply to a broad family of graph problems, called bidimensional problems, which includes many domination and problems such as vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, disk dimension, and many others restricted to bounded-genus graphs (phrased as bipartite-graph problem). Furthermore, it is fairly straightforward to prove that a problem is bidimensional. In particular, our framework includes, as special cases, all previously known problems to have such subexponential algorithms. Previously, these algorithms applied to planar graphs, single-crossing-minor-free graphs, and/or map graphs; we extend these results to apply to bounded-genus graphs as well. In a parallel development of combinatorial results, we establish an upper bound on the treewidth (or branchwidth) of a bounded-genus graph that excludes some planar graph $\textit{H}$ as a minor. This bound depends linearly on the size $\textit{¦V(H)¦}$ of the excluded graph $\textit{H}$ and the genus $\textit{g(G)}$ of the graph $\textit{G},$ and applies and extends the graph-minors work of Robertson and Seymour.Building on these results, we develop subexponential fixed-parameter algorithms for dominating set, vertex cover, and set cover in any class of graphs excluding a fixed graph $\textit{H}$ as a minor. In particular, this general category of graphs includes planar graphs, bounded-genus graphs, single-crossing-minor-free graphs, and any class of graphs that is closed under taking minors. Specifically, the running time is $2^{O(&kracic;)}$ $n^{h},$ where $\textit{h}$ is a constant depending only on $\textit{H},$ which is polynomial for $\textit{k}$ = $O(log^{2}$ $\textit{n}).$ We introduce a general approach for developing algorithms on $\textit{H}-minor-free$ graphs, based on structural results about $\textit{H}-minor-free$ graphs at the heart of Robertson and Seymour's graph-minors work. We believe this approach opens the way to further development on problems in $\textit{H}-minor-free$ graphs. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2005-11-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 52 Issue Number 6 Page Count 28 Starting Page 866 Ending Page 893

#### Open content in new tab

Source: ACM Digital Library