Document

**Published in:** LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Given n subspaces of a finite-dimensional vector space over a fixed finite field F, we wish to find a "branch-decomposition" of these subspaces of width at most k, that is a subcubic tree T with n leaves mapped bijectively to the subspaces such that for every edge e of T, the sum of subspaces associated to the leaves in one component of T-e and the sum of subspaces associated to the leaves in the other component have the intersection of dimension at most k. This problem includes the problems of computing branch-width of F-represented matroids, rank-width of graphs, branch-width of hypergraphs, and carving-width of graphs.
We present a fixed-parameter algorithm to construct such a branch-decomposition of width at most k, if it exists, for input subspaces of a finite-dimensional vector space over F. Our algorithm is analogous to the algorithm of Bodlaender and Kloks (1996) on tree-width of graphs. To extend their framework to branch-decompositions of vector spaces, we developed highly generic tools for branch-decompositions on vector spaces. For this problem, a fixed-parameter algorithm was known due to Hlinený and Oum (2008). But their method is highly indirect. Their algorithm uses the non-trivial fact by Geelen et al. (2003) that the number of forbidden minors is finite and uses the algorithm of Hlinený (2006) on checking monadic second-order formulas on F-represented matroids of small branch-width. Our result does not depend on such a fact and is completely self-contained, and yet matches their asymptotic running time for each fixed k.

Jisu Jeong, Eun Jung Kim, and Sang-il Oum. Finding Branch-Decompositions of Matroids, Hypergraphs, and More. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jeong_et_al:LIPIcs.ICALP.2018.80, author = {Jeong, Jisu and Kim, Eun Jung and Oum, Sang-il}, title = {{Finding Branch-Decompositions of Matroids, Hypergraphs, and More}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {80:1--80:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.80}, URN = {urn:nbn:de:0030-drops-90849}, doi = {10.4230/LIPIcs.ICALP.2018.80}, annote = {Keywords: branch-width, rank-width, carving-width, fixed-parameter tractability} }

Document

**Published in:** LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

We give alternative definitions for maximum matching width, e.g., a graph G has mmw(G) <= k if and only if it is a subgraph of a chordal graph H and for every maximal clique X of H there exists A,B,C \subseteq X with A \cup B \cup C=X and |A|,|B|,|C| <= k such that any subset of X that is a minimal separator of H is a subset of either A, B or C. Treewidth and branchwidth have alternative definitions through intersections of subtrees, where treewidth focuses on nodes and branchwidth focuses on edges. We show that mm-width combines both aspects, focusing on nodes and on edges. Based on this we prove that given a graph G and a branch decomposition of mm-width k we can solve Dominating Set in time O^*(8^k), thereby beating O^*(3^{tw(G)}) whenever tw(G) > log_3(8) * k ~ 1.893 k. Note that mmw(G) <= tw(G)+1 <= 3 mmw(G) and these inequalities are tight. Given only the graph G and using the best known algorithms to find decompositions, maximum matching width will be better for solving Dominating Set whenever tw(G) > 1.549 * mmw(G).

Jisu Jeong, Sigve Hortemo Sæther, and Jan Arne Telle. Maximum Matching Width: New Characterizations and a Fast Algorithm for Dominating Set. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 212-223, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{jeong_et_al:LIPIcs.IPEC.2015.212, author = {Jeong, Jisu and S{\ae}ther, Sigve Hortemo and Telle, Jan Arne}, title = {{Maximum Matching Width: New Characterizations and a Fast Algorithm for Dominating Set}}, booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)}, pages = {212--223}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-92-7}, ISSN = {1868-8969}, year = {2015}, volume = {43}, editor = {Husfeldt, Thore and Kanj, Iyad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.212}, URN = {urn:nbn:de:0030-drops-55846}, doi = {10.4230/LIPIcs.IPEC.2015.212}, annote = {Keywords: FPT algorithms, treewidth, dominating set} }

Document

**Published in:** LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Linear rank-width is a graph width parameter, which is a variation of rank-width by restricting its tree to a caterpillar. As a corollary of known theorems, for each k, there is a finite set \mathcal{O}_k of graphs such that a graph G has linear rank-width at most k if and only if no vertex-minor of G is isomorphic to a graph in \mathcal{O}_k. However, no attempts have been made to bound the number of graphs in \mathcal{O}_k for k >= 2. We construct, for each k, 2^{\Omega(3^k)} pairwise locally non-equivalent graphs that are excluded vertex-minors for graphs of linear rank-width at most k.
Therefore the number of graphs in \mathcal{O}_k is at least double exponential.

Jisu Jeong, O-joung Kwon, and Sang-il Oum. Excluded vertex-minors for graphs of linear rank-width at most k.. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 221-232, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{jeong_et_al:LIPIcs.STACS.2013.221, author = {Jeong, Jisu and Kwon, O-joung and Oum, Sang-il}, title = {{Excluded vertex-minors for graphs of linear rank-width at most k.}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {221--232}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.221}, URN = {urn:nbn:de:0030-drops-39369}, doi = {10.4230/LIPIcs.STACS.2013.221}, annote = {Keywords: rank-width, linear rank-width, vertex-minor, well-quasi-ordering} }