Graph Minors and algorithms The irrelevant vertex technique

Graph Minors and algorithms The irrelevant vertex technique
Algorithmic Graph Minors:
turning Combinatorics to Algorithms
Dimitrios M. Thilikos
Q
Department of Mathematics { 8
UoA - National and Kapodistrian University of Athens
Laboratoire d’Informatique, de Robotique et de Microelectronique de Montpellier
(LIRMM)
Montpellier, February 2, 2012
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 1/111 1Antichain: an in nite sequence on non- -comparable elements.
We say thatX is Well-Quasi-Ordered by if it has no in nite
antichain
Examples:
NI 2 is not W.Q.O. by set inclusion.
IN is not W.Q.O. by divisibility.
kIN is W.Q.O. by by component-wise ordering.
Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
LetX be a set and let \" be a partial ordering relation onX .
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 2/111 2We say thatX is Well-Quasi-Ordered by if it has no in nite
antichain
Examples:
NI 2 is not W.Q.O. by set inclusion.
IN is not W.Q.O. by divisibility.
kIN is W.Q.O. by by component-wise ordering.
Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
LetX be a set and let \" be a partial ordering relation onX .
Antichain: an in nite sequence on non- -comparable elements.
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 3/111 2Examples:
NI 2 is not W.Q.O. by set inclusion.
IN is not W.Q.O. by divisibility.
kIN is W.Q.O. by by component-wise ordering.
Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
LetX be a set and let \" be a partial ordering relation onX .
Antichain: an in nite sequence on non- -comparable elements.
We say thatX is Well-Quasi-Ordered by if it has no in nite
antichain
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 4/111 2Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
LetX be a set and let \" be a partial ordering relation onX .
Antichain: an in nite sequence on non- -comparable elements.
We say thatX is Well-Quasi-Ordered by if it has no in nite
antichain
Examples:
NI 2 is not W.Q.O. by set inclusion.
IN is not W.Q.O. by divisibility.
kIN is W.Q.O. by by component-wise ordering.
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 5/111 2The theory of Well-quasi-ordering was rst developed by
Graham Higman and Erd} os & Rado
under the name \ nite basis property"
Remind: This talk is about graphs and algorithms!
Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
General question: Given a setX and an ordering relation on it,
isX W.Q.O. by to?
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 6/111 3Remind: This talk is about graphs and algorithms!
Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
General question: Given a setX and an ordering relation on it,
isX W.Q.O. by to?
The theory of Well-quasi-ordering was rst developed by
Graham Higman and Erd} os & Rado
under the name \ nite basis property"
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 7/111 3Graph Minors and algorithms The irrelevant vertex technique
Well Quasi Ordering Theory
General question: Given a setX and an ordering relation on it,
isX W.Q.O. by to?
The theory of Well-quasi-ordering was rst developed by
Graham Higman and Erd} os & Rado
under the name \ nite basis property"
Remind: This talk is about graphs and algorithms!
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 8/111 3v
1 nv: vertex removal:
e
2 ne: edge removal:
e
3 =e: edge contraction
Minor Relation:
HG if H can be obtained from G after a sequence of the above operations
Graph Minors and algorithms The irrelevant vertex technique
The minor relation on Graphs
Graph Minors
We de ne 3 local operations on graphs:
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 9/111 4e
2 ne: edge removal:
e
3 =e: edge contraction
Minor Relation:
HG if H can be obtained from G after a sequence of the above operations
Graph Minors and algorithms The irrelevant vertex technique
The minor relation on Graphs
Graph Minors
We de ne 3 local operations on graphs:
v
1 nv: vertex removal:
Dimitrios M. Thilikos Department of Mathematics, UoA
Algorithmic Graph Minors: turning Combinatorics to Algorithms Page 10/111 4