Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
From MaRDI portal
modular decompositionclique-widthsplit decompositionprimeval decompositionneighbourhood diversityhardness in Pfully polynomial FPT
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Abstract: Parameterized complexity theory has enabled a refined classification of the difficulty of NP-hard optimization problems on graphs with respect to key structural properties, and so to a better understanding of their true difficulties. More recently, hardness results for problems in P were achieved using reasonable complexity theoretic assumptions such as: Strong Exponential Time Hypothesis (SETH), 3SUM and All-Pairs Shortest-Paths (APSP). According to these assumptions, many graph theoretic problems do not admit truly subquadratic algorithms, nor even truly subcubic algorithms (Williams and Williams, FOCS 2010 and Abboud, Grandoni, Williams, SODA 2015). A central technique used to tackle the difficulty of the above mentioned problems is fixed-parameter algorithms for polynomial-time problems with polynomial dependency in the fixed parameter (P-FPT). This technique was introduced by Abboud, Williams and Wang in SODA 2016 and continued by Husfeldt (IPEC 2016) and Fomin et al. (SODA 2017), using the treewidth as a parameter. Applying this technique to clique-width, another important graph parameter, remained to be done. In this paper we study several graph theoretic problems for which hardness results exist such as cycle problems (triangle detection, triangle counting, girth, diameter), distance problems (diameter, eccentricities, Gromov hyperbolicity, betweenness centrality) and maximum matching. We provide hardness results and fully polynomial FPT algorithms, using clique-width and some of its upper-bounds as parameters (split-width, modular-width and -sparseness). We believe that our most important result is an -time algorithm for computing a maximum matching where is either the modular-width or the -sparseness. The latter generalizes many algorithms that have been introduced so far for specific subclasses such as cographs, -lite graphs, -extendible graphs and -tidy graphs. Our algorithms are based on preprocessing methods using modular decomposition, split decomposition and primeval decomposition. Thus they can also be generalized to some graph classes with unbounded clique-width.
Recommendations
- scientific article; zbMATH DE number 6850484
- Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
- Clique-width: on the price of generality
- Modular-width: an auxiliary parameter for parameterized parallel complexity
- Algorithmic lower bounds for problems parameterized by clique-width
Cites work
- scientific article; zbMATH DE number 1696534 (Why is no real title available?)
- scientific article; zbMATH DE number 4173000 (Why is no real title available?)
- scientific article; zbMATH DE number 4031953 (Why is no real title available?)
- scientific article; zbMATH DE number 1375569 (Why is no real title available?)
- scientific article; zbMATH DE number 1107732 (Why is no real title available?)
- scientific article; zbMATH DE number 2044928 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 1512682 (Why is no real title available?)
- scientific article; zbMATH DE number 6850484 (Why is no real title available?)
- scientific article; zbMATH DE number 7561360 (Why is no real title available?)
- scientific article; zbMATH DE number 7561384 (Why is no real title available?)
- A Linear Recognition Algorithm for Cographs
- A characterisation of clique-width through nested partitions
- A faster algorithm for betweenness centrality*
- A game of cops and robbers
- A linear-time algorithm for a special case of disjoint set union
- A partial k-arboretum of graphs with bounded treewidth
- A survey of the algorithmic aspects of modular decomposition
- Algorithmic meta-theorems for restrictions of treewidth
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- An O(n) time algorithm for maximum matching on cographs
- An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs
- Applying clique-decomposition for computing Gromov hyperbolicity
- Approximating clique-width and branch-width
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- BetweenO(nm) andO(nalpha)
- Bipartite graphs totally decomposable by canonical decomposition
- Boolean-width of graphs
- Clique-width is NP-complete
- Clique-width of graphs defined by one-vertex extensions
- Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
- Computing graph distances parameterized by treewidth and diameter
- Computing the Gromov hyperbolicity of a discrete metric space
- Decomposition of Directed Graphs
- Distance labeling scheme and split decomposition
- Distance-hereditary graphs
- Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- Graph minors. II. Algorithmic aspects of tree-width
- Graph theory
- Graph theory
- Graphs indecomposable with respect to the X-join
- Handle-rewriting hypergraph grammars
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Into the square: on the complexity of some quadratic-time solvable problems
- Intractability of clique-width parameterizations
- LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
- Linear time solvable optimization problems on graphs of bounded clique-width
- Linear time split decomposition revisited
- Linear-time approximation for maximum weight matching
- On a class of \(O(n^ 2)\) problems in computational geometry
- On computing the Gromov hyperbolicity
- On computing the hyperbolicity of real-world graphs
- On metric properties of certain clique graphs
- On the Relationship Between Clique-Width and Treewidth
- On the \(p\)-connectedness of graphs---a survey
- On the clique-width of graph with few \(P_{4}\)'s
- On the clique-width of some perfect graph classes
- On the hyperbolicity of chordal graphs
- On the model-checking of monadic second-order formulas with edge set quantifications
- On the power of tree-depth for fully polynomial FPT algorithms
- On the structure of graphs with few P₄s
- P-Components and the Homogeneous Decomposition of Graphs
- Parameterized Algorithms for Modular-Width
- Paths, Trees, and Flowers
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Recognition and isomorphism of tree-like \(P_4\)-connected graphs
- Recognition of C₄-free and 1/2-hyperbolic graphs
- Safe separators for treewidth
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Solving some NP-complete problems using split decomposition
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- Subcubic equivalences between graph centrality problems, APSP and diameter
- Subcubic equivalences between path, matrix, and triangle problems
- TWO THEOREMS IN GRAPH THEORY
- The Parallel Complexity of Coloring Games
- The Power of Linear-Time Data Reduction for Maximum Matching
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Thread graphs, linear rank-width and their algorithmic applications
- Topology manipulations for speeding betweenness centrality computation
- Transitiv orientierbare Graphen
- Tree-like P₄-connected graphs
- Treewidth: Characterizations, Applications, and Computations
- Upper Bounds on Boolean-Width with Applications to Exact Algorithms
- Upper bounds to the clique width of graphs
- Weak bipolarizable graphs
- When can graph hyperbolicity be computed in linear time?
- Which problems have strongly exponential complexity?
Cited in
(39)- Parameterized complexity for iterated type partitions and modular-width
- On the tree-depth and tree-width in heterogeneous random graphs
- Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
- Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
- The complexity of diameter on H-free graphs
- Obstructions to faster diameter computation: asteroidal sets
- Data Reduction for Maximum Matching on Real-World Graphs
- The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
- scientific article; zbMATH DE number 2044928 (Why is no real title available?)
- Efficient parameterized algorithms for computing all-pairs shortest paths
- The complexity of diameter on \(H\)-free graphs
- The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
- _i-metric graphs: radius, diameter and all eccentricities
- A story of diameter, radius, and (almost) Helly property
- Computing Graph Polynomials on Graphs of Bounded Clique-Width
- Getting linear time in graphs of bounded neighborhood diversity
- Dominance drawings for DAGs with bounded modular width
- The diameter of AT‐free graphs
- Computing maximum matchings in temporal graphs
- Parameterized complexity of streaming diameter and connectivity problems
- \(b\)-coloring parameterized by clique-width
- Maximum Matching in almost linear time on graphs of bounded clique-width
- Maximum matching in almost linear time on graphs of bounded clique-width
- On the power of tree-depth for fully polynomial FPT algorithms
- Twin-width. III: Max independent set, min dominating set, and coloring
- A fixed-parameter algorithm for dominance drawings of DAGs
- Eccentricity queries and beyond using hub labels
- Parameterized complexity of diameter
- Beyond Helly graphs: the diameter problem on absolute retracts
- Detecting and enumerating small induced subgraphs in c-closed graphs
- Certificates in P and subquadratic-time computation of radius, diameter, and all eccentricities in graphs
- Distance problems within Helly graphs and \(k\)-Helly graphs
- Eccentricity function in distance-hereditary graphs
- Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
- Separator theorem and algorithms for planar hyperbolic graphs
- scientific article; zbMATH DE number 6850484 (Why is no real title available?)
- Parameterized complexity of streaming diameter and connectivity problems
- Optimal centrality computations within bounded clique-width graphs
- Coloring a dominating set without conflicts: \(q\)-subset square coloring
This page was built for publication: Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4972678)
