Fully polynomial FPT algorithms for some classes of bounded clique-width graphs

DOI10.1145/3310228MaRDI QIDQ4972678zbMATH OpenOpenAlexWikidataFDO

Authors David Coudert, Guillaume Ducoffe, Alexandru Popa

Publication date 25 November 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.05016

zbMATH Keywords

clique-widthfully polynomial FPThardness in Pmodular decompositionneighbourhood diversityprimeval decompositionsplit decomposition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

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 $P_4$-sparseness). We believe that our most important result is an $calO(k^{4}cdotn+m)$-time algorithm for computing a maximum matching where $k$ is either the modular-width or the $P_4$-sparseness. The latter generalizes many algorithms that have been introduced so far for specific subclasses such as cographs, $P_4$-lite graphs, $P_4$-extendible graphs and $P_4$-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

• A characterisation of clique-width through nested partitions
• A faster algorithm for betweenness centrality*
• A game of cops and robbers
• A Linear Recognition Algorithm for Cographs
• 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 in \(P_{4}\)-tidy graphs
• An O(n) time algorithm for maximum matching on cographs
• 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(n^alpha)
• 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)
• 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?)
• 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 \(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 Relationship Between Clique-Width and Treewidth
• 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
• The \(b\)-matching problem in distance-hereditary graphs and beyond
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The Parallel Complexity of Coloring Games
• The Power of Linear-Time Data Reduction for Maximum Matching
• The use of a pruned modular decomposition for maximum matching algorithms on some graph classes
• 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
• TWO THEOREMS IN GRAPH THEORY
• 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

(41)

• Detecting and enumerating small induced subgraphs in c-closed graphs
• Optimal centrality computations within bounded clique-width graphs
• Maximum matching in almost linear time on graphs of bounded clique-width
• Coloring a dominating set without conflicts: \(q\)-subset square coloring
• On the tree-depth and tree-width in heterogeneous random graphs
• Eccentricity queries and beyond using hub labels
• The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
• The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
• Beyond Helly graphs: the diameter problem on absolute retracts
• Distance problems within Helly graphs and \(k\)-Helly graphs
• On the power of tree-depth for fully polynomial FPT algorithms
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 6850484 (Why is no real title available?)
• Modular-width: an auxiliary parameter for parameterized parallel complexity
• Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
• The \(b\)-matching problem in distance-hereditary graphs and beyond
• Data Reduction for Maximum Matching on Real-World Graphs
• Parameterized complexity of diameter
• The diameter of AT‐free graphs
• Efficient parameterized algorithms for computing all-pairs shortest paths
• A story of diameter, radius, and (almost) Helly property
• Parameterized complexity for iterated type partitions and modular-width
• Computing maximum matchings in temporal graphs
• Dominance drawings for DAGs with bounded modular width
• Maximum Matching in almost linear time on graphs of bounded clique-width
• _i-metric graphs: radius, diameter and all eccentricities
• Getting linear time in graphs of bounded neighborhood diversity
• Parameterized complexity of streaming diameter and connectivity problems
• \(b\)-coloring parameterized by clique-width
• Twin-width. III: Max independent set, min dominating set, and coloring
• A fixed-parameter algorithm for dominance drawings of DAGs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Certificates in P and subquadratic-time computation of radius, diameter, and all eccentricities in graphs
• Separator theorem and algorithms for planar hyperbolic graphs
• The complexity of diameter on H-free graphs
• Parameterized complexity of streaming diameter and connectivity problems
• Obstructions to faster diameter computation: asteroidal sets
• The complexity of diameter on \(H\)-free graphs
• Eccentricity function in distance-hereditary graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs

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)