New Width Parameters of Graphs
Doctoral thesis
Permanent lenke
https://hdl.handle.net/1956/6166Utgivelsesdato
2012-09-03Metadata
Vis full innførselSamlinger
Sammendrag
The main focus of this thesis is on using the divide and conquer technique to efficiently solve graph problems that are in general intractable. We work in the field of parameterized algorithms, using width parameters of graphs that indicate the complexity inherent in the structure of the input graph. We use the notion of branch decompositions of a set function introduced by Robertson and Seymour to define three new graph parameters, boolean-width, maximum matching-width (MM-width) and maximum induced matching-width (MIM-width). We compare these new graph width parameters to existing graph parameters by defining partial orders of width parameters. We focus on tree-width, branch-width, clique-width, module-width and rank-width, and include a Hasse diagram of these orders containing 32 graph parameters. We use the size of a maximum matching in a bipartite graph as a set function to define MM-width and show that MM-width never differs by more than a multiplicative factor 3 from tree-width. The main reason for introducing MM-width is that it simplifies the comparison between tree-width and parameters defined via branch decomposition of a set function. We use the logarithm of the number of maximal independent sets in a bipartite graph as set function to define boolean-width. We show that booleanwidth of a graph class is bounded if and only if rank-width is bounded, and show that the boolean-width of a graph can be as low as the logarithm of the rank-width of the graph. Given a decomposition of boolean-width k, we design FPT algorithms parameterized by k, for a large class of graph problems, whose runtime has a single exponential dependency in the boolean-width, i.e. O∗(2O(k2)). Moreover we solve Maximum Independent Set in time O∗(22k) and Minimum Dominating Set in time O∗(23k). These algorithms are in particular interesting in conjunction with the fact that many graph classes have boolean-width O(log(n)), e.g. interval graphs. MIM-width is defined using the size of a maximum induced matching in a bipartite graph as set function. The main reason to introduce MIM-width is that its value is lower than any of the other parameters, in particular MIMwidth is 1 on interval graphs, permutation graphs and convex graphs, and at most 2k on circular k-trapezoid graphs, k-polygon graphs, Dliworth k graphs and complements of k-degenerate graphs. We show that the FPT algorithms designed for boolean-width are XP algorithms when parameterized by MIMwidth, this shows that a large class of locally checkable vertex subset and vertex partitioning problems are polynomial time solvable on the mentioned graph classess with bounded MIM-width. We give exact algorithms to compute optimal decompositions for all the three new width parameters and report on the implementation of a heuristic for finding decompositions of low boolean-width.
Består av
Paper I: Boolean-width of graphs. Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle.Paper II: Graph Classes with Structured Neighborhoods and Algorithmic Applications. Remy Belmonte, Martin Vatshelle.
Paper III: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle.
Paper IV: Feedback Vertex Set on Graphs of Low Clique-width. Binh-Minh Bui-Xuan, Ondřej Suchý, Jan Arne Telle, Martin Vatshelle.
Paper V: Finding Good Decompositions for Dynamic Programming on Dense Graphs. Eivind Magnus Hvidevold, Sadia Sharmin, Jan Arne Telle, Martin Vatshelle.