research-article

Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs

Authors:

Guillaume Ducoffe,

Alexandru PopaAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 15, Issue 3

Article No.: 33, Pages 1 - 57

https://doi.org/10.1145/3310228

Published: 07 June 2019 Publication History

Abstract

Recently, hardness results for problems in P were achieved using reasonable complexity-theoretic assumptions such as the Strong Exponential Time Hypothesis. According to these assumptions, many graph-theoretic problems do not admit truly subquadratic algorithms. A central technique used to tackle the difficulty of the above-mentioned problems is fixed-parameter algorithms with polynomial dependency in the fixed parameter (P-FPT). Applying this technique to clique-width, an important graph parameter, remained to be done.

In this article, we study several graph-theoretic problems for which hardness results exist such as cycle problems, distance problems, and maximum matching. We give hardness results and P-FPT algorithms, using clique-width and some of its upper bounds as parameters. We believe that our most important result is an algorithm in O(k⁴ ⋅ n + m)-time for computing a maximum matching, where k is either the modular-width of the graph or the P₄-sparseness. The latter generalizes many algorithms that have been introduced so far for specific subclasses such as cographs. Our algorithms are based on preprocessing methods using modular decomposition and split decomposition. Thus they can also be generalized to some graph classes with unbounded clique-width.

References

[1]

Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. 2015. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’15). SIAM, Philadelphia, PA, 1681--1697.

Digital Library

[2]

Amir Abboud and Virginia Vassilevska Williams. 2014. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS’14). IEEE, 434--443.

Digital Library

[3]

Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. 2016. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’16). SIAM, 377--391.

Digital Library

[4]

Martin Aigner and Michael Fromme. 1984. A game of cops and robbers. Discr. Appl. Math. 8, 1 (1984), 1--12.

[5]

Luitpold Babel. 1998. Tree-like P<sub>4</sub>-connected graphs. Discr. Math. 191, 1--3 (1998), 13--23.

Digital Library

[6]

Luitpold Babel. 2000. Recognition and isomorphism of tree-like P<sub>4</sub>-connected graphs. Discr. Appl. Math. 99, 1 (2000), 295--315.

Digital Library

[7]

Luitpold Babel and Stephan Olariu. 1998. On the structure of graphs with few P<sub>4</sub>’s. Discr. Appl. Math. 84, 1--3 (1998), 1--13.

Digital Library

[8]

Luitpold Babel and Stephan Olariu. 1999. On the p-connectedness of graphs—A survey. Discr. Appl. Math. 95, 1--3 (1999), 11--33.

[9]

Hans-Jürgen Bandelt and Henry Martyn Mulder. 1986. Distance-hereditary graphs. J. Combin. Theor. B 41, 2 (1986), 182--208.

Digital Library

[10]

Stefan Baumann. 1996. A Linear Algorithm for the Homogeneous Decomposition of Graphs. Technical Report M-9615. Zentrum Mathematik, Technische Universität München. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.7643.

[11]

Matthias Bentert, Till Fluschnik, André Nichterlein, and Rolf Niedermeier. 2017. Parameterized aspects of triangle enumeration. In Proceedings of the International Symposium on Fundamentals of Computation Theory (FCT’17), Lecture Notes in Computer Science, Vol. 10472. Springer, 96--110.

[12]

Claude Berge. 1957. Two theorems in graph theory. Proc. Natl. Acad. Sci. U.S.A. 43, 9 (1957), 842--844.

[13]

Hans L. Bodlaender. 1998. A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1 (1998), 1--45.

Digital Library

[14]

Hans L. Bodlaender. 2006. Treewidth: Characterizations, applications, and computations. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG’06), Lecture Notes in Computer Science, Vol. 4271. Springer, 1--14.

Digital Library

[15]

Hans L. Bodlaender and Arie M. C. A. Koster. 2006. Safe separators for treewidth. Discr. Math. 306, 3 (2006), 337--350.

Digital Library

[16]

John Adrian Bondy and Uppaluri Siva Ramachandra Murty. 2008. Graph Theory. Graduate Texts in Mathematics, Vol. 244. Springer-Verlag, London.

Digital Library

[17]

Michele Borassi, David Coudert, Pierluigi Crescenzi, and Andrea Marino. 2015. On computing the hyperbolicity of real-world graphs. In Proceedings of the European Symposia on Algorithms (ESA’15). Lecture Notes in Computer Science, Vol. 9294. Springer, 215--226.

[18]

Michele Borassi, Pierluigi Crescenzi, and Michel Habib. 2016. Into the square: On the complexity of some quadratic-time solvable problems. Electr. Not. Theor. Comput. Sci. 322 (2016), 51--67.

Digital Library

[19]

Ulrik Brandes. 2001. A faster algorithm for betweenness centrality. J. Math. Sociol. 25, 2 (2001), 163--177.

[20]

Gunnar Brinkmann, Jack H. Koolen, and Vincent Moulton. 2001. On the hyperbolicity of chordal graphs. Ann. Combin. 5, 1 (2001), 61--69.

[21]

Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. 2011. Boolean-width of graphs. Theor. Comput. Sci. 412, 39 (2011), 5187--5204.

[22]

Pierre Charbit, Fabien De Montgolfier, and Mathieu Raffinot. 2012. Linear time split decomposition revisited. SIAM J. Discr. Math. 26, 2 (2012), 499--514.

[23]

Nathann Cohen, David Coudert, Guillaume Ducoffe, and Aurélien Lancin. 2017. Applying clique-decomposition for computing Gromov hyperbolicity. Theor. Comput. Sci. 690 (2017), 114--139.

[24]

Nathann Cohen, David Coudert, and Aurélien Lancin. 2015. On computing the Gromov hyperbolicity. J. Exp. Algor. 20 (2015), 1--6.

Digital Library

[25]

Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce Reed, and Udi Rotics. 2000. Polynomial time recognition of clique-width ≤3 graphs. In Proceedings of the Latin American Theoretical INformatics Symposium (LATIN’00), Lecture Notes in Computer Science, Vol. 1776. Springer, 126--134.

Digital Library

[26]

Derek G. Corneil, Yehoshua Perl, and Lorna K. Stewart. 1985. A linear recognition algorithm for cographs. SIAM J. Comput. 14, 4 (1985), 926--934.

Digital Library

[27]

Derek G. Corneil and Udi Rotics. 2005. On the relationship between clique-width and treewidth. SIAM J. Comput. 34, 4 (2005), 825--847.

Digital Library

[28]

David Coudert and Guillaume Ducoffe. 2014. Recognition of C<sub>4</sub>-free and 1/2-hyperbolic graphs. SIAM J. Discr. Math. 28, 3 (2014), 1601--1617.

Digital Library

[29]

David Coudert, Guillaume Ducoffe, and Alexandru Popa. 2018. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’18). SIAM, 2765--2784.

[30]

Bruno Courcelle. 1990. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85, 1 (1990), 12--75.

Digital Library

[31]

Bruno Courcelle. 2012. On the model-checking of monadic second-order formulas with edge set quantifications. Discr. Appl. Math. 160, 6 (2012), 866--887.

Digital Library

[32]

Bruno Courcelle, Joost Engelfriet, and Grzegorz Rozenberg. 1993. Handle-rewriting hypergraph grammars. J. Comput. System Sci. 46, 2 (1993), 218--270.

Digital Library

[33]

Bruno Courcelle, Pinar Heggernes, Daniel Meister, Charis Papadopoulos, and Udi Rotics. 2015. A characterisation of clique-width through nested partitions. Discr. Appl. Math. 187 (2015), 70--81.

Digital Library

[34]

Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. 2000. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33, 2 (2000), 125--150.

[35]

Bruno Courcelle and Stephan Olariu. 2000. Upper bounds to the clique width of graphs. Discr. Appl. Math. 101, 1 (2000), 77--114.

Digital Library

[36]

William H. Cunningham. 1982. Decomposition of directed graphs. SIAM J. Algebr. Discr. Methods 3, 2 (1982), 214--228.

Digital Library

[37]

Reinhard Diestel. 2010. Graph Theory, 4th ed. Springer.

[38]

Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer Science 8 Business Media.

Digital Library

[39]

Feodor F. Dragan. 1997. On greedy matching ordering and greedy matchable graphs. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG’97), Lecture Notes in Computer Science, Vol. 1335. Springer, 184--198.

[40]

Feodor F. Dragan and Falk Nicolai. 2000. LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem. Discr. Appl. Math. 98, 3 (2000), 191--207.

Digital Library

[41]

Ran Duan and Seth Pettie. 2014. Linear-time approximation for maximum weight matching. J. ACM 61, 1 (2014), 1.

Digital Library

[42]

Guillaume Ducoffe. 2016. Metric Properties of Large Graphs. Ph.D. Dissertation. Université Côte d’Azur. https://tel.archives-ouvertes.fr/tel-01485328

[43]

Guillaume Ducoffe and Alexandru Popa. 2018. The b-matching problem in distance-hereditary graphs and beyond. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC’18), Leibniz International Proceedings in Informatics, Vol. 123. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 30:1--30:13.

[44]

Guillaume Ducoffe and Alexandru Popa. 2018. The use of a pruned modular decomposition for maximum matching algorithms on some graph classes. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC’18), Leibniz International Proceedings in Informatics, Vol. 123. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 6:1--6:13.

[45]

Jack Edmonds. 1965. Paths, trees, and flowers. Can. J. Math. 17, 3 (1965), 449--467.

[46]

Wolfgang Espelage, Frank Gurski, and Egon Wanke. 2001. How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG’01), Lecture Notes in Computer Science, Vol. 1. Springer, 117--128.

[47]

Jacob Evald and Søren Dahlgaard. 2016. Tight hardness results for distance and centrality problems in constant degree graphs. CoRR abs/1609.08403 (2016). arxiv:1609.08403 http://arxiv.org/abs/1609.08403

[48]

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider. 2009. Clique-width is NP-complete. SIAM J. Discr. Math. 23, 2 (2009), 909--939.

Digital Library

[49]

Till Fluschnik, Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, and Nimrod Talmon. 2017. When can graph hyperbolicity be computed in linear time? In Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 10389. Springer, 397--408.

[50]

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. 2010. Intractability of clique-width parameterizations. SIAM J. Comput. 39, 5 (2010), 1941--1956.

Digital Library

[51]

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. 2014. Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput. 43, 5 (2014), 1541--1563.

Digital Library

[52]

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. 2019. Clique-width III: Hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algor. 15, 1 (2019), 9.

[53]

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Michal Pilipczuk, and Marcin Wrochna. 2018. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Trans. Algor. 14, 3 (2018), 34:1--34:45.

Digital Library

[54]

Jean-Luc Fouquet, Vassilis Giakoumakis, and Jean-Marie Vanherpe. 1999. Bipartite graphs totally decomposable by canonical decomposition. Int. J. Found. Comput. Sci. 10, 4 (1999), 513--533.

[55]

Jean-Luc Fouquet, Igor Parfenoff, and Henri Thuillier. 1997. An O(n)-time algorithm for maximum matching in P<sub>4</sub>-tidy graphs. Inf. Process. Lett. 62, 6 (1997), 281--287.

Digital Library

[56]

Hervé Fournier, Anas Ismail, and Antoine Vigneron. 2015. Computing the Gromov hyperbolicity of a discrete metric space. Inf. Process. Lett. 115, 6 (2015), 576--579.

Digital Library

[57]

Linton C. Freeman. 1977. A set of measures of centrality based on betweenness. Sociometry 40, 1 (1977), 35--41.

[58]

Harold N. Gabow. 1983. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Proceedings of the ACM Symposium on the Theory of Computing (STOC’83). ACM, 448--456.

Digital Library

[59]

Harold N. Gabow and Robert Endre Tarjan. 1983. A linear-time algorithm for a special case of disjoint set union. In Proceedings of the ACM Symposium on the Theory of Computing (STOC’83). ACM, 246--251.

[60]

Jakub Gajarskỳ, Michael Lampis, and Sebastian Ordyniak. 2013. Parameterized algorithms for modular-width. In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC’13), Lecture Notes in Computer Science, Vol. 8246. Springer, 163--176.

[61]

Anka Gajentaan and Mark H. Overmars. 1995. On a class of O(n<sup>2</sup>) problems in computational geometry. Comput. Geom. 5, 3 (1995), 165--185.

Digital Library

[62]

Tibor Gallai. 1967. Transitiv orientierbare graphen. Acta Math. Hung. 18, 1 (1967), 25--66.

[63]

Robert Ganian. 2010. Thread graphs, linear rank-width and their algorithmic applications. In Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA’10), Lecture Notes in Computer Science, Vol. 6460. Springer, 38--42.

Digital Library

[64]

Cyril Gavoille and Christophe Paul. 2003. Distance labeling scheme and split decomposition. Discr. Math. 273, 1 (2003), 115--130.

Digital Library

[65]

Vassilis Giakoumakis, Florian Roussel, and Henri Thuillier. 1997. On P<sub>4</sub>-tidy graphs. Discr. Math. Theor. Comput. Sci. 1, 1 (1997), 17--41. http://dmtcs.episciences.org/232

[66]

Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. 2017. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theor. Comput. Sci. 689 (2017), 67--95.

[67]

Emeric Gioan and Christophe Paul. 2012. Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs. Discr. Appl. Math. 160, 6 (2012), 708--733.

Digital Library

[68]

Martin Charles Golumbic and Udi Rotics. 2000. On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11, 3 (2000), 423--443.

[69]

Mikhaïl Gromov. 1987. Hyperbolic groups. In Essays in Group Theory. Springer, 75--263.

[70]

Frank Gurski and Egon Wanke. 2000. The tree-width of clique-width bounded graphs without K<sub>n</sub>, n. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG’00), Lecture Notes in Computer Science, Vol. 1928. Springer, 196--205.

[71]

Michel Habib and Christophe Paul. 2010. A survey of the algorithmic aspects of modular decomposition. Comput. Sci. Rev. 4, 1 (2010), 41--59.

Digital Library

[72]

Edward Howorka. 1979. On metric properties of certain clique graphs. J. Combin. Theor. B 27, 1 (1979), 67--74.

[73]

Thore Husfeldt. 2016. Computing graph distances parameterized by treewidth and diameter. In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC’16), Leibniz International Proceedings in Informatics, Vol. 63. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 16:1--16:11.

[74]

Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 1998. Which problems have strongly exponential complexity? In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS’98). IEEE, 653--663.

Digital Library

[75]

Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. 2018. On the power of tree-depth for fully polynomial FPT algorithms. In Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS’18), Leibniz International Proceedings in Informatics, Vol. 96. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 41:1--41:14.

[76]

Beverly Jamison and Stephan Olariu. 1995. P-components and the homogeneous decomposition of graphs. SIAM J. Discr. Math. 8, 3 (1995), 448--463.

Digital Library

[77]

Camille Jordan. 1869. Sur les assemblages de lignes. J. Reine Ang. Math. 1869, 70 (1869), 185--190.

[78]

Richard M. Karp and Michael Sipser. 1981. Maximum matching in sparse random graphs. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS’81). IEEE, 364--375.

Digital Library

[79]

Dieter Kratsch and Jeremy P. Spinrad. 2006. Between O(nm) and O(n<sup>a</sup>). SIAM J. Comput. 36, 2 (2006), 310--325.

Digital Library

[80]

Stefan Kratsch and Florian Nelles. 2018. Efficient and adaptive parameterized algorithms on modular decompositions. In Proceedings of the European Symposia on Algorithms (ESA’18). 55:1--55:15.

[81]

Michael Lampis. 2012. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64, 1 (2012), 19--37.

[82]

Jean-Marc Lanlignel. 2001. Autour de la décomposition en coupes. Ph.D. Dissertation. Université Montpellier 2.

[83]

Johann A. Makowsky and Udi Rotics. 1999. On the clique-width of graphs with few P<sub>4</sub>’s. Int. J. Found. Comput. Sci. 10, 03 (1999), 329--348.

[84]

George B. Mertzios, André Nichterlein, and Rolf Niedermeier. 2017. The power of linear-time data reduction for maximum matching. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS’17), Leibniz International Proceedings in Informatics, Vol. 83. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 46:1--46:14.

[85]

Silvio Micali and Vijay V. Vazirani. 1980. An O(√VE) algorithm for finding maximum matching in general graphs. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS’80). IEEE, 17--27.

Digital Library

[86]

Mark B. Novick. 1989. Fast Parallel Algorithms for the Modular Decomposition. Technical Report TR89-1016. Cornell University. https://hdl.handle.net/1813/6816.

[87]

Stephan Olariu. 1989. Weak bipolarizable graphs. Discr. Math. 74, 1--2 (1989), 159--171.

Digital Library

[88]

Sang-il Oum and Paul D. Seymour. 2006. Approximating clique-width and branch-width. J. Combin. Theor. B 96, 4 (2006), 514--528.

Digital Library

[89]

Rami Puzis, Yuval Elovici, Polina Zilberman, Shlomi Dolev, and Ulrik Brandes. 2015. Topology manipulations for speeding betweenness centrality computation. J. Complex Netw. 3, 1 (Mar. 2015), 84--112.

[90]

Yuri Rabinovich, Jan Arne Telle, and Martin Vatshelle. 2013. Upper bounds on boolean-width with applications to exact algorithms. In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC’13), Lecture Notes in Computer Science, Vol. 8246. Springer, 308--320.

[91]

Michaël Rao. 2008. Clique-width of graphs defined by one-vertex extensions. Discr. Math. 308, 24 (2008), 6157--6165.

Digital Library

[92]

Michaël Rao. 2008. Solving some NP-complete problems using split decomposition. Discr. Appl. Math. 156, 14 (2008), 2768--2780.

Digital Library

[93]

Neil Robertson and Paul D. Seymour. 1986. Graph minors. II. Algorithmic aspects of tree-width. J. Algor. 7, 3 (1986), 309--322.

[94]

Liam Roditty and Virginia Vassilevska Williams. 2013. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the ACM Symposium on the Theory of Computing (STOC’13). ACM, 515--524.

Digital Library

[95]

Petra Scheffler. 1990. A linear algorithm for the pathwidth of trees. In Topics in Combinatorics and Graph Theory. Springer, 613--620.

[96]

Mauricio Soto Gómez. 2011. Quelques propriétés topologiques des graphes et applications à internet et aux réseaux. Ph.D. Dissertation. Univ. Paris Diderot (Paris 7). Retrieved from http://www.dim.uchile.cl/ mausoto/memoires/these.pdf.

[97]

David P. Sumner. 1973. Graphs indecomposable with respect to the X-join. Discr. Math. 6, 3 (1973), 281--298.

Digital Library

[98]

Marc Tedder, Derek G. Corneil, Michel Habib, and Christophe Paul. 2008. Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP’08), Lecture Notes in Computer Science, Vol. 5125. Springer, 634--645.

[99]

Virginia Vassilevska Williams. 2015. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (Invited talk). In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC’15), Leibniz International Proceedings in Informatics, Vol. 43. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 16--28.

[100]

Virginia Vassilevska Williams and R. Ryan Williams. 2010. Subcubic equivalences between path, matrix and triangle problems. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS’10). IEEE, 645--654.

Digital Library

[101]

Ming-Shing Yu and Cheng-Hsing Yang. 1993. An O(n)-time algorithm for maximum matching on cographs. Inf. Process. Lett. 47, 2 (1993), 89--93.

Digital Library

Cited By

Korhonen TSokołowski MMohar BShinkar IO'Donnell R(2024)Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic RankwidthProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649732(1538-1549)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649732
Ortali GTollis I(2024)A Fixed-Parameter Algorithm for Dominance Drawings of DAGsTheoretical Computer Science10.1016/j.tcs.2024.114819(114819)Online publication date: Sep-2024
https://doi.org/10.1016/j.tcs.2024.114819
Cordasco GGargano LRescigno A(2024)Parameterized complexity for iterated type partitions and modular-widthDiscrete Applied Mathematics10.1016/j.dam.2024.03.009350:C(100-122)Online publication date: 15-Jun-2024
https://dl.acm.org/doi/10.1016/j.dam.2024.03.009
Show More Cited By

Index Terms

Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Graph algorithms
      2. Matchings and factors
2. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness
  2. Design and analysis of algorithms
    1. Graph algorithms analysis
    2. Parameterized complexity and exact algorithms
      1. Fixed parameter tractability

Recommendations

Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
SODA '18: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

Recently, hardness results for problems in P were achieved using reasonable complexity theoretic assumptions such as the Strong Exponential Time Hypothesis. According to these assumptions, many graph theoretic problems do not admit truly subquadratic ...
Computing the Tutte Polynomial on Graphs of Bounded Clique-Width

The Tutte polynomial is a notoriously hard graph invariant, and efficient algorithms for it are known only for a few special graph classes, like for those of bounded tree-width. The notion of clique-width extends the definition of cographs (graphs ...
Recent developments on graphs of bounded clique-width

Whether the clique-width of graphs in a certain class of graphs is bounded or not, is an important question from an algorithmic point of view, as many problems that are NP-hard in general admit polynomial-time solutions when restricted to graphs of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 15, Issue 3

July 2019

392 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3331056

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 June 2019

Accepted: 01 January 2019

Revised: 01 January 2019

Received: 01 April 2018

Published in TALG Volume 15, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
270
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)3

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Korhonen TSokołowski MMohar BShinkar IO'Donnell R(2024)Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic RankwidthProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649732(1538-1549)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649732
Ortali GTollis I(2024)A Fixed-Parameter Algorithm for Dominance Drawings of DAGsTheoretical Computer Science10.1016/j.tcs.2024.114819(114819)Online publication date: Sep-2024
https://doi.org/10.1016/j.tcs.2024.114819
Cordasco GGargano LRescigno A(2024)Parameterized complexity for iterated type partitions and modular-widthDiscrete Applied Mathematics10.1016/j.dam.2024.03.009350:C(100-122)Online publication date: 15-Jun-2024
https://dl.acm.org/doi/10.1016/j.dam.2024.03.009
Oostveen Jvan Leeuwen E(2024)Parameterized Complexity of Streaming Diameter and Connectivity ProblemsAlgorithmica10.1007/s00453-024-01246-z86:9(2885-2928)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01246-z
Dragan FDucoffe G(2024)$$\alpha _i$$-Metric Graphs: Radius, Diameter and all EccentricitiesAlgorithmica10.1007/s00453-024-01223-686:7(2092-2129)Online publication date: 25-Mar-2024
https://doi.org/10.1007/s00453-024-01223-6
Jaffke LLima PLokshtanov D(2024)b-Coloring Parameterized by Clique-WidthTheory of Computing Systems10.1007/s00224-023-10132-068:4(1049-1081)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00224-023-10132-0
Abidha VAshok PTomar AYadav D(2023)Colouring a dominating set without conflicts: q-subset square colouringTheoretical Computer Science10.1016/j.tcs.2023.114160(114160)Online publication date: Aug-2023
https://doi.org/10.1016/j.tcs.2023.114160
Ducoffe G(2023)Distance problems within Helly graphs and k-Helly graphsTheoretical Computer Science10.1016/j.tcs.2023.113690946(113690)Online publication date: Feb-2023
https://doi.org/10.1016/j.tcs.2023.113690
Mertzios GMolter HNiedermeier RZamaraev VZschoche P(2023)Computing maximum matchings in temporal graphsJournal of Computer and System Sciences10.1016/j.jcss.2023.04.005137(1-19)Online publication date: Nov-2023
https://doi.org/10.1016/j.jcss.2023.04.005
Kratsch SNelles F(2023)Efficient parameterized algorithms for computing all-pairs shortest pathsDiscrete Applied Mathematics10.1016/j.dam.2023.07.029341:C(102-119)Online publication date: 31-Dec-2023
https://dl.acm.org/doi/10.1016/j.dam.2023.07.029
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents