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

David Coudert, Guillaume Ducoffe, Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Citations (Scopus)

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 paper 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 O(k4 · n + m)-time algorithm for computing a maximum matching where k is either the modular-width or the P4-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.

Original languageEnglish
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Pages2765-2784
Number of pages20
ISBN (Electronic)9781611975031
DOIs
Publication statusPublished - Jan 1 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Other

Other29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
CountryUnited States
CityNew Orleans
Period1/7/181/10/18

Fingerprint

Clique-width
Polynomial Algorithm
Polynomials
Graph in graph theory
Hardness
Fixed-parameter Algorithms
Maximum Matching
Modular Decomposition
Decomposition
Cographs
Polynomial
Graph Classes
Exponential time
Preprocessing
Class
Upper bound
Cycle
Decompose
Generalise
Computing

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Coudert, D., Ducoffe, G., & Popa, A. (2018). Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. In A. Czumaj (Ed.), 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 (pp. 2765-2784). Association for Computing Machinery. https://doi.org/10.1137/1.9781611975031.176

Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. / Coudert, David; Ducoffe, Guillaume; Popa, Alexandru.

29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. ed. / Artur Czumaj. Association for Computing Machinery, 2018. p. 2765-2784.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Coudert, D, Ducoffe, G & Popa, A 2018, Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. in A Czumaj (ed.), 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Association for Computing Machinery, pp. 2765-2784, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, United States, 1/7/18. https://doi.org/10.1137/1.9781611975031.176
Coudert D, Ducoffe G, Popa A. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. In Czumaj A, editor, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Association for Computing Machinery. 2018. p. 2765-2784 https://doi.org/10.1137/1.9781611975031.176
Coudert, David ; Ducoffe, Guillaume ; Popa, Alexandru. / Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. editor / Artur Czumaj. Association for Computing Machinery, 2018. pp. 2765-2784
@inproceedings{493b002ba37c4e0493ee9e63986e4a23,
title = "Fully polynomial FPT algorithms for some classes of bounded clique-width graphs",
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 paper 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 O(k4 · n + m)-time algorithm for computing a maximum matching where k is either the modular-width or the P4-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.",
author = "David Coudert and Guillaume Ducoffe and Alexandru Popa",
year = "2018",
month = "1",
day = "1",
doi = "10.1137/1.9781611975031.176",
language = "English",
pages = "2765--2784",
editor = "Artur Czumaj",
booktitle = "29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018",
publisher = "Association for Computing Machinery",

}

TY - GEN

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

AU - Coudert, David

AU - Ducoffe, Guillaume

AU - Popa, Alexandru

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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 paper 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 O(k4 · n + m)-time algorithm for computing a maximum matching where k is either the modular-width or the P4-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.

AB - 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 paper 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 O(k4 · n + m)-time algorithm for computing a maximum matching where k is either the modular-width or the P4-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.

UR - http://www.scopus.com/inward/record.url?scp=85045548643&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045548643&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.176

DO - 10.1137/1.9781611975031.176

M3 - Conference contribution

AN - SCOPUS:85045548643

SP - 2765

EP - 2784

BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

A2 - Czumaj, Artur

PB - Association for Computing Machinery

ER -