Skip to content

Main content
Bookmark this: tool.io/random/independent-set-instance

Random Independent Set Instance Generator

Generate a simple graph with a planted independent set and Bernoulli edges outside that set; no maximum-cardinality claim is made.

Loading tool…

Description

Generate a simple graph with a planted independent set and Bernoulli edges outside that set; no maximum-cardinality claim is made.

A graph uses vertices and edges to represent relationships. Direction, duplicate handling, indexing, and traversal order affect its interpretation; returning a constructed graph together with a witness or calculated answer helps verify an algorithm.

Generate a simple graph with a planted independent set and Bernoulli edges outside that set; no maximum-cardinality claim is made.

When to use this tool

Use this generator to create reproducible independent set instance cases from the supplied model or bank. Inspect the returned evidence before using cases in a test or exercise.

How to use the tool and how it works

  1. Supply nodeCount, independentSetSize, edgeProbability in the field shapes below. Set seed when you need an explicit replay.
  2. Run the tool and correct any input error. For generated controls, distinguish a successful fixture containing an invalid case from failure to generate the fixture.
  3. Read nodes, edges, independentSet. Use the conventions below and keep answer-bearing fields separate when presenting an exercise.

Sample a planted independent vertex subset, then draw only edges having at least one endpoint outside it. Return the simple undirected graph and the planted vertices.1

Input fieldMeaning and unitsAccepted input
nodeCountNumber of vertices, labeled 0 through nodeCount - 1.Required. Safe integer; minimum 2; maximum 32.
independentSetSizeIndependent Set SizeRequired. Safe integer; minimum 0; maximum 32.
edgeProbabilityEdge ProbabilityRequired. Finite number; minimum 0; maximum 1.
seedOptional numeric seed; takes precedence over context randomness. Without either, use the fixed tool.io default seed.Optional. Safe integer.
Output fieldInterpretationReturned shape
nodesNodesRequired. Array of Safe integer; minimum 0.; maximum items 32.
edgesEdgesRequired. Array of Array of Safe integer; minimum 0.; minimum items 2; maximum items 2.; maximum items 496.
independentSetIndependent SetRequired. Array of Safe integer; minimum 0.; maximum items 32.
randomnessReplay metadata: source is seed or context; seed is the normalized 32-bit seed or null for a context source.Required. Object; no unknown keys.
randomness.seedOptional numeric replay seed; normalization and precedence are explained below.Required. Safe integer. or Null.
randomness.sourceSourceRequired. Text; one of "context", "seed".

An explicit safe-integer seed takes precedence over injected context randomness and is normalized to an unsigned 32-bit integer. With no seed and no context source, replay uses the fixed tool.io default seed. A context source must return finite values from zero inclusive to one exclusive; its advancing state must be retained separately. randomness records the source and normalized seed, or null for context. These generators are not cryptographic random sources.

json
{
  "input": {
    "nodeCount": 5,
    "independentSetSize": 3,
    "edgeProbability": 0.4,
    "seed": 42
  },
  "output": {
    "nodes": [
      0,
      1,
      2,
      3,
      4
    ],
    "edges": [
      [
        0,
        1
      ],
      [
        1,
        2
      ],
      [
        3,
        4
      ]
    ],
    "independentSet": [
      0,
      2,
      4
    ],
    "randomness": {
      "seed": 42,
      "source": "seed"
    }
  }
}

Limitations and assumptions

  • The witness size cannot exceed node count and is not a solved maximum independent-set size. Other independent sets can exist and the graph can be disconnected.
  • A replay requires the same complete input and implementation. Randomized construction does not guarantee uniform coverage of every feasible output; finite samples can repeat unless a distinct-selection rule is explicitly stated.
  • The field tables state structural bounds; cross-field constraints and bounded search or output budgets also apply. Unknown keys are rejected where the object contract disallows them. Input errors are distinct from null fields and deliberate invalid controls in a successful output.

Alternative or Complementary methods

For a supplied example, inspect the returned construction or delegated check directly. To evaluate a consumer, also test cases chosen for its own boundaries; a generated finite corpus does not establish exhaustive coverage.

References

  1. Tool behavior and example: Random Independent Set Instance Generator — tool.io

Similar or alternative tools

Support Tool.io