Tarjan's algorithm for finding a minimal set of equations

You are given a system consisting of a large number of equations (not necessarily linear), where you need to solve for only a few variables. How can you do this efficiently? What is the minimum set of equations you need? In this article, we will discuss graph representations of systems of equations, apply Tarjan's algorithm, and formalize the process in Python.

Formulation of the problem

Let's introduce a bipartite graph $G = (V_1 \cup V_2, \ E)$ . V_1 – a set of vertices representing equations, V_2 – vertices representing variables. Edge $e \in E$ connects steamif the equation depends on variable .

And we will use the adjacency matrix . By rows – equations, by columns – variables. If $M_{ij} = 1$ That -th equation depends on -variable.

$S:\left\{\begin{array}{cccc} f_1\left(x_1, x_2, \ldots, x_n\right) & = & 0 & e_1 \\ f_2\left(x_1, x_2, \ldots, x_n\right) & = & 0 & e_2 \\ \vdots & & & \\ f_n\left(x_1, x_2, \ldots, x_n\right) & = & 0 & e_n \end{array},\right.$

Find minimal subsystem $v_1 \subset V_1$ equations, by solving which one can find the variables $v_2 = \{x_i, x_j, \dots\} \subset V_2$ (arbitrary subset).

Formulation of the algorithm

The number of equations and variables must match for this algorithm to apply.

The following permutation of matrix rows is found that the main diagonal will have ones. In other words, this is a renumbering such that each variable enters the equation with the same number.

$M^{'} = \begin{pmatrix} 1 & a_{12} & \dots & a_{1n}\\ a_{21} & 1 & \dots & a_{2n} \\ \vdots & \vdots & \dots & a_{n - 1, n} \\ \dots & \dots & \dots & 1 \end{pmatrix}$

In fact, the problem is to reduce the matrix to the block lower triangular (BLT) form. We will do this with the help of Tarjan's algorithm, who will find strongly connected components (CSS) in a directed graph. A CSS is a subgraph such that for any pair of vertices A and B, there is a path from A to B and back – from B to A.

The key point is that the variable for which we want to find the minimum set of equations will be chosen as the starting vertex (for simplicity, we will assume for now that there is only one such variable). Then the algorithm will return the KSS in the order in which they are related to the desired variable, thus implicitly reducing the adjacency matrix to BNT form.

Hidden text

def tarjan_algorithm_with_start(graph: dict[int, set[int]], start_node: int):
    def dfs(v):
        nonlocal index
        indices[v] = index
        lowlink[v] = index
        index += 1
        stack.append(v)
        on_stack[v] = True

        for neighbor in graph[v]:
            if indices[neighbor] == -1:
                dfs(neighbor)
                lowlink[v] = min(lowlink[v], lowlink[neighbor])
            elif on_stack[neighbor]:
                lowlink[v] = min(lowlink[v], indices[neighbor])

        if indices[v] == lowlink[v]:
            scc = []
            while True:
                node = stack.pop()
                on_stack[node] = False
                scc.append(node)
                if node == v:
                    break
            strongly_connected_components.append(scc)

    index = 0
    stack = []
    indices = [-1] * len(graph)
    lowlink = [-1] * len(graph)
    on_stack = [False] * len(graph)
    strongly_connected_components = []

    dfs(start_node)

    return strongly_connected_components

If there are several variables to be found, then we add a new vertex (let's call it root), which will be connected by outgoing edges with the variables under study. Then the root vertex should be taken as the starting vertex. .

From the point of view of the system of equations, an auxiliary variable is added $r = f_r(x_1, \dots x_h)$ expressed as a certain function of the variables of interest to us.

Example

Utility functions:

Hidden text

import networkx as nx
import numpy as np
from matplotlib import pyplot as plt


def matr2dct(m):
    gr = {}
    num_nodes = m.shape[0]
    for i in range(num_nodes):
        neighbors = set(np.nonzero(m[i])[0])
        gr[i] = neighbors
    return gr


def colorGraph(matrix, scc):
    G = nx.DiGraph(matrix)
    pos = nx.spring_layout(G)
    colors = ['red', 'green', 'blue', 'yellow', 'orange', 'violet', 'pink']
    for component, color in zip(scc, colors):
        nx.draw_networkx_nodes(G, pos, nodelist=component, node_color=color, node_size=500)
    nx.draw_networkx_edges(G, pos, arrows=True)
    nx.draw_networkx_labels(G, pos)
    plt.axis('off')
    # plt.savefig('graph.png')
    plt.show()