Dresden 2017 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe
DY: Fachverband Dynamik und Statistische Physik
DY 26: Posters - Statistical Physics, Stochastic Thermodynamics
DY 26.13: Poster
Dienstag, 21. März 2017, 18:15–21:00, P3
A Linear Programming Approach to Graph-Coloring — •Daniel Grujic and Alexander K. Hartmann — Institut of Physics, University of Oldenburg
We study phase transitions in the combinatorial optimimization problem [1] in particular Graph-Coloring for Erdős-Rényi random graphs with N nodes and M edges. Graph coloring is an assignment of q colors to vertices in a way that no two adjacent vertices share the same color. To find such a solution we use the simplex algorithm known from linear programming (LP). Similiar studies were performed previously for other NP-hard problems like the Vertex-Cover problem [2] and the Travelling-Salesman problem [3]. We use a LP relaxation, which can lead to incomplete solutions where a node has multiple colors. We find that the LP is able to find complete solutions for small connectivities c = 2M/N which means the problem is “easy” there. At the critical connectivity ccrit a phase transition occurs. Beyond the critical point we find incomplete solutions with high probability. We try different methods to eliminate such incomplete solutions such as different types of cutting planes. We also try a pseudo-optimization, where we assign specific colors to specific nodes in advance and let the LP try to retain the colors. Both approaches lead to different critical thresholds ccrit.
[1] A. K. Hartmann, M. Weight, Phase Transitions in Combinatorial Optimization Problems, Wiley-VCH, Weinheim (2005)
[2] T. Dewenter, A. K. Hartmann, Phys. Rev. E 86, 041128 (2012)
[3] Hendrik Schawe, Alexander K. Hartmann, EPL 113, 30004 (2016)