Article

Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)

Authors:

Udi RoticsAuthors Info & Claims

SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms

Pages 468 - 476

Published: 09 January 2001 Publication History

Abstract

We consider three graph partitioning problems, both from the vertices and the edges point of view. These problems are dominating set, list-q-coloring with costs (fixed number of colors q) and coloring with non-fixed number of colors. They are all known to be NP-hard in general. We show that all these problems (except edge-coloring) can be solved in polynomial time on graphs with clique-width bounded by some constant k, if the k-expression of the input graph is also given. In particular, we present the first polynomial algorithms (on these classes) for chromatic number, edge-dominating set and list-q-coloring with costs (fixed number of colors q, both vertex and edge versions). Since these classes of graphs include classes like P₄-sparse graphs, distance hereditary graphs and graphs with bounded treewidth, our algorithms also apply to these graphs.

References

[1]

L. Cai and J.A. Ellis, NP-Completeness of Edge Colouring Some Restricted Graphs, Discrete Applied Math. 30 (1991), pp. 15-27.]]

Digital Library

[2]

B. Courcelle, private communication.]]

[3]

B. Courcelle, J. Engelfriet and G. Rozenberg, Handlerewriting hypergraphs grammars, J. Comput. System Sci. 46 (1993), pp. 218-270.]]

Digital Library

[4]

D. G. Corneil, M. Habib, J. M. Lanlignel, B. Reed and U. Rotics, Polynomial time recognition of cliquewidth < 3 graphs (Extended Abstract), in Proc. Latin American Theoretical INformatic, LATIN'2000, Lecture Notes in Computer Science 1776 (2000).]]

Digital Library

[5]

B. Courcelle, J.A. Makowsky and U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory of Computing Systems 33 (2000), pp. 125-150.]]

[6]

B. Courcelle, J.A. Makowsky and U. Rotics, On the fixed parameter complexity of graph enumeration problems definable in monadic second order logic, Discrete Applied Math., to appear.]]

Digital Library

[7]

B. Courcelle and S. Olariu, Upper bounds to the cliquewidth of graphs, Discrete Applied Math. 101 (2000), pp. 77-114.]]

Digital Library

[8]

M.U. Gerber and D. Kobler, Algorithms for vertex partitioning problems on graphs with fixed clique-width, Technical report (2000).]]

[9]

M.C. Golumbic and U. Rotics, On the cliquewidth of perfect graph classes (extended abstract), in Proc. Graph Theoretic Concepts in Computer Science WG'99, Lecture Notes in Computer Science 1665 (1999), pp. 135-147.]]

Digital Library

[10]

I. Holyer, The NP-completeness of edge-coloring, SIAM J. Computing 10 (1981), pp. 718-720.]]

[11]

K. Jansen and P. Scheffler, Some coloring results for tree like graphs, in Workshop on Graph Theoretic Con. cepts in Computer Science, Lecture Notes in Computer Science 657 (1992), pp. 50-59.]]

Digital Library

[12]

K. Jansen, Complexity results for the optimum cost chromatic partition problem, Technical Report (1996).]]

[13]

O. Johansson, Clique-decomposition, NLC- decomposition, and modular decomposition relationships and results for random graphs, Congressus Numerantium 132 (1998), pp. 39-60.]]

[14]

M. Kubale, Some results concerning the complexity of restricted colorings of graphs, Discrete Applied Math. 36 (1992), pp. 35-46.]]

Digital Library

[15]

J.A. Makowsky and U. Rotics. On the clique-width of graphs with few P4 's, International Journal of Foundations of Computer Science 10 (1999), pp. 329--348.]]

[16]

K.J. Supowit, Finding a maximum planar subset of a set of nets in a channel, IEEE Transactions on Computer Aided Design 1 (1987), pp. 93-94.]]

[17]

J.A. Telle and A. Proskurowski, Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (1997), pp. 529-550.]]

Digital Library

[18]

E. Wanke, k-NLC graphs and polynomial algorithms, Discrete Applied Math. 54 (1994), pp. 251-266.]]

Digital Library

Cited By

Golovach PLokshtanov DSaurabh SZehavi MCzumaj A(2018)Cliquewidth IIIProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175285(262-273)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175285
Fomin FGolovach PLokshtanov DSaurabh SZehavi M(2018)Clique-width IIIACM Transactions on Algorithms10.1145/328082415:1(1-27)Online publication date: 16-Nov-2018
https://dl.acm.org/doi/10.1145/3280824
Curticapean RMarx D(2016)Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genusProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884548(1650-1669)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884548
Show More Cited By

Index Terms

Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Nonlinear equations
    2. Numerical analysis
      1. Computations on matrices
      2. Computations on polynomials
2. Theory of computation
  1. Formal languages and automata theory
  2. Randomness, geometry and discrete structures

Recommendations

Edge dominating set and colorings on graphs with fixed clique-width

We consider both the vertex and the edge versions of three graph partitioning problems. These problems are dominating set, list-q-coloring with costs (fixed number of colors q) and chromatic number. They are all known to be NP-hard in general. We show ...
Algorithms for vertex-partitioning problems on graphs with fixed clique-width

Many vertex-partitioning problems can be expressed within a general framework introduced by Telle and Proskurowski. They showed that optimization problems in this framework can be solved in polynomial time on classes of graphs with bounded tree-width. ...
Bounding the Clique-Width of H-Free Chordal Graphs

A graph is H-free if it has no induced subgraph isomorphic toï źH. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at mostï ź3 has unbounded clique-width. Brandstädt, Le, and Mosca erroneously ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms

January 2001

937 pages

ISBN:0898714907

Chairman:
S. Rao Kosaraju

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM: Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 09 January 2001

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
385
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Golovach PLokshtanov DSaurabh SZehavi MCzumaj A(2018)Cliquewidth IIIProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175285(262-273)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175285
Fomin FGolovach PLokshtanov DSaurabh SZehavi M(2018)Clique-width IIIACM Transactions on Algorithms10.1145/328082415:1(1-27)Online publication date: 16-Nov-2018
https://dl.acm.org/doi/10.1145/3280824
Curticapean RMarx D(2016)Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genusProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884548(1650-1669)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884548
Belmonte RVatshelle M(2011)Graph classes with structured neighborhoods and algorithmic applicationsProceedings of the 37th international conference on Graph-Theoretic Concepts in Computer Science10.1007/978-3-642-25870-1_6(47-58)Online publication date: 21-Jun-2011
https://dl.acm.org/doi/10.1007/978-3-642-25870-1_6
Fomin FGolovach PLokshtanov DSaurabh SCharikar M(2010)Algorithmic lower bounds for problems parameterized by clique-widthProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873643(493-502)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.5555/1873601.1873643
Fomin FGolovach PLokshtanov DSaurabh SMathieu C(2009)Clique-widthProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496860(825-834)Online publication date: 4-Jan-2009
https://dl.acm.org/doi/10.5555/1496770.1496860

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents