TU Darmstadt ULB TUprints

# Partitioning into Isomorphic or Connected Subgraphs

### Lüthen, Hendrik :Partitioning into Isomorphic or Connected Subgraphs. Technische Universität, Darmstadt [Ph.D. Thesis], (2019)  Preview
Text
LuethenDissertation.pdf - Accepted Version
Available under CC-BY-SA 4.0 International - Creative Commons, Attribution Share-alike.

Item Type: Ph.D. Thesis
Title: Partitioning into Isomorphic or Connected Subgraphs
Language: English
Abstract:

This thesis deals mainly with the partitioning and connectedness of graphs. First, we show that the problem of partitioning the nodes of a graph into a specific number of subsets such that the induced subgraphs on these sets are isomorphic to one another is NP-complete. If the induced subgraphs have to be connected, the problem remains NP-complete. Then we inspect some special graph classes for which the problem is solvable in polynomial time. Afterwards, we deal with the problem of defining a polytope by incidence vectors of nodes, which induce a connected graph. We inspect some facet-defining inequalities and their general structure. For some graph classes we state the full description. We then proceed to the problem of partitioning the nodes of a graph into a given number of parts such that the induced graphs are connected. For the corresponding polytope we show the dimension and some facet defining inequalities. This theoretical inspection is advanced by the problem of partitioning a graph into different parts such that the parts induce a connected graph in order to maximize the induced cut. We introduce different ideas for solving this problem in SCIP and show the numerical results. This leads to interesting problems on MIPs in general. As the problem in literature generally deals with the feasible region, we focus on the objective function. To do that, we inspect the problem of finding MIPs for problems with nonlinear objective functions. We discuss properties and requirements showing the existence or non-existence of particular formulations. Lastly, we inspect the problem of partitioning the nodes of a graph such that all but one class are isomorphic. This problem becomes interesting if the part not inducing the isomorphism is minimized. For this purpose we also introduce a technique, which generates the parts by brute-force. Instead of partitioning the graph into isomorphic parts, we proceed to the problem of similar graphs. In this case we inspect different similarities and show algorithms which implement these.

Alternative Abstract:
Alternative AbstractLanguage
Diese Arbeit befasst sich hauptsächlich mit der Partitionierung und dem Zusammenhang von Graphen. Als erstes zeigen wir, dass das Problem, die Knoten eines Graphen in eine vorgegebene Anzahl an Teilmengen zu teilen, sodass die induzierten Subgraphen jeweils isomorph zueinander sind, NP-vollständig ist. Wenn die induzierten Subgraphen auch noch zusammenhängend sein sollen, bleibt das Problem NP-vollständig. Anschließend untersuchen wir spezielle Graphenklassen für die dieses Problem in Polynomialzeit gelöst werden kann. Danach betrachten wir das Polytop, welches durch die Inzidenzvektoren von Knoten induziert wird, welche einen zusammenhängenden Subgraphen induzieren. Wir untersuchen facettendefinierende Ungleichungen und deren allgemeine Struktur. Für spezielle Graphenklassen geben wir eine vollständige Beschreibung an. Danach befassen wir uns mit dem Problem, die Knoten eines Graphen so in eine gegebene Anzahl an Teilmengen zu partitionieren, dass die induzierten Subgraphen zusammenhängend sind. Für das entsprechende Polytop zeigen wir die Dimension und facettendefinierende Ungleichungen. Diese theoretische Betrachtung wird durch das Problem erweitert, die Knoten eines Graphen in eine vorgegebene Anzahl zu partitionieren, sodass die induzierten Graphen zusammenhängend sind, derart, dass der entsprechende Schnitt maximiert wird. Wir stellen verschiedene Wege vor, dieses Problem in SCIP zu lösen und zeigen numerische Resultate. Hierdurch werden interessante Problem für MIPs im generellen angedeutet. Da dieses Problem in der Literatur im Allgemeinen nur durch die zulässige Menge definiert wird, betrachten wir die Zielfunktion. Hierfür betrachten wir das Problem, MIPs für Probleme mit nicht-linearer Zielfunktion zu finden. Wir diskutieren Eigenschaften und Voraussetzungen für die Existenz oder Nichtexistenz spezieller Formulierungen. Als letztes betrachten wir das Problem, die Knoten eines Graphen so zu partitionieren, dass alle bis auf einen induzierten Graphen isomorph sind. Dieses Problem wird interessant, wenn die Menge, die nicht die Isomorphie induziert, minimiert wird. Hierfür stellen wir auch eine Technik vor, die auf Brute-Force basiert. Statt den Graphen in isomorphe Teile zu zerlegen, untersuchen wir noch ähnliche Graphen. In diesem Fall betrachten wir verschiedene Definitionen von Ähnlichkeit und stellen vor, wie diese implementiert worden sind.German
Classification DDC: 500 Naturwissenschaften und Mathematik > 510 Mathematik
Divisions: 04 Department of Mathematics > Optimization > Discrete Optimization
Date Deposited: 28 Feb 2019 14:07
URN: urn:nbn:de:tuda-tuprints-84572
Referees: Pfetsch, Prof. Dr. Marc E. and Liers, Prof. Dr. Frauke
Refereed: 4 May 2018 View Item