Abstract

Graph partitioning problems enjoy many practical applications as well as algorithmic and theoretical challenges. This motivates the topics of this thesis that is composed of two parts. The first part of the thesis consists of Chapters 2 to 4. In this part, we present results on the complexity and inapproximability of some vertex partitioning problems, and we give approximation algorithms and on-line algorithms for some other vertex partitioning problems. We will start by investigating the inapproximability and complexity of the problems of finding the minimum number of monochromatic cliques and rainbow cycles that, respectively, partition V (G), where the graph G avoids some forbidden induced subgraphs. Secondly, we study the complexity, and develop approximation algorithms and on-line algorithms for injective coloring problems, to be defined later. Finally, we consider the design of a semidefinite programming based approximation algorithm for a variant of the max hypergraph cut problem. The second part of the thesis consists of Chapters 5 to 7. In this part, we turn our attention to structural properties of some problems that are related to matching problems which be regarded as edge partitioning problems. Firstly, we determine the minimum size of a k-extendable bipartite graph and that of an n-factor-critical graph, and we study the problem of determining the minimum size of a k-extendable non-bipartite graph. We solve this problem for k = 1 and k = 2, and we pose a conjecture related to the problem for general k. Secondly, we improve two equivalent structural results due to Woodall and Las Vergnas on the existence of a directed Hamilton cycle in a digraph and the containment of every perfect matching in a Hamilton cycle in a balanced (undirected) bipartite graph, respectively. Finally, we study a generalization of the maximum matching problem called the maximum triangle set problem, in which the aim is to find the maximum number of vertex-disjoint triangles of a given graph. We present a necessary and sufficient condition for augmenting triangle sets, analogous to the well-known augmenting path result for matchings.
Original languageUndefined
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Broersma, Haitze J., Supervisor
  • Uetz, Marc Jochen, Supervisor
Sponsors
Date of Award9 May 2014
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-3626-4
DOIs
StatePublished - 9 May 2014

Fingerprint

Approximation algorithms
Triangle
Partitioning
Graph in graph theory
Vertex of a graph
Inapproximability
Hamilton cycle
Matching problem
Bipartite graph
Forbidden induced subgraph
Factor graph
Maximum matching
Critical graph
Graph partitioning
Semidefinite programming
Perfect matching
Hypergraph
Clique
Undirected graph
Injective

Keywords

  • METIS-303483
  • IR-90624
  • MSC-05C
  • EWI-24778

Cite this

Zhang, X.. / Algorithmic and structural aspects of graph partitioning and related problems. Enschede : Universiteit Twente, 2014. 158 p.
@misc{74238151ac2d414194b3947b4cbcebca,
title = "Algorithmic and structural aspects of graph partitioning and related problems",
abstract = "Graph partitioning problems enjoy many practical applications as well as algorithmic and theoretical challenges. This motivates the topics of this thesis that is composed of two parts. The first part of the thesis consists of Chapters 2 to 4. In this part, we present results on the complexity and inapproximability of some vertex partitioning problems, and we give approximation algorithms and on-line algorithms for some other vertex partitioning problems. We will start by investigating the inapproximability and complexity of the problems of finding the minimum number of monochromatic cliques and rainbow cycles that, respectively, partition V (G), where the graph G avoids some forbidden induced subgraphs. Secondly, we study the complexity, and develop approximation algorithms and on-line algorithms for injective coloring problems, to be defined later. Finally, we consider the design of a semidefinite programming based approximation algorithm for a variant of the max hypergraph cut problem. The second part of the thesis consists of Chapters 5 to 7. In this part, we turn our attention to structural properties of some problems that are related to matching problems which be regarded as edge partitioning problems. Firstly, we determine the minimum size of a k-extendable bipartite graph and that of an n-factor-critical graph, and we study the problem of determining the minimum size of a k-extendable non-bipartite graph. We solve this problem for k = 1 and k = 2, and we pose a conjecture related to the problem for general k. Secondly, we improve two equivalent structural results due to Woodall and Las Vergnas on the existence of a directed Hamilton cycle in a digraph and the containment of every perfect matching in a Hamilton cycle in a balanced (undirected) bipartite graph, respectively. Finally, we study a generalization of the maximum matching problem called the maximum triangle set problem, in which the aim is to find the maximum number of vertex-disjoint triangles of a given graph. We present a necessary and sufficient condition for augmenting triangle sets, analogous to the well-known augmenting path result for matchings.",
keywords = "METIS-303483, IR-90624, MSC-05C, EWI-24778",
author = "X. Zhang",
year = "2014",
month = "5",
doi = "10.3990/1.9789036536264",
isbn = "978-90-365-3626-4",
publisher = "Universiteit Twente",
school = "University of Twente",

}

Algorithmic and structural aspects of graph partitioning and related problems. / Zhang, X.

Enschede : Universiteit Twente, 2014. 158 p.

Research output: ScientificPhD Thesis - Research UT, graduation UT

TY - THES

T1 - Algorithmic and structural aspects of graph partitioning and related problems

AU - Zhang,X.

PY - 2014/5/9

Y1 - 2014/5/9

N2 - Graph partitioning problems enjoy many practical applications as well as algorithmic and theoretical challenges. This motivates the topics of this thesis that is composed of two parts. The first part of the thesis consists of Chapters 2 to 4. In this part, we present results on the complexity and inapproximability of some vertex partitioning problems, and we give approximation algorithms and on-line algorithms for some other vertex partitioning problems. We will start by investigating the inapproximability and complexity of the problems of finding the minimum number of monochromatic cliques and rainbow cycles that, respectively, partition V (G), where the graph G avoids some forbidden induced subgraphs. Secondly, we study the complexity, and develop approximation algorithms and on-line algorithms for injective coloring problems, to be defined later. Finally, we consider the design of a semidefinite programming based approximation algorithm for a variant of the max hypergraph cut problem. The second part of the thesis consists of Chapters 5 to 7. In this part, we turn our attention to structural properties of some problems that are related to matching problems which be regarded as edge partitioning problems. Firstly, we determine the minimum size of a k-extendable bipartite graph and that of an n-factor-critical graph, and we study the problem of determining the minimum size of a k-extendable non-bipartite graph. We solve this problem for k = 1 and k = 2, and we pose a conjecture related to the problem for general k. Secondly, we improve two equivalent structural results due to Woodall and Las Vergnas on the existence of a directed Hamilton cycle in a digraph and the containment of every perfect matching in a Hamilton cycle in a balanced (undirected) bipartite graph, respectively. Finally, we study a generalization of the maximum matching problem called the maximum triangle set problem, in which the aim is to find the maximum number of vertex-disjoint triangles of a given graph. We present a necessary and sufficient condition for augmenting triangle sets, analogous to the well-known augmenting path result for matchings.

AB - Graph partitioning problems enjoy many practical applications as well as algorithmic and theoretical challenges. This motivates the topics of this thesis that is composed of two parts. The first part of the thesis consists of Chapters 2 to 4. In this part, we present results on the complexity and inapproximability of some vertex partitioning problems, and we give approximation algorithms and on-line algorithms for some other vertex partitioning problems. We will start by investigating the inapproximability and complexity of the problems of finding the minimum number of monochromatic cliques and rainbow cycles that, respectively, partition V (G), where the graph G avoids some forbidden induced subgraphs. Secondly, we study the complexity, and develop approximation algorithms and on-line algorithms for injective coloring problems, to be defined later. Finally, we consider the design of a semidefinite programming based approximation algorithm for a variant of the max hypergraph cut problem. The second part of the thesis consists of Chapters 5 to 7. In this part, we turn our attention to structural properties of some problems that are related to matching problems which be regarded as edge partitioning problems. Firstly, we determine the minimum size of a k-extendable bipartite graph and that of an n-factor-critical graph, and we study the problem of determining the minimum size of a k-extendable non-bipartite graph. We solve this problem for k = 1 and k = 2, and we pose a conjecture related to the problem for general k. Secondly, we improve two equivalent structural results due to Woodall and Las Vergnas on the existence of a directed Hamilton cycle in a digraph and the containment of every perfect matching in a Hamilton cycle in a balanced (undirected) bipartite graph, respectively. Finally, we study a generalization of the maximum matching problem called the maximum triangle set problem, in which the aim is to find the maximum number of vertex-disjoint triangles of a given graph. We present a necessary and sufficient condition for augmenting triangle sets, analogous to the well-known augmenting path result for matchings.

KW - METIS-303483

KW - IR-90624

KW - MSC-05C

KW - EWI-24778

U2 - 10.3990/1.9789036536264

DO - 10.3990/1.9789036536264

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-3626-4

PB - Universiteit Twente

ER -

Zhang X. Algorithmic and structural aspects of graph partitioning and related problems. Enschede: Universiteit Twente, 2014. 158 p. Available from, DOI: 10.3990/1.9789036536264