TU Wien:Algorithmics VU (Szeider)/Exam 2023-03-17

1. Planarity, A*, Randomized
   • Draw a simple planar graph with all vertices deg 4 or argue why it can’t be planar
   • For a complete bipartite graph, Km,n for which m and n can it be planar?
   • MAXSAT – you have k clauses who all have m variables, what is the expected number of satisfied clauses after one run of Johnsons algorithm?
   • Which is the lower bound for all formulas of satisfied clauses that you’ll always find?
2. 5 point question: dominating set with max. 9 neighbors, FPT algorithm with a lot of help because it's only 5 points – why is a > 10k instance a no instance, what does the algo do if it the graph has >10k vertices, what does it do if it has <10k vertices
3. Determine treewidth for given graph by lower and upper bound; argue why a graph with vertex cover k can’t have a treewidth higher than k
4. MILP for chronological graph, with adjecency matrix aij; directed graph; 2points for each formula:
   • no vertex connected to itself, if ij is an edge then ji can’t be, if ij and jk are edges then ik must exist
   • How can you design a MILP where the minima are solutions for a flipping thingy, where entries of a given matrix can be flipped by bij = 1-aij and you want to flip the least entries to get a chronological graph?
5. Canonical decomposition, exactly like old exam https://vowi.fsinf.at/images/f/f0/TU_Wien-Algorithmics_VU_%28Raidl%29_-_28-01-2021-exam.pdf
6. 5 point question: Sweep line, there was a graphical example:
   • What does the algo do at step b0?
   • What’s the order of lines at step x1, from top to bottom
   • Which intersection causes it to stop and at which point is this detected?
   • What exactly happens at a step s0 and what is the expected runtime if it’s stored in an AVL tree?