The maximum cardinality search (MCS) algorithm works as follows. Given a weighted graph $G = (V, E)$ where $w(u, v)$ denotes the weight of the edge $\{u, v\}$, we select a start node $a \in V$ and do the following:

  • Set $A = \{a\}$.
  • While $A \ne V$:
    • Choose a node $v \in V - A$ adjacent to at least one node in $A$ maximizing $\sum_{u \in A, \{u, v\} \in E} w(u, v)$.
    • Add $v$ to $A$ (set $A := A \cup \{v\})$.

Maximum cardinality search has applications in finding chordal graphs and as a substep in the Stoer-Wagner global min cut algorithm.

The structure of MCS is similar to the procedures used by Prim's algorithm and Dijkstra's algorithm - we begin with a single node in a set $A$, then iteratively and greedily expand that set by picking a node adjacent to $A$ optimizing some quantity and add it to $A$ until we're done.

One of the ways we can show correctness of Prim's algorithm or Dijkstra's algorithm is to argue that as $A$ is built up through the course of the algorithm, it is optimal with regards to some quantity. For example:

  • In each step of Prim's algorithm, the set $A$ is, of all subsets $X \subseteq V$ of cardinality $|A|$ containing the source node $a$, the one that induces the subgraph $G[X]$ with the least-cost MST.

  • In each step of Dijkstra's algorithm, the set $A$ is, of all subsets $X \subseteq V$ of cardinality $|A|$ containing the source node $a$, the one whose longest shortest paths in $G[X]$ has minimum length.

I've been trying to find some sort of similar invariant maintained by MCS. Specifically, I'd like to be able to say something like this for some function $F$:

In each step of MCS, the set $A$ is, of all subsets $X \subseteq V$ of cardinality $|A|$ containing the source node $a$, the one for which $F(G[X])$ is maximum.

However, I can't seem to find a quantity that MCS actually maximizes. Here are some ideas I tried that didn't pan out:

  • Because MCS greedily adds nodes to $A$ based on the sum of the edge costs crossing into $A$, I thought that, perhaps, the set $A$ has the highest sum of edge costs among all comparable sets. However, this can be shown to be false with a simple line graph counterexample.
  • Because MCS is used as a subroutine in the Stoer-Wagner algorithm for finding minimum cuts, I considered that MCS might build a set $A$ that represents some optimal cut containing the node $a$. However, this can be falsified simply by looking at the starting set $A = \{a\}$, which is not guaranteed to be a minimum cut of any sort.

The literature I've seen on MCS mostly looks at applications in network detection or in the recognition of chordal graphs, where the concern is less about greedily optimizing some quantity and more about looking at the connectivity strengths of each added node.

Is MCS known to optimize some quantity at each step?

  • $\begingroup$ I'm not sure whether this is relevant. Running MCS on a chordal graph $G$ is equivalent to running Prim’s algorithm on the weighted clique graph of $G$ (dx.doi.org/10.1007/3-540-60618-1_88), looking for a maximum-cost spanning tree. $\endgroup$
    – Yixin Cao
    May 28, 2020 at 6:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.