Graph-Theoretic Concepts in Computer Science

Lexicographic Breadth First Search, introduced by Rose, Tarjan and Lueker for the recognition of chordal graphs is currently the most popular graph algorithmic search paradigm, with applications in recognition of restricted graph families, diameter approximation for restricted families and determining a dominating pair in an AT-free graph. This paper surveys this area and provides new directions for further research in the area of graph searching.

Wireless and mobile networks are an excellent playground for graph theoreticians. Many research challenges turn out to be variants of classic graph theory problems. In particular the rapidly growing areas of ad-hoc and sensor networks demand new solutions for timeless graph theory problems, because i) wireless devices have lower bandwidth and ii) wireless devices are mobile and therefore the topology of the network changes rather frequently. As a consequence, algorithms for wireless and mobile networks should have i) as little communication as possible and should ii) run as fast as possible. Both goals can only be achieved by developing algorithms requiring a small number of communication rounds only (so-called

local

algorithms). In this work we present a few connections between graph theory and wireless networking, such as topology control, clustering, and geo-routing. Each section is supplemented with an open problem.

Many algorithms to generate all trees with

n

vertices without repetition are already known. The best algorithm runs in time proportional to the number of trees. However, the time needed to generate each tree may not be bounded by a constant, even though it is “on average”. In this paper we give a simple algorithm to generate all trees with exactly

n

vertices and diameter

d

, without repetition. Our algorithm generates each tree in constant time. It also generates all trees so that each tree can be obtained from the preceding tree by at most three operations. Each operation consists of a deletion of a vertex and an addition of a vertex. By using the algorithm for each diameter 2,3, ⋯ ,

n

 − 1, we can generate all trees with

n

vertices.

An undirected graph is a treelike comparability graph if it admits a transitive orientation such that its transitive reduction is a tree. We show that treelike comparability graphs are distance hereditary. Utilizing this property, we give a linear time recognition algorithm. We then characterize permutation graphs that are treelike. Finally, we consider the

Partitioning into Bounded Cliques

problem on special subgraphs of treelike permutation graphs.

In our contribution to the study of graph labelings with three distance constraints we introduce a concept of elegant labelings: labelings where labels appearing in a neighborhood of a vertex can be completed into intervals such that these intervals are disjoint for adjacent vertices. We justify introduction of this notion by showing that use of these labelings provides good estimates for the span of the label space, and also provide a polynomial time algorithm to find an optimal elegant labeling of a tree for distance constraints (

p

,1,1). In addition several computational complexity issues are discussed.

In this paper we study collective additive tree spanners for families of graphs that either contain or are contained in AT-free graphs. We say that a graph

G

=(

V

,

E

)

admits a system of μ

collective additive tree r

-spanners

if there is a system

${\cal T}(G)$

of at most

μ

spanning trees of

G

such that for any two vertices

x

,

y

of

G

a spanning tree

$T\in {\cal T}(G)$

exists such that

d

T

(

x

,

y

)≤

d

G

(

x

,

y

)+

r

. Among other results, we show that AT-free graphs have a system of two collective additive tree 2-spanners (whereas there are trapezoid graphs that do not admit any additive tree 2-spanner). Furthermore, based on this collection of trees, we derive a compact and efficient routing scheme for those graphs. Also, any DSP-graph (there exists a dominating shortest path) admits one additive tree 4-spanner, a system of two collective additive tree 3-spanners and a system of five collective additive tree 2-spanners.

The Maximum Cardinality Search algorithm visits the vertices of a graph in an order such that at any point, a vertex is visited that has the largest number of visited neighbours. An MCS-ordering of a graph is an ordering of the vertices that can be generated by the Maximum Cardinality Search algorithm. The visited degree of a vertex

v

in an MCS-ordering is the number of neighbours of

v

that are before

v

in the ordering. The MCSLB of an MCS-ordering

ψ

of

G

is the maximum visited degree over all vertices

v

in

ψ

. Lucena [10] showed that the treewidth of a graph

G

is at least the MCSLB of any MCS-ordering of

G

.

In this paper, we analyse the maximum MCSLB over all possible MCS-orderings of given graphs

G

. We give upper and lower bounds for this number for planar graphs. Given a graph

G

, it is NP-complete to determine if

G

has an MCS-ordering with MCSLB at least

k

, for any fixed

k

≥ 7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.

We also propose and experimentally analysed some heuristics for the problem. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the maximum MCSLB that an MCS-ordering can obtain which appear to give results close to optimal on several graphs from real life applications.

This paper presents an optimal fully-dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph

G

, the algorithm supports arc and vertex modification (insertion or deletion) in

$\mathcal{O}(d)$

time where

d

is the number of arcs involved in the operation. Moreover, if the modified graph remains a directed cograph, the modular tree decomposition is updated; otherwise, a certificate is returned within the same complexity.

In this paper, we consider the recognition problem on two classes of perfectly orderable graphs, namely, the HHD-free and the Welsh-Powell opposition graphs (or WPO-graphs). In particular, we prove properties of the chordal completion of a graph and show that a modified version of the classic linear-time algorithm for testing for a perfect elimination ordering can be efficiently used to determine in

O

( min {

n

m

α

(

n

),

nm

+

n

2

log

n

}) time whether a given graph

G

on

n

vertices and

m

edges contains a house or a hole; this leads to an

O

( min {

n

m

α

(

n

),

n

m

 + 

n

2

log

n

})-time and

O

(

n

+

m

)-space algorithm for recognizing HHD-free graphs. We also show that determining whether the complement

$\skew3\overline{G}$

of the graph

G

contains a house or a hole can be efficiently resolved in

O

(

nm

) time using

O

(

n

2

) space; this in turn leads to an

O

(

nm

)-time and

O

(

n

2

)-space algorithm for recognizing WPO-graphs. The previously best algorithms for recognizing HHD-free and WPO-graphs required

O

(

n

3

) time and

O

(

n

2

) space.

This paper gives a decomposition theory for bipartite graphs. It uses

bimodules

, a special case of

2-modules

(also known as

homogeneous pairs

, an extension of both modules and splits). It is shown how a unique decomposition tree represents the bimodular decomposition of a bipartite graph, with strong analogs with modular decomposition of graphs. An

O

(

mn

3

) algorithm for this decomposition is provided. At least a classification of the 2-modules of a bipartite graph is given.

We show how to use split decomposition to compute the weighted clique number and the chromatic number of a graph and we apply these results to some classes of graphs. In particular we present an

O

(

n

2

m

) algorithm to compute the chromatic number for all those graphs having a split decomposition in which every prime graph is an induced subgraph of either a

C

k

or a

$\overline{C_k}$

for some

k

≥ 3.

The clique problem consists in determining whether an undirected graph

G

of order

n

contains a clique of order ℓ. In this paper we are concerned with the decremental version of clique problem, where the property of containing an ℓ-clique is dynamically checked during deletions of nodes. We provide an improved dynamic algorithm for this problem for every fixed value of ℓ ≥ 3. Our algorithm naturally applies to filtering for the constraint satisfaction problem. In particular, we show how to speed up the filtering based on an important local consistency property: the inverse consistency.

Graphs can be represented symbolically by the Ordered Binary Decision Diagram (OBDD) of their characteristic function. To solve problems in such implicitly given graphs, specialized symbolic algorithms are needed which are restricted to the use of functional operations offered by the OBDD data structure. In this paper, a symbolic algorithm for the all-pairs shortest-paths (APSP) problem in loopless directed graphs with strictly positive integral edge weights is presented. It requires

$\Theta\bigl(\log^{2}(NB)\bigr)$

OBDD-operations to obtain the lengths and edges of all shortest paths in graphs with

N

nodes and maximum edge weight

B

. It is proved that runtime and space usage are polylogarithmic w. r. t.

N

and

B

on graph sequences with characteristic bounded-width functions. This convenient property is closed under certain graph composition operations. Moreover, an alternative symbolic approach for general integral edge weights is sketched which does not behave efficiently on general graph sequences with bounded-width functions. Finally, two variants of the APSP problem are briefly discussed.

Let be the following strategy to construct a walk in a labeled digraph: at each vertex, we follow the unvisited arc of minimum label. In this work we study for which languages, applying the previous strategy over the corresponding de Bruijn graph, we finish with an Eulerian cycle, in order to obtain the minimal de Bruijn sequence of the language.

In two previous papers we have investigates the problem of computing the least common subsumer (lcs) and the most specific concept (msc) for the description logic

$\mathcal{EL}$

in the presence of terminological cycles that are interpreted with descriptive semantics, which is the usual first-order semantics for description logics. In this setting, neither the lcs nor the msc needs to exist. We were able to characterize the cases in which the lcs/msc exists, but it was not clear whether this characterization yields decidability of the existence problem.

In the present paper, we develop a common graph-theoretic generalization of these characterizations, and show that the resulting property is indeed decidable, thus yielding decidability of the existence of the lcs and the msc. This is achieved by expressing the property in monadic second-order logic on infinite trees. We also show that, if it exists, then the lcs/msc can be computed in polynomial time.

In portable multimedia systems a number of communicating tasks has to be performed on a set of heterogeneous processors in an energy-efficient way. We model this problem as a graph optimization problem, which we call the minimum weight processor assignment problem. We show that our setting generalizes several problems known in literature, including minimum multiway cut, graph

k

-colorability, and minimum (generalized) vertex covering. We show that the minimum weight processor assignment problem is

NP

-hard, even when restricted to instances where the (process) graph is a bipartite graph with maximum degree at most 3, or with only two processors, or with arbitrarily small weight differences, or with only two different edge weights. For graphs with maximum degree at most 2 (or in fact the larger class of degree-2-contractible graphs) we give a polynomial time algorithm. Finally we generalize this algorithm into an exact (but not efficient) algorithm for general graphs.

In this paper we study a stochastic location problem with applications to tele-diagnostic, locating the boundaries between polynomiality and NP-completeness, and providing efficient approximation algorithms.

A unit disk graph is the intersection graph of unit disks in the euclidean plane. We present a polynomial-time approximation scheme for the maximum weight independent set problem in unit disk graphs. In contrast to previously known approximation schemes, our approach does not require a geometric representation (specifying the coordinates of the disk centers).

The approximation algorithm presented is robust in the sense that it accepts any graph as input and either returns a (1+

ε

)-approximate independent set or a certificate showing that the input graph is no unit disk graph. The algorithm can easily be extended to other families of intersection graphs of geometric objects.

In this paper we use arc tolerances, instead of arc costs, to improve Branch-and-Bound type algorithms for the Asymmetric Traveling Salesman Problem (ATSP). We derive new tighter lower bounds based on exact and approximate bottleneck upper tolerance values of the Assignment Problem (AP). It is shown that branching by tolerances provides a more rational branching process than branching by costs. Among others, we show that branching on an arc with the bottleneck upper tolerance value is the best choice, while such an arc appears quite often in a shortest cycle of the current AP relaxation. This fact shows why branching on shortest cycles was always found as a best choice. Computational experiments confirm our theoretical results.

We consider the

NP

-complete problem of deciding whether an input graph on

n

vertices has

k

vertex-disjoint copies of a fixed graph

H

. For

H

=

K

3

(the triangle) we give an

O

(2

2klog k + 1.869k

n

2

) algorithm, and for general

H

an

O

(2

k

|

H

|

log

k

 + 2

k

|

H

|

log

|

H

|

n

|H|

) algorithm. We introduce a preprocessing (kernelization) technique based on crown decompositions of an auxiliary graph. For

H

=

K

3

this leads to a preprocessing algorithm that reduces an arbitrary input graph of the problem to a graph on

O

(

k

3

) vertices in polynomial time.

We design fast exact algorithms for the problem of computing a minimum dominating set in undirected graphs. Since this problem is NP-hard, it comes with no big surprise that all our time complexities are exponential in the number

n

of vertices. The contribution of this paper are ‘nice’ exponential time complexities that are bounded by functions of the form

c

n

with reasonably small constants

c

<2: For arbitrary graphs we get a time complexity of 1.93782

n

. And for the special cases of split graphs, bipartite graphs, and graphs of maximum degree three, we reach time complexities of 1.41422

n

, 1.73206

n

, and 1.51433

n

, respectively.

This paper examines a parameterized problem that we refer to as

n

–

k

Graph Coloring

, i.e., the problem of determining whether a graph

G

with

n

vertices can be colored using

n

–

k

colors. As the main result of this paper, we show that there exists a

O

(

kn

2

+

k

2

+ 2

3.8161k

)=

O

(

n

2

) algorithm for

n

–

k

Graph Coloring

for each fixed

k

. The core technique behind this new parameterized algorithm is kernalization via maximum (and certain maximal) matchings.

The core technical content of this paper is a near linear-time kernelization algorithm for

n

–

k

Clique Covering

. The near linear-time kernelization algorithm that we present for

n

–

k

Clique Covering

produces a linear size (3

k

–3) kernel in

O

(

k

(

n

+

m

)) steps on graphs with

n

vertices and

m

edges. The algorithm takes an instance 〈

G

,

k

〉 of

Clique Covering

that asks whether a graph

G

can be covered using |

V

|–

k

cliques and reduces it to the problem of determining whether a graph

G

′=(

V

′,

E

′) of size ≤ 3

k

–3 can be covered using |

V

′| –

k

′ cliques. We also present a similar near linear-time algorithm that produces a 3

k

kernel for

Vertex Cover

. This second kernelization algorithm is the

crown reduction rule

.

The family of well-orderly maps is a family of planar maps with the property that every connected planar graph has at least one plane embedding which is a well-orderly map. We show that the number of well-orderly maps with

n

nodes is at most 2

αn

 + 

O

(

log

n

)

, where

α

≈ 4.91. A direct consequence of this is a new upper bound on the number

p

(

n

) of unlabeled planar graphs with

n

nodes, log

2

p

(

n

) ≤ 4.91

n

.

The result is then used to show that asymptotically almost all (labeled or unlabeled), (connected or not) planar graphs with

n

nodes have between 1.85

n

and 2.44

n

edges.

Finally we obtain as an outcome of our combinatorial analysis an explicit linear time encoding algorithm for unlabeled planar graphs using, in the worst-case, a rate of 4.91 bits per node and of 2.82 bits per edge.

We consider the problem of estimating the Shannon capacity of a circulant graph

C

n

,

J

of degree four with

n

vertices and chord length

J

, 2 ≤

J

≤

n

, by computing its Lovász theta function

θ

(

C

n

,

J

). We present an algorithm that takes

O

(

J

) operations if

J

is an odd number, and

O

(

n

/

J

) operations if

J

is even. On the considered class of graphs our algorithm strongly outperforms the known algorithms for theta function computation.

It has long been known that the number of spanning trees in circulant graphs with fixed jumps and

n

nodes satisfies a recurrence relation in

n

. The proof of this fact was algebraic (relating the products of eigenvalues of the graphs’ adjacency matrices) and not combinatorial. In this paper we derive a straightforward combinatorial proof of this fact. Instead of trying to decompose a large circulant graph into smaller ones, our technique is to instead decompose a large circulant graph into different

step graph

cases and then construct a recurrence relation on the step graphs. We then generalize this technique to show that the numbers of Hamiltonian Cycles, Eulerian Cycles and Eulerian Orientations in circulant graphs also satisfy recurrence relations.

The

Phylogenetic

k

th Root Problem (PR

k

)

is theproblem of finding a (phylogenetic) tree

T

from a given graph

G

=(

V

,

E

) such that (1)

T

has no degree-2 internal nodes, (2) the external nodes (

i.e.

leaves) of

T

are exactly the elements of

V

, and (3) (

u

,

v

) ∈

E

if and only if the distance between

u

and

v

in tree

T

is at most

k

, where

k

is some fixed threshold

k

. Such a tree

T

, if exists, is called a

phylogenetick

th

root

of graph

G

. The computational complexity of

PR

k

is open, except for

k

≤ 4. Recently, Chen

et al.

investigated

PR

k

under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. They presented a linear-time algorithm that determines if a given

connectedG

has such a phylogenetic

k

th root, and if so, demonstrates one. In this paper, we supplement their work by presenting a linear-time algorithm for

disconnected

graphs.

An orthogonal drawing of a plane graph is called an octagonal drawing if each inner face is drawn as a rectilinear polygon of at most eight corners and the contour of the outer face is drawn as a rectangle. A slicing graph is obtained from a rectangle by repeatedly slicing it vertically and horizontally. A slicing graph is called a good slicing graph if either the upper subrectangle or the lower one obtained by any horizontal slice will never be vertically sliced. In this paper we show that any good slicing graph has an octagonal drawing with prescribed face areas, in which the area of each inner face is equal to a prescribed value. Such a drawing has practical applications in VLSI floorplanning. We also give a linear-time algorithm to find such a drawing. We furthermore present a sufficient condition for a plane graph to be a good slicing graph, and give a linear-time algorithm to find a tree-structure of slicing paths for a graph satisfying the condition.

We propose a two-phase heuristic for crossing reduction in circular layouts. While the first algorithm uses a greedy policy to build a good initial layout, an adaptation of the sifting heuristic for crossing reduction in layered layouts is used for local optimization in the second phase. Both phases are conceptually simpler than previous heuristics, and our extensive experimental results indicate that they also yield fewer crossings. An interesting feature is their straightforward generalization to the weighted case.

Let

p

≥ 1 and

q

≥ 0 be integers. A family of sets

${\mathcal F}$

is

(p

,q

)-intersecting

when every subfamily

${\mathcal F}' \subseteq {\mathcal F}$

formed by

p

or less members has total intersection of cardinality at least

q

. A family of sets

${\mathcal F}$

is

(p

,q

)-Helly

when every (

p

,

q

)-intersecting subfamily

${\mathcal F}' \subseteq {\mathcal F}$

has total intersection of cardinality at least

q

. A graph

G

is a

(p

,q

)-clique-Helly graph

when its family of (maximal) cliques is (

p

,

q

)-Helly. According to this terminology, the usual Helly property and the clique-Helly graphs correspond to the case

p

=2,

q

=1. In this work we present a characterization for (

p

,

q

)-clique-Helly graphs. For fixed

p

,

q

, this characterization leads to a polynomial-time recognition algorithm. When

p

or

q

is not fixed, it is shown that the recognition of (

p

,

q

)-clique-Helly graphs is NP-hard.

We study the following

NP

-hard graph augmentation problem: Given a weighted graph

G

and a connected spanning subgraph

H

of

G

, find a minimum weight set of edges of

G

to be added to

H

so that

H

becomes 2-edge-connected. We provide a formulation of the problem as a set covering problem, and we analyze the conditions for which the linear programming relaxation of our formulation always gives an integer solution. This yields instances of the problem that can be solved in polynomial time. As we will show in the paper, these particular instances have not only theoretical but also practical interest, since they model a wide range of survivability problems in communication networks.

Assume that each vertex of a graph

G

is assigned a nonnegative integer weight and that

l

and

u

are nonnegative integers. One wish to partition

G

into connected components by deleting edges from

G

so that the total weight of each component is at least

l

and at most

u

. Such an “almost uniform” partition is called an

$(l, u) \mbox{-}$

partition. We deal with three problems to find an

$(l, u) \mbox{-}$

partition of a given graph. The minimum partition problem is to find an

$(l, u) \mbox{-}$

partition with the minimum number of components. The maximum partition problem is defined similarly. The

p

-partition problem is to find an

$(l, u) \mbox{-}$

partition with a fixed number

p

of components. All these problems are NP-complete or NP-hard even for series-parallel graphs. In this paper we show that both the minimum partition problem and the maximum partition problem can be solved in time

O

(

u

4

n

) and the

p

-partition problem can be solved in time

O

(

p

2

u

4

n

) for any series-parallel graph of

n

vertices. The algorithms can be easily extended for partial

k

-trees, that is, graphs with bounded tree-width.

We consider a weighted version of the subcoloring problem that we call the hypocoloring problem: given a weighted graph

G

=(

V

,

E

;

w

) where

w

(

v

)≥ 0, the goal consists in finding a partition

${\cal S}=(S_1,\ldots,S_k)$

of the node set of

G

into hypostable sets and minimizing ∑

$_{i=1}^{k}$

w

(

S

i

) where an hypostable

S

is a subset of nodes which generates a collection of node disjoint cliques

K

. The weight of

S

is defined as max { ∑ 

v

 ∈ 

K

w

(

v

)|

K

 ∈ 

S

}. Properties of hypocolorings are stated; complexity and approximability results are presented in some graph classes. The associated decision problem is shown to be

NP-complete

for bipartite graphs and triangle-free planar graphs with maximum degree 3. Polynomial algorithms are given for graphs with maximum degree 2 and for trees with maximum degree Δ.

In cooperative game theory, a characterization of games with stable cores is known as one of the most notorious open problems. We study this problem for a special case of the minimum coloring games, introduced by Deng, Ibaraki & Nagamochi, which arises from a cost allocation problem when the players are involved in conflict. In this paper, we show that the minimum coloring game on a perfect graph has a stable core if and only if every vertex of the graph belongs to a maximum clique. We also consider the problem on the core largeness, the extendability, and the exactness of minimum coloring games.