# Matroid Intersection
## Ermiya, Yonggang, Sayan, Sagnik

**26 January**

**Question-1:** For bipartite matching or colorful spanning tree, can we get better than $n \sqrt{r}$ algorithm (in the rank query model)?

**Question-2:** For bipartite matching and matroid intersection, what happens if one uses push-relabel instead of blocking flow?
* Related paper: https://infoshako.sk.tsukuba.ac.jp/~databank/pdf/472.pdf
* Push-relabel algorithm: https://www.youtube.com/watch?v=0hI89H39USg
Also see: https://andrasfrank.web.elte.hu/cikkek/FrankJ62.PDF

**Question-3:** What do the current algorithms for arborescence and colorful spanning tree imply in the rank-query model for matroid intersection?

**Question-4:** Cerification of common independent set: How to certify efficiently that the common independent set has rank $r' < r$ when both matorids have rank $r$? (An easier question is to certify this in the communication complexity setting, where Alice has one matroid and Bob another.)
* The rank of the common independent set is contentious (rank according to which matroid?).
* For bipartite matching, it makes sense to talk about size instead of rank. It has a short certificate (size of the largest independent set).
* For colourful spanning tree, size is not a useful notion. Maybe: Certify that the smallest number of components of the largest (in terms of edges) colourful spanning forest is < 1?

**Comment on Question 4 (by Sagnik)** It would be useful to see what would be an NP certificate for colourful spanning tree first before trying to solve Question 4 (even for 2-party model). The question is the following: Alice has the graphic matroid, Bob has the colouring partition matroid. They are given a colourful spanning forest with (say) 2 connected components. They need to verify that there is no colourful spanning tree.

A usual pitfall in thinking about this is the following (I am use you are aware of this, just reiterating): Bob does not get to see the graph structure. For Bob, what he sees is a list of edge IDs and their colours with no information about how the edges are connected to the vertices. So Bob cannot simply take the forest and extent it to a tree.

I think this should be solvable by LP duality. But is there a more combinatorial one? (For example, for bipartite matching, it is just the maximum cardinality independent set).

**Question-5 (small question):** Value version of matroid intersection. CHECK: Greedy algorithm gives a 2-approximation with $\tilde O(n)$ queries. Can we do better than $n$ while not getting a significant hit in the approximation factor?

## Resources

1. https://www.youtube.com/watch?v=G27vjNQUoh4&list=PLXsmhnDvpjORcTRFMVF3aUgyYlHsxfhNL&index=1
2. Deeparnab's paper: https://arxiv.org/abs/1911.10765
3. Our paper: https://arxiv.org/pdf/2102.05548.pdf
4. Nice lecture notes by Rothvoss: https://sites.math.washington.edu/~rothvoss/514-fall-2023/NetworksAndCombOpt-Math514-Fall2023.pdf

-------------------------------------

**2 February**

**Question-6:** Let $U$ be the universe of all elements, and let $M_1$ and $M_2$ denote the two matroids with rank functions $r_1 : 2^{U} \rightarrow \mathbb{R}^+$ and $r_2 : 2^{U} \rightarrow \mathbb{R}^{+}$, respectively. Let $\mathcal{I}_1 \subseteq 2^{U}$ and $\mathcal{I}_2 \subseteq 2^{U}$ respectively denote the collections of independent sets, under $M_1$ and $M_2$. Then there is a duality theorem (see Lecture 9.8 above) which says that: $$\max_{I \in \mathcal{I}_1 \cap \mathcal{I}_2} |I| = \min_{X \subseteq U} \left(r_1(X) + r_2(U \setminus X)\right).$$

Now, define $f : 2^{U} \rightarrow \mathbb{R}^+$ such that $f(X) = r_1(X) + r_2(U \setminus X)$ for all $X \subseteq U$.

**Claim 1:** $f$ is a (non-monotone) submodular function.

Thus, if we just want to solve the "value version" of our problem, under rank-oracle queries, then this can be solved by minimizing a (non-monotone) submodular function under value-oracle queries. **Question:** What is query complexity of this latter problem? Is it known how to solve it using only $\tilde{O}(n)$ queries, where $n = |U|$? If not, then can we somehow use the fact that we are dealing with a very specific type of submodular function here?

**Comment:** Given $X$ that minimizes the RHS, can we quickly recreate an $I \in \mathcal{I}_1 \cap \mathcal{I}_2$ via the exchange graph? If the answer is no, then it is a sanity check that the value version might be easier.

**Comment:** The above duality theorem should resolve Question 4 from 26 January.

**Comment:** There is a black-box reduction in the communication setting, which says that deterministic communication complexity is at most NP-complexity and co-NP complexity. But for value version of the above question, both NP-complexity and co-NP-complexity $O(n)$. Hence, the deterministic communication complexity is at most $O(n^2)$.

**Question-7:** Suppose we wish to get $(1+\epsilon)$-approximation to matroid intersection (even in the weighted setting). The fractional version of this problem is just asking us to solve an implicit packing LP. So, some MWU based approach might be useful to attack this question.

**9 February**

**Summary of Push-Relable algorithm for intersection of two submodular systems (for the special case of our concern):**
* Link to paper: https://infoshako.sk.tsukuba.ac.jp/~databank/pdf/472.pdf

Let $S_1 \in \mathcal{I}_1$ and $S_2 \in \mathcal{I}_2$ be such that $S_2 \subseteq S_1$. The aim is to change $S_1$ and $S_2$ (make $S_1$ smaller and $S_2$ bigger) so that the three below invariants always hold and finally $S_1 = S_2$.
1. $S_1 \in \mathcal{I}_1$ and $S_2 \in \mathcal{I}_2$.
2. $S_2 \subseteq S_1$.
3. There exist an $X \subseteq U$ such that $|S_1| \geq r_1(X) + r_2(U \setminus X)$.

Start with a common independent set $S_2$ in $\mathcal{I}_1 \cap \mathcal{I}_2$ derived by greedy algorithm and extend it to a basis $S_1$ of $M_1$.

**Claim 1:** $(S_1, S_2)$ satisfies above conditions.

Now, define an auxiliary graph $G = (V, A)$ with respect to $(S_1, S_2)$ as follows:
\begin{eqnarray}
V &=& U \cup \{ s^-, s^+ \} \\
A &=& S^+ \cup S^- \cup A^1 \cup A^2 \\
S^+ &=& \{ (u,s^+) | u \in U \} \\
S^- &=& \{ (u,s^-) | u \in U - \text{span}_2(S_2) \} \\
A^1 &=& \{ (u,v) | u \in S_1, v \in \text{span}_1(S_1) - S_1, S_1 - u + v \in \mathcal{I}_1 \} \\
A^2 &=& \{ (u,v) | v \in S_2 , u \in \text{span}_2(S_2) - S_2, S_2 + u - v \in \mathcal{I}_2 \}
\end{eqnarray}
We call $d: V \rightarrow \mathbb{Z}_{\geq0}$ a *valid labeling* if $d(S^+) = n+2$, $d(s^-)=0$ and $d(u) \leq d(v) + 1$ for each $(u,v) \in A$. Initialy, we let $d(s^+) = n+2$, $d(s^-)=0$ and $d(v)=1$ for each $v \in U$.

Elements of $S_1 \setminus S_2$ are called *active vertices*.

We use two subroutines 'push' and 'relable':

Push(u, v): 
# is applicable when (u, v) is in A and u is active and d(u) = d(v) + 1
    If (u,v) in S^+:
        S_1 = S_1 - u
    Else If (u,v) in A^1:
        S_1 = S_1 - u + v
    Else If (u,v) in A^2:
        S_2 = S_2 + u - v
    Else If (u,v) in S^-:
        S_2 = S_2 + u

Relable(u): 
# is applicable when u is active and for every (u, v) in A we have d(u) <= d(v)
    d(u) = min{d(v) + 1 | (u,v) in A}

**Claim 2:** After each operation, desired conditions for $(S_1, S_2)$ remain satisfied.
**Claim 3:** After each operation, labeling $d$ remains valid (even when new edges are formed in the auxiliary graph).
**Claim 4:** for all $v \in V$ we have $d(v) \leq n+3$.
**Claim 5:** After a bunch of operations, if $S_1 = S_2$ then it is the optimal solution.

**Comment:** The main issue is the order of operations on vertices. There is a suggestion in the paper which leads to the termination after $O(n^3)$ pushes and $O(n^2)$ relabels. But, we care about the number of queries to the rank function here. Hence, we have to find some way that without revealing all of the edges of the auxiliary graph (which needs call to ran function) we can improve our current $(S_1, S_2)$.

**Question-8 (out of the blue):** We know that greedy algorithm gives us a $1/2$-approximate solution. What happens if we choose $k$ random permutations on the ground set and do greedy algorithm in all of them? For instance if $k=\Omega(\log n)$, can we say that with high probability we have a $3/4$-approximate solution?

---------------------------------

**Comment 1:** We might be able to get a fast approximation algorithm for weighted matroid intersection, using ideas from the Gupta-Peng paper on dynamic matching.
https://arxiv.org/pdf/1304.0378.pdf

Currently, the fastest algorithm for this problem returns $(1+\epsilon)$-approximation in $\tilde{O}(n r W)$ time, for weights in the range $[1, W]$. We might be able to improve this bound to $\tilde{O}(n r)$, with exponential dependency in $1/\epsilon$.
https://epubs.siam.org/doi/epdf/10.1137/1.9781611974331.ch33

--------------------------------------------------

**16 February**

Future directions:
(1) Remove the exponential in $(1/\epsilon)$-dependency from Gupta-Peng reduction.
(2) For unweighted matroid intersection, can we get $(1-\epsilon)$-approximation in $\tilde{O}_{\epsilon}(n)$ time, under independence oracle queries?
(3) Understand the Push-Relabel framework for matroid intersection.
(4) Formalize the current writeup in overleaf (and confirm whether it extends to both independence and rank oracle queries).

--------------------------------------------------------------------

**1 March**

https://epubs.siam.org/doi/epdf/10.1137/1.9781611974331.ch33

Question: Suppose that the element-weights come from $\{1, \ldots, W\}$ where $W$ is a constant. Can we have a reduction from unweighted to weighted setting that loses only $(1+\epsilon)$ factor in approximation ratio and constant factor (assuming $\epsilon$ and $W$ are constants) in runtime? The above paper might be a useful reference to check.

The paper below gives a weight-splitting based algorithm.
https://andrasfrank.web.elte.hu/cikkek/FrankJ6.PDF

-------------------------------------------------------

**8 March**