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

• DOI: 10.1145/3310228
• Publication Date: 2019-06-10T12:10:51Z
• Authors: David Coudert; Guillaume Ducoffe; Alexandru Popa
• Keywords: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]; FOS: Computer and information sciences; Primeval decomposition; Discrete Mathematics (cs.DM); Modular decomposition; [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]; 0102 computer and information sciences; [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]; Computational Complexity (cs.CC); 01 natural sciences; [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]; [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]; Computer Science - Data Structures and Algorithms; FOS: Mathematics; Mathematics - Combinatorics; Data Structures and Algorithms (cs.DS); Graph algorithms; Neighbourhood diversity; Clique-width; Hardness in P; Split decomposition; Computer Science - Computational Complexity; Combinatorics (math.CO); Fully polynomial FPT; Computer Science - Discrete Mathematics

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 4 ⋅ n + m )-time for computing a maximum matching, where k is either the modular-width of the graph or the P 4 -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.