# Lund University Publications

## LUND UNIVERSITY LIBRARIES

### Efficient Parallel Algorithms for Combinatorial Problems

(1996)
Abstract
This thesis is concerned with the design of efficient parallel algorithms for some optimization graph problems. A subset S of vertices or edges in a graph G is said to be maximum with respect to a property if, among all the subsets of G having this property, S is one having the largest cardinality. Set S is said to be maximal with respect to a property, if it is not a proper subset of another set having this property.

A subset of vertices in a graph, is called independent if no two of them are adjacent. The problems of finding maximum and maximal independent sets in a graph are well known. For any positive integer k, we call a set Q of vertices a k-dependent set, if each vertex in Q has no more than k neighbours in Q.... (More)
This thesis is concerned with the design of efficient parallel algorithms for some optimization graph problems. A subset S of vertices or edges in a graph G is said to be maximum with respect to a property if, among all the subsets of G having this property, S is one having the largest cardinality. Set S is said to be maximal with respect to a property, if it is not a proper subset of another set having this property.

A subset of vertices in a graph, is called independent if no two of them are adjacent. The problems of finding maximum and maximal independent sets in a graph are well known. For any positive integer k, we call a set Q of vertices a k-dependent set, if each vertex in Q has no more than k neighbours in Q. Thus an independent set is a 0-dependent set.

We prove that the maximum k-dependent set problem is NP-complete for every fixed integer k even when restricted to planar graphs. We extend known approximation heuristics for the maximum independent set for planar graphs to include maximum k-dependent sets. We observe that these problems can be solved in linear time when restricted to partial k-trees.

While the problem of finding a maximum k-dependent set in a graph is NP hard, finding a maximal k-dependent set can be easily done in linear time using a greedy algorithm. However, constructing efficient parallel algorithms for this problem is not trivial. We present the first NC algorithm for this problem.

A subset of the set of edges in a graph such that no two edges in the set are adjacent is called a matching. Let f be an integer valued function defined over the set of vertices, such that for each vertex v, 0 < f(v) < deg (v). An f-matching is a subset of edges such that for each vertex v at most f(v) edges of the subset are adjacent to v. Taking f(v) = 1 for all vertices v results in an "ordinary" matching.

We don't know whether it is possible to find an NC algorithm for finding a maximum matching. We show that the maximum f-matching problem is NC reducible to the maximum matching problem. A maximal f-matching can be trivially constructed by a greedy sequential algorithm. Designing parallel algorithms for this problem requires more complicated methods. Here we present the first deterministisc and randomized NC algorithms for this problem.

A hypergraph H=(V,E) is a natural generalization of a graph, where an edge in E is an arbitrary subset of the set V. An independent set in H is a subset of V which doesn't include any edge in E. The parallel complexity status of finding a maximal independent set in an arbitrary hypergraph is regarded as a major open problem in parallel complexity theory. We show that this problem admits NC algorithms if the input hypergraph is of so called polylogarithmic arboricity. (Less)
author
opponent
• Prof. Sykora, Ondrzej
publishing date
type
Thesis
publication status
published
subject
keywords
Matematik, Mathematics, Data- och systemvetenskap, computer technology, Systems engineering, matchings., independent sets, graphs, parallel algorithms
pages
72 pages
publisher
Department of Computer Science, Lund University
defense location
Room E:1406, E-Huset, Lund Technologi Institute, Lund, Sweden
defense date
1996-03-16 10:15
external identifiers
• Other:LUNSFD6/(NFCS-1009)/1-72/(1996)
language
English
LU publication?
no
id
4788f1ec-bfeb-4731-9128-a31fbb97d492 (old id 17590)
2007-05-24 09:43:40
date last changed
2016-09-19 08:45:10
```@misc{4788f1ec-bfeb-4731-9128-a31fbb97d492,
abstract     = {This thesis is concerned with the design of efficient parallel algorithms for some optimization graph problems. A subset S of vertices or edges in a graph G is said to be maximum with respect to a property if, among all the subsets of G having this property, S is one having the largest cardinality. Set S is said to be maximal with respect to a property, if it is not a proper subset of another set having this property.<br/><br>
<br/><br>
A subset of vertices in a graph, is called independent if no two of them are adjacent. The problems of finding maximum and maximal independent sets in a graph are well known. For any positive integer k, we call a set Q of vertices a k-dependent set, if each vertex in Q has no more than k neighbours in Q. Thus an independent set is a 0-dependent set.<br/><br>
<br/><br>
We prove that the maximum k-dependent set problem is NP-complete for every fixed integer k even when restricted to planar graphs. We extend known approximation heuristics for the maximum independent set for planar graphs to include maximum k-dependent sets. We observe that these problems can be solved in linear time when restricted to partial k-trees.<br/><br>
<br/><br>
While the problem of finding a maximum k-dependent set in a graph is NP hard, finding a maximal k-dependent set can be easily done in linear time using a greedy algorithm. However, constructing efficient parallel algorithms for this problem is not trivial. We present the first NC algorithm for this problem.<br/><br>
<br/><br>
A subset of the set of edges in a graph such that no two edges in the set are adjacent is called a matching. Let f be an integer valued function defined over the set of vertices, such that for each vertex v, 0 &lt; f(v) &lt; deg (v). An f-matching is a subset of edges such that for each vertex v at most f(v) edges of the subset are adjacent to v. Taking f(v) = 1 for all vertices v results in an "ordinary" matching.<br/><br>
<br/><br>
We don't know whether it is possible to find an NC algorithm for finding a maximum matching. We show that the maximum f-matching problem is NC reducible to the maximum matching problem. A maximal f-matching can be trivially constructed by a greedy sequential algorithm. Designing parallel algorithms for this problem requires more complicated methods. Here we present the first deterministisc and randomized NC algorithms for this problem.<br/><br>
<br/><br>
A hypergraph H=(V,E) is a natural generalization of a graph, where an edge in E is an arbitrary subset of the set V. An independent set in H is a subset of V which doesn't include any edge in E. The parallel complexity status of finding a maximal independent set in an arbitrary hypergraph is regarded as a major open problem in parallel complexity theory. We show that this problem admits NC algorithms if the input hypergraph is of so called polylogarithmic arboricity.},
author       = {Garrido Gómez, Oscar},
keyword      = {Matematik,Mathematics,Data- och systemvetenskap,computer technology,Systems engineering,matchings.,independent sets,graphs,parallel algorithms},
language     = {eng},
pages        = {72},
publisher    = {ARRAY(0x8db1858)},
title        = {Efficient Parallel Algorithms for Combinatorial Problems},
year         = {1996},
}

```