Fabrizio Frati Dipartimento di Informatica e Automazione Università degli Studi Roma Tre Tecniche...
-
Upload
bryce-tuton -
Category
Documents
-
view
219 -
download
7
Transcript of Fabrizio Frati Dipartimento di Informatica e Automazione Università degli Studi Roma Tre Tecniche...
Fabrizio Frati
Dipartimento di Informatica e Automazione
Università degli Studi Roma Tre
Tecniche Algoritmiche per Grafi e Reti
• 3 CREDITI
• I° periodo:• Lunedì 9:45-11:15 aula N13
• Contatti:• {angelini,gdb,frati,ratm}
@dia.uniroma3.it• Ricevimento: mercoledì dalle 17 alle 19
• II° periodo:• Venerdì 8:00-9:45 aula N7
• Struttura del Corso• ~ 8 seminari
• algoritmi, strutture dati, combinatorica, graph drawing…
• progetti a gruppi di 2 - 4 persone• problema di ricerca
• Materiale Didattico• slides• G. Di Battista, P. Eades, R. Tamassia, I.
G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, 1999. Prentice Hall.
ACM Computing Classification SystemA. General Literature
B. HardwareC. Computer System OrganizationD. SoftwareE. DataF. Theory of ComputationG. Mathematics of ComputingH. Information SystemsI. Computing MethodologiesJ. Computer Applications
ACM Computing Classification SystemC. Computer System Organization
1. Processor Architectures2. Computer-Communication Networks3. Application-Based Systems4. Performance of Systems5. Computer System Implementations
ACM Computing Classification SystemC. Computer System Organization
2. Computer-Communication Networks
2.1 Network Architectures2.2 Network Protocols2.3 Network Operations2.4 Distributed Systems2.5 LAN & WAN2.6 Internetworking
ACM Computing Classification SystemA. General Literature
B. HardwareC. Computer System OrganizationD. SoftwareE. DataF. Theory of ComputationG. Mathematics of ComputingH. Information SystemsI. Computing MethodologiesJ. Computer Applications
ACM Computing Classification SystemE. Data
1. Data Structures2. Data Storage Representations3. Data Encryption4. Coding and Information Theory5. Files
ACM Computing Classification SystemE. Data
1. Data Structures
1.1 Arrays1.2 Distributed Data Structures1.3 Graphs and Networks1.4 Lists, Stacks, and Queues1.5 Records1.6 Tables1.7 Trees
ACM Computing Classification SystemA. General Literature
B. HardwareC. Computer System OrganizationD. SoftwareE. DataF. Theory of ComputationG. Mathematics of ComputingH. Information SystemsI. Computing MethodologiesJ. Computer Applications
ACM Computing Classification SystemF. Theory of Computation
1. Computation by Abstract Devices2. Analysis of Algorithms and Problem
Complexity3. Logics and Meanings of Programs4. Mathematical Logic and Formal Languages
ACM Computing Classification SystemF. Theory of Computation
1. Computation by Abstract Devices
1.1 Models of Computation1.2 Complexity Measures and Completeness
1.2.1 Complexity Hierarchies1.2.2 Machine-Independent Complexity1.2.3 Reducibility and Completeness1.2.4 Relations among Complexity Classes
ACM Computing Classification SystemF. Theory of Computation
2. Analysis of Algorithms and Problem Complexity
2.1 Numerical Algorithms2.2 Non-numerical Algorithms and Problems
2.2.1 Complexity of Proof Procedures2.2.2 Computations on Discrete Structures2.2.3 Geometrical Problems2.2.4 Pattern Matching2.2.5 Routing and Layout2.2.6 Sequencing and Scheduling2.2.7 Sorting and Searching
ACM Computing Classification SystemA. General Literature
B. HardwareC. Computer System OrganizationD. SoftwareE. DataF. Theory of ComputationG. Mathematics of ComputingH. Information SystemsI. Computing MethodologiesJ. Computer Applications
ACM Computing Classification SystemG. Mathematics of Computing
1. Numerical Analysis2. Discrete Mathematics3. Probability and Statistics4. Mathematical Software
ACM Computing Classification SystemG. Mathematics of Computing
2. Discrete Mathematics2.1 Combinatorics
2.2 Graph Theory
2.3 Applications
2.1.1 Combinatorial Algorithms2.1.2 Counting Problems2.1.3 Generating Functions2.1.4 Permutations and Combinations2.1.5 Recurrences and Difference Equations
2.2.1 Graph Algorithms2.2.2 Graph Labeling…2.2.5 Path and Circuit Problems2.2.6 Trees
a world FULL of NP-hard problems
Problem: I want to travel among a set of cities driving the fewest possible number of KMs. IT’S DIFFICULT!!
Problem: I want to put a set of objects into some bags, knowing that each bag can not afford more than 10 KGs and trying to use as few bags as possible. IT’S DIFFICULT!!
How to Deal with NP-hard problems?
• Exact Algorithms
• Randomized Algorithms
• Approximation Algorithms
• Fixed-Parameter Tractable Algorithms
• …
Approximation Algorithms
Approximation Algorithms
• We want a solution “close” to the optimal one.
• Given a minimization problem Π, an algorithm is an α-approximation for Π if, for every instance I of Π, it outputs a solution SOL(I) such that
SOL(I)/OPT(I) ≤ α
Vertex Cover
• Problem: Given a graph G(V,E), find a minimum vertex cover, that is, a set V’ V such that every edge e E has an endvertex in V’.
NP-hard [Karp]
How to Guarantee an Approximation?
• We want an approximation algorithm for Vertex Cover.
• But computing the cost of an optimal solution is NP-HARD!!
LOWER BOUNDS!
• The cost of the solution produced by the algorithm should be compared with the cost of an optimal solution.
Lower Bound for Vertex Cover
• Given a graph G(V,E), a matching M is a set of edges M E such that no two edges share an endvertex.
• The size of a matching is a lower bound on the size of an optimal solution to Vertex Cover!
• A matching is maximal if no matching M’ exists such that M M’.
An Approximation Algorithm for Vertex
Cover
• Algorithm: Find a maximal matching M and output the set S of matched vertices
An Approximation Algorithm for Vertex
Cover• Theorem: The previous algorithm is a
2-approximation algorithm for Vertex Cover
• Proof: • S is a vertex cover, otherwhise the
matching would not be maximal.• OPT≥M, where M is the size of the
output maximal matching.• SOL=2M, as the number of matched
vertices is twice the size of the matching.
Approximation Algorithms:much more…
• Approximation schemes: (1+ε)-approx.
• Inapproximability results.
• Complexity classes, e.g., APX.
Fixed-Parameter Tractable Algorithms
Problem (optimization): Let G be a graph. Which is the minimum number of vertices whose deletion makes G planar?
Easy or Hard?
NP-hard [Lewis-Yannakakis ]
Problem (decision): Let G be a graph and k be an integer. Is there a set of k vertices whose deletion makes G planar?
Easy or Hard?
Polynomial • Easy O(nk+1) time algorithm for solving the
problem:• Consider every set of k vertices. Remove such vertices. Test the planarity of the resulting graph.• There are O(nk) such sets. Testing the planarity of an n-vertex graph takes O(n) time. Then, T(n,k)= O(nk) O(n) = O(nk+1)
Where is the trick?
Easy or Hard?
In the decision version, k is a constant parameter part of the input
An O(nk+1)-time algorithm, with k constant, is a polynomial-time algorithm.
But it is very slow
Fixed-Parameter Tractability
A problem is fixed-parameter tractable if it can be solved in f(k) nO(1) time, where k is a parameter of the problem, f is an arbitrary function, and nO(1) is a polynomial (not depending on k).
FPT algorithm for Vertex Cover
Theorem [Melhorn]: There is an O(2k n)-time algorithm for Vertex Cover.
Proof: Consider an instance (G,k).• There is a vertex cover with k=0 if and only
if G has no edge.• Consider any edge e=(u,v). Either u or v
belongs to any vertex cover S.• Consider both the case in which u S and the
case in which v S.
FPT algorithm for Vertex Cover
• u S -> S is a vertex cover of G if and only if S-{u} is a vertex cover of G-{u} -> solve the instance (G-{u}, k-1)
• v S -> S is a vertex cover of G if and only if S-{v} is a vertex cover of G-{v} -> solve the instance (G-{v}, k-1)
u
v v
u
FPT algorithm for Vertex Cover
• Time complexity T(n,k):• T(n,0) =
O(n) • T(n,k) = 2 T(n-1, k-1) +O(n) ≤ 2 T(n, k-1) +O(n) ≤
2 (2 T(n, k-2) +O(n)) +O(n) ≤
2 (2 (2 T(n, k-3) +O(n)) +O(n)) +O(n) ≤
2 (2 (2 (…(2 T(n, 0)+O(n)) + … +O(n)) +O(n)) +O(n) ≤
2k O(n) + (2k-1 + 2k-2 + 2k-3 + ... + 1) O(n) =2k O(n) + (2k - 1) O(n) = O(2k n)
Reduction RulesReduction rule : a rule (that is, a polynomial time algorithm) that transforms an instance (I,k) to an "equivalent and simpler” instance (I', k’).Equivalent: (I,k) is a YES instance if and only if (I', k') is a YES instance.
Simpler: |I'|<|I| or k'<k or I' has fewer occurrences of a particular substructure.
Another FPT algorithm for Vertex Cover
Theorem: There is an O(1.6181k n2)-time algorithm for Vertex Cover.
Proof: Consider an instance (G,k).• We apply the following two reduction rules:
• If G has a vertex u of degree 0, then let (G',k')=(G-{u},k).
• If G has a vertex u of degree 1, then let N(u) denote the set of neighbors of u (here |N(u)|=1). Add N(u) to S and let (G',k')=(G-{u,N(u)},k-1).
Another FPT algorithm for Vertex Cover
• If G has a vertex u of degree 0, then let (G',k')=(G-{u},k). Correctness: if S is a vertex cover of G and u is in S, then S-{u} is also a vertex cover of G, as u has no incident edge.
• If G has a vertex u of degree 1, then let N(u) denote the set of neighbors of u (here |N(u)|=1). Add N(u) to S and let (G',k')=(G-{u, N(u)},k-1). Correctness: if S is a vertex cover of G and u is in S, then S-{u} N(u) is also a vertex cover of G, as u has no other incident edge.
Another FPT algorithm for Vertex Cover
• If neither of the two rules can be applied, then every vertex has degree at least 2.
• Pick a vertex u. Any vertex cover of G contains either u or N(u). Thus, (G,k) is a YES instance if and only if (G-{u},k-1) or (G-N(u),k-|N(u)|) is.
FPT algorithm for Vertex Cover
• Time complexity T(n,k):• Since |N(u)|\geq 2,
• T(n,k) ≤ T(n,k-1)+ T(n,k-2)+O(n^2).
• The k-th number of the Fibonacci series tends to the golden ratio to the power of k.
• Fibonacci series: every number is the sum of the previous two xk =xk-1 +xk-2 +c.
• T(n,k)=Φk O(n2)=((1+√5)/2)k O(n2) = O(1.6181k n2).
Kernelization• Sometimes the reduction rules work till the
size of the problem is reduced really a lot. That is, after the reduction rules have been applied, the problem has size g(k), for some function k. In this case the problem has a g(k)-kernel.
• Kernel: given a problem and an instance (I,k), a kernel is an algorithm that outputs in polynomial time an instance (I',k') such that (a) (I',k') is a YES instance if and only if (I,k) is; (b) |I'|<g(k), and k'<g(k).
Kernelization• Theorem [Niedermaier]: Every fixed-parameter
tractable problem has a g(k)-kernel.• Proof: Suppose that there exists a FPT
algorithm with running time f(k) nc, for some function f and some constant c. Consider an instance (I,k) with |I|=n.
• If n>f(k), we run the decision algorithm in time f(k) nc < nc+1. If it returns YES (NO), the kernelization algorithm outputs a constant size YES (resp. NO) instance.
• If n≤f(k), the the kernelization algorithm returns (I,k).
Kernelization• The last theorem implies that every problem
that is FPT has a kernel. • However, the goal is to obtain kernels that
are "small", that is, polynomial in k, or even constant.
FPT: much more…• Some problems are not FPT (e.g., graph
coloring).• Complexity classes: W[1] -> Can a non-
deterministic Turing machine accept an unary string s in at most k steps? • Independent Set is W[1]-hard.• Reductions to W[1]-hard problems give
new W[1]-hard problems.• Lower bounds for FPT tractability• Upper and lower bounds for the size of the
kernels
FPT: much more…• Theorem [Robertson and Seymour]: Every graph
problem with parameter k whose YES istances are closed under taking minors can be solved in O(f(k) n3)