Partitioning Perfect Graphs into Stars |
| |
| Authors: | René van Bevern Robert Bredereck Laurent Bulteau Jiehua Chen Vincent Froese Rolf Niedermeier Gerhard J Woeginger |
| |
| Affiliation: | 1. NOVOSIBIRSK STATE UNIVERSITY, NOVOSIBIRSK, RUSSIAN FEDERATION;2. INSTITUT FüR SOFTWARETECHNIK UND THEORETISCHE INFORMATIK, TU BERLIN, BERLIN, GERMANY;3. INSTITUT GASPARD‐MONGE, UNIVERSITé PARIS‐EST MARNE‐LA‐VALLéE, MARNE‐LA‐VALLéE, FRANCE;4. DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE, TU EINDHOVEN, EINDHOVEN, THE NETHERLANDS |
| |
| Abstract: | 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 same‐size 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‐complete cases, for example, on grid graphs and chordal graphs. |
| |
| Keywords: | P3‐Partition generalized matching problem graph factors graph packing graph algorithms |
|
|
