Abstract: The 3-coloring problem is well known to be NP-complete. It is also well known that it
remains NP-complete when the input is restricted to graphs with diameter 4. Moreover, assuming
the Exponential Time Hypothesis (ETH), 3-coloring cannot be solved in time 2
o
(
n
)
on graphs with
n
vertices and diameter at most 4. In spite of the extensive studies of the 3-coloring problem with
respect to several basic parameters, the complexity status of this problem on graphs with small
diameter, i.e. with diameter at most 2, or at most 3, has been a longstanding and challenging open
question. In this paper we investigate graphs with small diameter. For graphs with diameter at most 2,
we provide the rst subexponential algorithm for 3-coloring, with complexity 2
O
(
p
n
log
n
)
, which is
asymptotically the same as the currently best known time complexity for the graph isomorphism
problem. Furthermore we extend the notion of an articulation vertex to that of an
articulation
neighborhood
, and we provide a polynomial algorithm for 3-coloring on graphs with diameter 2
that have at least one articulation neighborhood. For graphs with diameter at most 3, we establish
the complexity of 3-coloring, even for the case of triangle-free graphs. Namely we prove that for
every
"
2
[0
;
1), 3-coloring is NP-complete on triangle-free graphs of diameter 3 and radius 2 with
n
vertices and minimum degree
=
(
n
"
). Moreover, assuming ETH, we use three di erent ampli cation
techniques of our hardnessresults, in order to obtain for every
"
2
[0
;
1) subexponential asymptotic
lower bounds for the complexity of 3-coloring on triangle-free graphs with diameter 3 and minimum
degree
=
(
n
"
). Finally, we provide a 3-coloring algorithm with running time 2
O
(min
f
;
n
log
g
)
for
arbitrary graphs with diameter 3, where
n
is the number of vertices and
(resp.
) is the minimum
(resp. maximum) degree of the input graph. To the best of our knowledge, this algorithm is the rst
subexponential algorithm for graphs with
=
!
(1) and for graphs with
=
O
(1) and
=
o
(
n
).
Due to the above lower bounds of the complexity of 3-coloring, the running time of this algorithm is
asymptotically almost tight when the minimum degree of the input graph is
=
(
n
"
), where
"
2
[
1
2
;
1).
Abstract: The study of the path coloring problem is motivated by the allocation of optical bandwidth to communication requests in all-optical networks that utilize Wavelength Division Multiplexing (WDM). WDM technology establishes communication between pairs of network nodes by establishing transmitter-receiver paths and assigning wavelengths to each path so that no two paths going through the same fiber link use the same wavelength. Optical bandwidth is the number of distinct wavelengths. Since state-of-the-art technology allows for a limited number of wavelengths, the engineering problem to be solved is to establish communication minimizing the total number of wavelengths used. This is known as the wavelength routing problem. In the case where the underlying network is a tree, it is equivalent to the path coloring problem.
We survey recent advances on the path coloring problem in both undirected and bidirected trees. We present hardnessresults and lower bounds for the general problem covering also the special case of sets of symmetric paths (corresponding to the important case of symmetric communication). We give an overview of the main ideas of deterministic greedy algorithms and point out their limitations. For bidirected trees, we present recent results about the use of randomization for path coloring and outline approximation algorithms that find path colorings by exploiting fractional path colorings. Also, we discuss upper and lower bounds on the performance of on-line algorithms.
Abstract: We study the combinatorial structure and computational complexity of extreme Nash equilibria, ones that maximize or minimize a certain objective function, in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel links, to control the routing of its own assigned traffic. In a Nash equilibrium, each user routes its traffic on links that minimize its expected latency cost.
Our structural results provide substantial evidence for the Fully Mixed Nash Equilibrium Conjecture, which states that the worst Nash equilibrium is the fully mixed Nash equilibrium, where each user chooses each link with positive probability. Specifically, we prove that the Fully Mixed Nash Equilibrium Conjecture is valid for pure Nash equilibria and that under a certain condition, the social cost of any Nash equilibrium is within a factor of 6 + epsi, of that of the fully mixed Nash equilibrium, assuming that link capacities are identical.
Our complexity results include hardness, approximability and inapproximability ones. Here we show, that for identical link capacities and under a certain condition, there is a randomized, polynomial-time algorithm to approximate the worst social cost within a factor arbitrarily close to 6 + epsi. Furthermore, we prove that for any arbitrary integer k > 0, it is -hard to decide whether or not any given allocation of users to links can be transformed into a pure Nash equilibrium using at most k selfish steps. Assuming identical link capacities, we give a polynomial-time approximation scheme (PTAS) to approximate the best social cost over all pure Nash equilibria. Finally we prove, that it is -hard to approximate the worst social cost within a multiplicative factor . The quantity is the tight upper bound on the ratio of the worst social cost and the optimal cost in the model of identical capacities.
Abstract: In this work, we study the combinatorial structure and the
computational complexity of Nash equilibria for a certain game that
models selfish routing over a network consisting of m parallel links. We
assume a collection of n users, each employing a mixed strategy, which
is a probability distribution over links, to control the routing of its own
assigned traffic. In a Nash equilibrium, each user selfishly routes its traffic
on those links that minimize its expected latency cost, given the network
congestion caused by the other users. The social cost of a Nash equilibrium
is the expectation, over all random choices of the users, of the
maximum, over all links, latency through a link.
We embark on a systematic study of several algorithmic problems related
to the computation of Nash equilibria for the selfish routing game we consider.
In a nutshell, these problems relate to deciding the existence of a
Nash equilibrium, constructing a Nash equilibrium with given support
characteristics, constructing the worst Nash equilibrium (the one with
maximum social cost), constructing the best Nash equilibrium (the one
with minimum social cost), or computing the social cost of a (given) Nash
equilibrium. Our work provides a comprehensive collection of efficient algorithms,
hardnessresults (both as NP-hardness and #P-completeness
results), and structural results for these algorithmic problems. Our results
span and contrast a wide range of assumptions on the syntax of the
Nash equilibria and on the parameters of the system.
Abstract: In this work, we introduce the notion of time to some well-known combinatorial optimization problems. In particular, we study problems defined on temporal graphs. A temporal graph D=(V,A) may be viewed as a time-sequence G_1,G_2,...,G_l of static graphs over the same (static) set of nodes V. Each G_t = D(t) = (V,A(t)) is called the instance of D at time t and l is called the lifetime of D. Our main focus is on analogues of traveling salesman problems in temporal graphs. A sequence of time-labeled edges (e.g. a tour) is called temporal if its labels are strictly increasing. We begin by considering the problem of exploring the nodes of a temporal graph as soon as possible. In contrast to the positive results known for the static case, we prove that, it cannot be approximated within cn, for some constant c > 0, in general temporal graphs and within (2 − \varepsilon), for every constant \varepsilon > 0, in the special case in which D(t) is connected for all 1 <= t <= l, both unless P = NP. We then study the temporal analogue of TSP(1,2), abbreviated TTSP(1,2), where, for all 1 <= t <= l, D(t) is a complete weighted graph with edge-costs from {1,2} and the cost of an edge may vary from instance to instance. The goal is to find a minimum cost temporal TSP tour. We give several polynomial-time approximation algorithms for TTSP(1,2). Our best approximation is (1.7 + \varepsilon) for the generic TTSP(1,2) and (13/8 + \varepsilon) for its interesting special case in which the lifetime of the temporal graph is restricted to n. In the way, we also introduce temporal versions of Maximum Matching, Path Packing, Max-TSP, and Minimum Cycle Cover, for which we obtain polynomial-time approximation algorithms and hardnessresults.
