Star partitions on graphs
| Autor: | L. De Giovanni, C. De Francesco, Paolo Serafini, Giovanni Andreatta |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Computational complexity theory
Linear programming Cardinality constraint 0211 other engineering and technologies Partition problem Polytope 0102 computer and information sciences 02 engineering and technology Domatic bipartition 01 natural sciences Theoretical Computer Science Combinatorics Cardinality Astrophysics::Solar and Stellar Astrophysics Partition (number theory) Astrophysics::Galaxy Astrophysics Mathematics Star partition 021103 operations research Applied Mathematics Integral polytope Computational complexity Treewidth Computational Theory and Mathematics 010201 computation theory & mathematics Bounded function Astrophysics::Earth and Planetary Astrophysics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Discrete Optimization. 33:1-18 |
| ISSN: | 1572-5286 |
| DOI: | 10.1016/j.disopt.2019.01.002 |
| Popis: | Given an undirected graph, a star partition is a partition of the nodes into subsets with at least two nodes so that the subgraph induced by each subset has a spanning star. Star partitions are related to well-known problems concerning domination in graphs and edge covering. We focus on the Constrained Star Partition Problem (CSP) that asks for finding a star partition of given cardinality. The problem is new and presents interesting peculiarities. We explore the relation between the cardinalities of star partitions and domatic bipartitions, showing that there are star partitions of any cardinality between minimum and maximum values, and that a similar but weaker result holds for domatic bipartitions. We study the computational complexity of different versions of star partition and domatic bipartition problems, proving that most of them, in particular CSP, constrained domatic bipartition and balanced domatic bipartition, are NP-complete. We also show that star partition problems are polynomial on trees and, more generally, on bounded treewidth graphs. We introduce an integer linear programming formulation that defines a polytope containing all the star partitions of a graph, showing that its vertices have only integral components for trees, which implies that linear programming can be used to solve weighted star partition problems on trees. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect