CS614. Advanced Algorithms. L02 Quiz.

CS614. Advanced Algorithms.

L02 Solutions

Problem 1. Identify the Circuits

Let $G$ be a simple, undirected, and connected graph. Consider the graphic matroid discussed in class, i.e, where:

the universe $U$ is the set of edges of $G$ , i.e, $E(G)$ ;
the family $\mathcal{F}$ of independent sets is the collection of all subsets of edges that are acyclic.

A maximal independent set in a matroid is called a basis, and for this example, the maximal independent sets correspond to spanning trees.

A minimal dependent set in a matroid is called a circuit. In this example, what are the circuits?

Solution

The circuits of the graphic matroid are the cycles of the graph $G$ .

Problem 2. Matchings

Let $G$ be a simple, undirected, and connected graph. Consider the following set system:

the universe $U$ is the set of edges of $G$ , i.e, $E(G)$ ;
the family $\mathcal{F}$ of independent sets is the collection of all subsets of edges that are matchings.

Is this a matroid? Why or why not? Justify your answer.

Solution

Not a matroid: consider the graph on the vertex set $\{a,b,c,d\}$ with the edges $\{ab, cd, ad\}$ .

There are two matchings in this instance:

$M_1 := \{ab,cd\}$
$M_2: \{ad\}$

However, although $|M_1| > |M_2|$ , neither of the edges from $M_1$ can be added to $M_2$ .

Problem 3. Independent Sets

Let $G$ be a simple, undirected, and connected graph. Consider the following set system:

the universe $U$ is the set of vertices of $G$ , i.e, $V(G)$ ;
the family $\mathcal{F}$ of independent sets is the collection of all subsets $S$ of that are independent in $G$ , i.e, the subgraph $G[S]$ has no edges.

Is this a matroid? Why or why not? Justify your answer.

Solution

Not a matroid: consider the graph on the vertex set $\{a,b,c\}$ with the edges $\{ab, ac\}$ . There are two independent sets: $S_1 := \{b,c\}$ and $M_2: \{a\}$ , but neither of the vertices from $S_1$ can be added to $S_2$ .

If the independent sets formed a matroid the problem of finding a maximum independent set would not be NP-complete.

— Comment in class