Greedy_VC_(via_maximal_matchings).ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyNxZyXw9QvLml99i+xr1jkN",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/tsourolampis/bu-cs630-fall23/blob/main/Greedy_VC_(via_maximal_matchings).ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Vertex cover\n",
        "\n",
        "A greedy algorithm for the vertex cover problem that provides a 2-approximation solution involves repeatedly selecting the edge with the highest degree nodes and adding both of these nodes to the vertex cover, until all edges are covered. Here's a basic outline of the algorithm:\n",
        "\n",
        "1. **Initialize** an empty vertex cover set `VC`.\n",
        "\n",
        "2. **While** there are edges not yet covered by the vertex cover:\n",
        "   - Select an edge $(u, v)$ where neither $u$ nor $v$ is already in `VC`.\n",
        "   - Add both  u and v to `VC`.\n",
        "\n",
        "3. **Return** the set `VC` as the vertex cover.\n",
        "\n",
        "This algorithm is a 2-approximation because, in the worst case, it adds both vertices of an edge to the cover, potentially doubling the number of vertices necessary. However, for every edge added, at least one of its vertices must be in any minimum vertex cover, ensuring that the size of the vertex cover found by this algorithm is at most twice the size of the minimum vertex cover.\n",
        "\n",
        "\n",
        "**Exercise:** Why do we choose both endpoints in the while loop instead of just one? Besides we only need an edge to be covered by at least one vertex.\n",
        "\n",
        "This greedy approach is simple and efficient, but it's important to note that the vertex cover problem is NP-hard, so finding the minimum vertex cover is computationally challenging for large graphs. The 2-approximation algorithm offers a practical solution with a guaranteed upper bound on its size relative to the optimal solution.\n",
        "\n",
        "\n",
        "### Theorem\n",
        "The greedy algorithm is a 2-approximation for vertex cover.\n",
        "\n",
        "### Proof\n",
        "\n",
        "The algorithm outputs a matching (a set of edges no two of which share an endpoint) that is  maximal; in other words, we cannot add any more edges to it. If we take both endpoints of those edges, we have a vertex cover.  Assuming the algorithm chose $k$ edges, the VC has size $2k$. Notice that _any_ vertex cover must have size at least $k$ nodes since we need to cover the edges in the matching, so we need at least one endpoint of each of these edges. In other words $OPT \\geq k$. This yields\n",
        "\n",
        "$$ |Output size| = 2k \\leq  2 \\cdot OPT. $$\n",
        "Thus, the algorithm is a 2-approximation. &#9632;\n"
      ],
      "metadata": {
        "id": "d5V6eF16TZ7Y"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import networkx as nx\n",
        "\n",
        "def greedy_vertex_cover(G):\n",
        "    \"\"\"\n",
        "    A 2-approximation greedy algorithm for the vertex cover problem.\n",
        "    \"\"\"\n",
        "    G = G.copy()\n",
        "    vertex_cover = set()\n",
        "\n",
        "    while G.edges():\n",
        "        # Pick an arbitrary edge\n",
        "        (u, v) = next(iter(G.edges()))\n",
        "        # Add both vertices to the vertex cover\n",
        "        vertex_cover.add(u)\n",
        "        vertex_cover.add(v)\n",
        "        G.remove_node(u)\n",
        "        G.remove_node(v)\n",
        "\n",
        "    return vertex_cover\n",
        "\n",
        "G = nx.Graph()\n",
        "G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)])\n",
        "VC = greedy_vertex_cover(G)\n",
        "\n",
        "print(VC)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "6y-Kkp-STYLB",
        "outputId": "c37c7312-ed54-407c-9c33-1ac035856c67"
      },
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "{1, 2, 3, 4}\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Let's see in practice why the single endpoint addition fails."
      ],
      "metadata": {
        "id": "W_c-TfVaWAI4"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def bad_greedy_VC(G):\n",
        "    G = G.copy()\n",
        "    vertex_cover = set()\n",
        "\n",
        "    while G.edges():\n",
        "        (u, v) = min(G.edges(), key=lambda edge: min(edge))\n",
        "        smaller_id_vertex = min(u, v)\n",
        "        vertex_cover.add(smaller_id_vertex)\n",
        "        G.remove_node(smaller_id_vertex)\n",
        "\n",
        "    return vertex_cover\n",
        "\n",
        "\n",
        "\n",
        "star_graph = nx.star_graph(19)\n",
        "relabel_mapping = {i: (i + 1) for i in range(19)}  # Peripheral nodes\n",
        "relabel_mapping[0] = 20  # Center node\n",
        "\n",
        "star_graph = nx.relabel_nodes(star_graph, relabel_mapping)\n",
        "\n",
        "\n",
        "bad_vertex_cover = bad_greedy_VC(star_graph)\n",
        "print(bad_vertex_cover)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DFW_3VVTVdrm",
        "outputId": "4df64485-cac4-43a4-f6d1-a8f0789f8950"
      },
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "VC = greedy_vertex_cover(star_graph)\n",
        "VC"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "oqki5_KqWL5r",
        "outputId": "daab4c63-a693-4552-e1a3-0ce9e066bf9a"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{2, 20}"
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "FiHB4bENWcPa"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}