CS614. Advanced Algorithms. L04 Quiz.

CS614. Advanced Algorithms.

L04 Solutions

Back to the course page

Problem 1. Matroid Intersection Example

Consider a directed graph $D=(V, E \subseteq V \times V)$. A set $T \subseteq E$ is an arborescence (oriented forest) if:

1. $T$ does not contain a cycle (ignoring directions of edges).

2. Every vertex in $V$ has at most one incoming edge.

An arborescence $T$ with $|T|=n-1$ will have one incoming edge incident on each node except one. If we denote this special node as root, this is an oriented spanning tree as shown in the figure.

An example arborescence.

Consider the underlying undirected graph $G_D = (V,E)$ associated with $D$ (this is the graph obtained by “erasing the arrows” in $D$). Consider the universe given by $E$. Suggest two matroids ${\mathcal M}_1$ and ${\mathcal M}_2$ for which set of arborescences is given by the sets independent in both ${\mathcal M}_1$ and ${\mathcal M}_2$.

Hint: these are both matroids seen in class. Further, you might find it useful to partition $E$ into $|V|$ many parts as follows — the part $P_v$ contains all edges that are incoming arcs for the vertex $v$ in $D$. Can you define a matroid based on this partition?

Describe ${\mathcal M}_1$ and ${\mathcal M}_2$.

Solution

Take ${\mathcal M}_1$ to be the graphic matroid and ${\mathcal M}_2$ to be the partition matroid with all budgets set to one. Membership in the first matroid ensures that there are no underlying undirected cycles and membership in the second matroid ensures that every vertex in $V$ has at most one incoming edge.

Problem 2. Maker-Breaker Game

Two players take turns removing edges from an undirected graph until there are no edges left.

Player 2 wins if the edges they remove contains a spanning tree, player 1 wins if the set of edges they remove would disconnect the original graph.

1. Is it true that exactly one player wins this game? In other words, is the following statement true?

“It is NOT the case that after the game has been played, both players can claim a win.”

• Yes
• No

2. Which player wins on a path?

• Player 1
• Player 2

3. Which player wins on a complete graph?

• Player 1
• Player 2

4. Complete this sentence: player 2 has the winning strategy if and only if the graph contains BLANK.

(No marks for answering this question, take your best guess :) )

Heads Up

Part (3) was under-specified: the second player wins on complete graphs with at least four vertices but the first player has easy wins if the graph is an edge (a complete graph on two vertices) or a triangle (a complete graph on three vertices).

Grading note: everyone recieves a full grade for this question.

Solution

1. Suppose both players indeed win. Let us delete the edges chosen by the first player. What is left is: (a) the set of edges chosen by the second player and (b) a disconnected graph. But the second player also won, so this set contains a spanning tree. A graph cannot simultaneously admit a spanning tree and be disconnected, this is a contradiction when applied on the graph induced by the leftover edges.

2. Player 1 can choose any edge in the first step and he already wins.

3. Assume that the graph has at least four vertices. Player 2 wins because notice that no matter how the first player plays the first $(n-1)$ steps, it is not enough to disconnect the graph. By chosing edges carefully¹, Player 2 can ensure that (s)he has booked a spanning tree already within the first $(n-1)$ moves.

4. No spoilers on this one (yet).

Footnotes

1. This can be done, for example, by choosing an edge incident on the $i$-th vertex in the $i$-th move that connectes the $i$-th vertex to the subgraph built so far by the second player: it can be shown that this is doable.