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 language | English |
|---|---|
| Title of host publication | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 |
| Editors | Artur Czumaj |
| Publisher | Association for Computing Machinery |
| Pages | 2765-2784 |
| Number of pages | 20 |
| ISBN (Electronic) | 9781611975031 |
| DOIs | |
| Publication status | Published - Jan 1 2018 |
| Event | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States Duration: Jan 7 2018 → Jan 10 2018 |
Other
| Other | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 |
|---|---|
| Country | United States |
| City | New Orleans |
| Period | 1/7/18 → 1/10/18 |
Fingerprint
ASJC Scopus subject areas
- Software
- Mathematics(all)
Cite this
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 proceeding › Conference contribution
}
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 -