Martin Fürer · arXiv (Cornell University) · 2015
Multi-clique-width is obtained by a simple modification in the definition of clique-width. It has the advantage of providing a natural extension of tree-width. Unlike clique-width, it does not explode exponentially compared to tree-width. Efficient algorithms based on multi-clique-width are still possible for interesting tasks like computing the independent set polynomial or testing $c$-colorability. In particular, $c$-colorability can be tested in time linear in $n$ and singly exponential in $c$ and the width $k$ of a given multi-$k$-expression. For these tasks, the running time as a function of the multi-clique-width is the same as the running time of the fastest known algorithm as a function of the clique-width. This results in an exponential speed-up for some graphs, if the corresponding graph generating expressions are given. The reason is that the multi-clique-width is never bigger, but is exponentially smaller than the clique-width for many graphs. This gap shows up when the tree-width is basically equal to the multi-clique width as well as when the tree-width is not bounded by any function of the clique-width.
Cited by 0Open access
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov et al. · ACM Transactions on Algorithms · 2018
M AX -C UT , E DGE D OMINATING S ET , G RAPH C OLORING , and H AMILTONIAN C YCLE on graphs of bounded clique-width have received significant attention as they can be formulated in MSO 2 (and, therefore, have linear-time algorithms on bounded treewidth graphs by the celebrated Courcelle’s theorem), but cannot be formulated in MSO 1 (which would have yielded linear-time algorithms on bounded clique-width graphs by a well-known theorem of Courcelle, Makowsky, and Rotics). Each of these problems can be solved in time g ( k ) n f ( k ) on graphs of clique-width k . Fomin et al. (2010) showed that the running times cannot be improved to g ( k ) n O (1) assuming W[1]≠FPT. However, this does not rule out non-trivial improvements to the exponent f ( k ) in the running times. In a follow-up paper, Fomin et al. (2014) improved the running times for E DGE D OMINATING S ET and M AX -C UT to n O ( k ) , and proved that these problems cannot be solved in time g ( k ) n o ( k ) unless ETH fails. Thus, prior to this work, E DGE D OMINATING S ET and M AX -C UT were known to have tight n Θ ( k ) algorithmic upper and lower bounds. In this article, we provide lower bounds for H AMILTONIAN C YCLE and G RAPH C OLORING . For H AMILTONIAN C YCLE , our lower bound g ( k ) n o ( k ) matches asymptotically the recent upper bound n O ( k ) due to Bergougnoux, Kanté, and Kwon (2017). As opposed to the asymptotically tight n Θ( k ) bounds for E DGE D OMINATING S ET , M AX -C UT , and H AMILTONIAN C YCLE , the G RAPH C OLORING problem has an upper bound of n O (2 k ) and a lower bound of merely n o (√ [4] k ) (implicit from the W[1]-hardness proof). In this article, we close the gap for G RAPH C OLORING by proving a lower bound of n 2 o ( k ) . This shows that G RAPH C OLORING behaves qualitatively different from the other three problems. To the best of our knowledge, G RAPH C OLORING is the first natural problem known to require exponential dependence on the parameter in the exponent of n .
Cited by 15
Bogdan Alecu, Mamadou Moustapha Kanté, Vadim Lozin et al. · Discrete Mathematics · 2020
Cited by 2
Sang‐il Oum, Paul Seymour · Journal of Combinatorial Theory Series B · 2006
Cited by 497
Sang‐il Oum · ACM Transactions on Algorithms · 2008
Rank-width was defined by Oum and Seymour [2006] to investigate clique-width. They constructed an algorithm that either outputs a rank-decomposition of width at most f ( k ) for some function f or confirms that rank-width is larger than k in time O (| V | 9 log | V |) for an input graph G = ( V , E ) and a fixed k . We develop three separate algorithms of this kind with faster running time. We construct an O (| V | 4 )-time algorithm with f ( k ) = 3 k + 1 by constructing a subroutine for the previous algorithm; we avoid generic algorithms minimizing submodular functions used by Oum and Seymour. Another one is an O (| V | 3 )-time algorithm with f ( k ) = 24 k , achieved by giving a reduction from graphs to binary matroids; then we use an approximation algorithm for matroid branch-width by Hliněný [2005]. Finally we construct an O (| V | 3 )-time algorithm with f ( k ) = 3 k − 1 by combining the ideas of the two previously cited papers.
Cited by 131
Onur Çağırıcı, Petr Hliněný, Filip Pokrývka et al. · Lecture notes in computer science · 2020
Cited by 0Open access
Pinar Heggernes, Daniel Meister, Charis Papadopoulos et al. · Discrete Applied Mathematics · 2016
Cited by 4
Pascal Koiran, See Profile, Klaus Meer et al. · 2016
Abstract. Starting point of our work is a previous paper by Flarup, Koiran, and Lyaudet [5]. There the expressive power of certain fami-lies of polynomials is investigated. Among other things it is shown that polynomials arising as permanents of bounded tree-width matrices have the same expressiveness as polynomials given via arithmetic formulas. A natural question is how expressive such restricted permanent polynomi-als are with respect to other graph-theoretic concepts for representing polynomials over a field K. One such is representing polynomials by for-mulas in conjunctive normal form. Here, a monomial occurs according to whether the exponent vector satisfies a given CNF formula or not. We can in a canonical way assign a graph to such a CNF formula and speak about the tree-width of the related CNF polynomial. In this paper we show that the expressiveness of CNF polynomials of bounded tree-width again gives precisely arithmetic formulas. We then study how far the approach of evaluating subclasses of permanents effi-
Cited by 0
Sigve Hortemo Sæther, Jan Arne Telle · Algorithmica · 2015
Cited by 12
Sigve Hortemo Sæther, Jan Arne Telle · Lecture notes in computer science · 2014
Cited by 7
Yann Strozecki · 2016
We define a width parameter for hypergraphs, which we call the decomposition-width. We provide an explicit family of hypergraphs of large decomposition-width and we prove that every MSO property can be checked in linear time for hypergraphs with bounded decomposition-width when their decomposition is given. Finally, the decomposition-width of a graph is proved to be bounded by twice its clique-width, which suggests that decomposition-width is a generalization of clique-width to relations of large or unbounded arity.
Cited by 0
Isolde Adler, Mamadou Moustapha Kanté · Theoretical Computer Science · 2015
Cited by 17
Wolfgang Espelage, Frank Gurski, Egon Wanke · Lecture notes in computer science · 2001
Cited by 7
Wolfgang Espelage, Frank Gurski, Egon Wanke · WORLD SCIENTIFIC eBooks · 2006
Cited by 0
Jean-Marie Vanherpe · HAL (Le Centre pour la Communication Scientifique Directe) · 2000
International audience
Cited by 0
Jean-Marie Vanherpe · Discrete Mathematics · 2003
Cited by 14
Marijn J. H. Heule, Stefan Szeider · Lecture notes in computer science · 2013
Cited by 6Open access
Frank Gurski, Egon Wanke · Discrete Mathematics · 2007
Cited by 33
Robert Brignall, Michal Opler, Vincent Vatter · arXiv (Cornell University) · 2026
A hereditary class of graphs has bounded clique-width if and only if its prime members do, but this lifting property fails for linear clique-width. We prove that a hereditary class has bounded linear clique-width if and only if its prime members do and it contains neither all quasi-threshold graphs nor all complements of quasi-threshold graphs. This generalizes a result of Brignall, Korpelainen, and Vatter, who established the result for cographs.
Cited by 0Open access
Vadim Lozin · ArXiv.org · 2007
The clique-width is known to be unbounded in the class of unit interval graphs. In this paper, we show that this is a minimal hereditary class of unbounded clique-width, i.e., in every hereditary subclass of unit interval graphs the clique-width is bounded by a constant.
Cited by 4Open access