1. Star Partitions of Perfect Graphs
- Author
-
Bevern, van, R., Bredereck, R., Bulteau, L., Chen, J., Froese, V., Niedermeier, R., Woeginger, G.J., Esparza, J., Fraigniard, P., Husfeldt, T., Koutsoupias, E., Discrete Mathematics, Department of Software Engineering and Theoretical Computer Science (SWT - TUB), Technische Universität Berlin (TU), Department of Mathematics and Computer Science, TUE (Eindhoven) and IMAPP, Nijmegen, and Radboud university [Nijmegen]-TUE and University of Nijmegen
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Discrete mathematics ,Clique-sum ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Strong perfect graph theorem ,Combinatorics ,Modular decomposition ,Indifference graph ,Pathwidth ,Chordal graph ,Maximal independent set ,Split graph ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
International audience; The partition of graphs into nice subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into stars, a problem known to be NP-complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial-time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP-hard cases, for example, on grid graphs and chordal graphs.
- Published
- 2014