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

David Coudert, Guillaume Ducoffe, Alexandru Popa

Research output: Contribution to journalArticle

Abstract

Recently, hardness results for problems in P were achieved using reasonable complexity-theoretic assumptions such as the Strong Exponential TimeHypothesis.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(k4 n +m)-time for computing a maximum matching, where k is either the modular-width of the graph 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
Article number0078
JournalACM Transactions on Algorithms
Volume15
Issue number3
DOIs
Publication statusPublished - May 1 2019

Fingerprint

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

Keywords

  • Clique-width
  • Fully polynomial FPT
  • Hardness in P
  • Modular decomposition
  • Neighbourhood diversity
  • Primeval decomposition
  • Split decomposition

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Cite this

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

In: ACM Transactions on Algorithms, Vol. 15, No. 3, 0078, 01.05.2019.

Research output: Contribution to journalArticle

Coudert, David ; Ducoffe, Guillaume ; Popa, Alexandru. / Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. In: ACM Transactions on Algorithms. 2019 ; Vol. 15, No. 3.
@article{1cbe2a8a3825451c8a900467664aafa0,
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 TimeHypothesis.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(k4 n +m)-time for computing a maximum matching, where k is either the modular-width of the graph 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.",
keywords = "Clique-width, Fully polynomial FPT, Hardness in P, Modular decomposition, Neighbourhood diversity, Primeval decomposition, Split decomposition",
author = "David Coudert and Guillaume Ducoffe and Alexandru Popa",
year = "2019",
month = "5",
day = "1",
doi = "10.1145/3310228",
language = "English",
volume = "15",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
publisher = "Association for Computing Machinery (ACM)",
number = "3",

}

TY - JOUR

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

AU - Coudert, David

AU - Ducoffe, Guillaume

AU - Popa, Alexandru

PY - 2019/5/1

Y1 - 2019/5/1

N2 - Recently, hardness results for problems in P were achieved using reasonable complexity-theoretic assumptions such as the Strong Exponential TimeHypothesis.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(k4 n +m)-time for computing a maximum matching, where k is either the modular-width of the graph 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 TimeHypothesis.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(k4 n +m)-time for computing a maximum matching, where k is either the modular-width of the graph 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.

KW - Clique-width

KW - Fully polynomial FPT

KW - Hardness in P

KW - Modular decomposition

KW - Neighbourhood diversity

KW - Primeval decomposition

KW - Split decomposition

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

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

U2 - 10.1145/3310228

DO - 10.1145/3310228

M3 - Article

VL - 15

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 3

M1 - 0078

ER -