Tools for agents: Dependency graph transitive reduction

Simplify an acyclic dependency graph without changing reachability and return a retained-path witness for every redundant edge.

Connect with MCP

{
  "mcpServers": {
    "super-agent-tools": {
      "url": "https://app.getsupers.com/sites/agent-dependency-reduction/mcp"
    }
  }
}
Streamable HTTP · No API key · Stateless

Use this URL in any client supporting remote Streamable HTTP MCP. Calls return structured JSON; inputs are processed without persistence.

Call reduce_dependency_graph

Edges are ordered [prerequisite,dependent] pairs. Node IDs are nonempty unique strings; every endpoint must be listed. Duplicate edges, cycles and self-loops fail the entire call. Empty and disconnected graphs are valid; isolated nodes are preserved. The retained edges form the unique transitive reduction of the DAG: reachability is unchanged and no remaining edge can be removed without losing reachability. Each removed edge has a witness_path containing only retained edges, including both endpoints. Node and edge output order preserves input order; topological ties use FIFO discovery based on node and edge input order, rather than lexical order. Only reachability is preserved: direct-edge metadata, timing constraints, costs and edge-specific semantics are not modeled and must not be discarded on that basis. This is stateless graph analysis, not a scheduler mutation or permission change. Breadth-first searches may be expensive for large dense graphs.

Input and output schemas
{
  "name": "reduce_dependency_graph",
  "title": "Dependency graph transitive reduction",
  "description": "Remove transitively redundant DAG edges while preserving all reachability; explain each removal with a path in the retained graph.",
  "inputSchema": {
    "properties": {
      "nodes": {
        "items": {
          "type": "string"
        },
        "title": "Nodes",
        "type": "array"
      },
      "edges": {
        "items": {
          "maxItems": 2,
          "minItems": 2,
          "prefixItems": [
            {
              "type": "string"
            },
            {
              "type": "string"
            }
          ],
          "type": "array"
        },
        "title": "Edges",
        "type": "array"
      }
    },
    "required": [
      "nodes",
      "edges"
    ],
    "title": "reduce_dependency_graphArguments",
    "type": "object"
  },
  "outputSchema": {
    "additionalProperties": true,
    "title": "reduce_dependency_graphDictOutput",
    "type": "object"
  },
  "icons": null,
  "annotations": {
    "title": null,
    "readOnlyHint": true,
    "destructiveHint": false,
    "idempotentHint": true,
    "openWorldHint": false
  },
  "meta": null,
  "execution": null
}

Run the example to see the actual result.

HTTP alternative

POST https://app.getsupers.com/sites/agent-dependency-reduction/call
Content-Type: application/json

{
  "nodes": [
    "research",
    "build",
    "test",
    "publish"
  ],
  "edges": [
    [
      "research",
      "build"
    ],
    [
      "build",
      "test"
    ],
    [
      "test",
      "publish"
    ],
    [
      "research",
      "test"
    ],
    [
      "research",
      "publish"
    ],
    [
      "build",
      "publish"
    ]
  ]
}

The HTTP and MCP interfaces execute the same implementation. Validation errors are returned explicitly. See the tool notes above for its supported inputs and behavior.

Redundant DAG edges and retained path witnesses

Read the explanation

The input example has four nodes research, build, test and publish. Its six edges include the cyan chain research to build to test to publish and three gold shortcuts: research to test, research to publish and build to publish. Cyan edges grow along the chain. The source contract defines prerequisite to dependent pairs. This animation derives the stored input, not an actual service result. Research still reaches test through build; research reaches publish through build and test; build reaches publish through test. The gold shortcuts fade because their endpoints are connected by retained cyan paths. Six direct edges become three while reachability stays unchanged. This is the transitive reduction of the example acyclic graph. Direct edge costs, timing and special semantics are outside this claim. The page contract rejects cycles, duplicate edges, self loops and unknown endpoints, preserving isolated nodes and input order. Removed edges should have witness paths made only of retained edges. This is stateless analysis, not a scheduler mutation or permission change. The local snapshot lacks the shared application and executable service, so offline layout proof cannot establish actual HTTP or MCP output. No backend request is made.

Dependency Graph Transitive Reduction Mechanics

How does transitive reduction prune redundant dependency edges without altering execution reachability in a DAG?

In directed acyclic graphs representing workflows, a dependency edge (u, v) is transitively redundant if there is already an indirect directed path from u to v spanning two or more steps. For finite DAGs, the transitive reduction is uniquely defined and forms the minimal subgraph preserving identical reachability. This tool checks every candidate edge against an unweighted breadth-first search on the remaining graph, discarding edges that possess alternative routes while generating retained-path witnesses.

The algorithm only computes topological reachability over unweighted, unannotated directed edges. Any direct constraints attached to removed edges—such as specific concurrency permits, explicit transfer timeouts, manual approval gates, or execution costs—are not modeled and will be lost if edges are discarded purely based on topological redundancy.

Try a worked example

Click "Run tool" with the default pipeline of 4 nodes ('research', 'build', 'test', 'publish') and 6 edges. The tool identifies that 'research' can reach 'test' via 'build', 'test' reaches 'publish' directly, and 'research' reaches 'publish' through intermediate steps. The structured output displays retained_edge_count as 3 ('research' -> 'build', 'build' -> 'test', 'test' -> 'publish') and prunes 3 redundant shortcuts, pairing each removal with a verified witness path.

Uniqueness and Reachability Equivalence in DAGs

For any finite directed acyclic graph, the transitive reduction is unique and corresponds to a spanning subgraph that preserves the exact reachability relation (its transitive closure) with the fewest possible edges. Transitive reduction - Wikipedia

In a DAG, an edge between two vertices belongs to the transitive reduction if and only if there is no alternative directed path of length two or greater connecting them. Transitive reduction - Wikipedia

Witness Generation and Computational Complexity

The Python implementation performs a breadth-first search for each candidate edge (u, v) with that specific edge skipped. If a path still connects u to v, the edge is removed from the active set; a second search over the retained edges then extracts the exact sequence of surviving steps as an explanatory witness path.

While theoretical reductions can be evaluated using fast matrix multiplication matching transitive closure complexity, sparse graphs often rely on path searches from each vertex, which can become computationally intensive on dense structures. Transitive reduction - Wikipedia

Sources and further reading