Bergen Open Research Archive

New Width Parameters of Graphs

Bergen Open Research Archive

Show simple item record Vatshelle, Martin eng 2012-11-02T11:00:32Z 2012-11-02T11:00:32Z 2012-09-03 eng
dc.identifier.isbn 978-82-308-2098-8 (print version) eng
dc.description.abstract <p>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.</p><p>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.</p><p>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.</p><p>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.</p><p>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.</p> eng
dc.language.iso eng eng
dc.publisher The University of Bergen eng
dc.relation.haspart Paper I: Boolean-width of graphs. Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle. eng
dc.relation.haspart Paper II: Graph Classes with Structured Neighborhoods and Algorithmic Applications. Remy Belmonte, Martin Vatshelle. eng
dc.relation.haspart Paper III: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle. eng
dc.relation.haspart Paper IV: Feedback Vertex Set on Graphs of Low Clique-width. Binh-Minh Bui-Xuan, Ondřej Suchý, Jan Arne Telle, Martin Vatshelle. eng
dc.relation.haspart Paper V: Finding Good Decompositions for Dynamic Programming on Dense Graphs. Eivind Magnus Hvidevold, Sadia Sharmin, Jan Arne Telle, Martin Vatshelle. eng
dc.rights Copyright the author. All rights reserved eng
dc.title New Width Parameters of Graphs eng
dc.type Doctoral thesis eng

Files in this item


This item appears in the following Collection(s)

Show simple item record

Search BORA


My Account