Unweighted KSG reduction of the independent set problem

This page contains examples from the paper, "Computer-Assisted Gadget Design and Problem Reduction of Unweighted Maximum Independent Set".

using UnitDiskMapping, Graphs # for mapping graphs to a King's subgraph (KSG)
using GenericTensorNetworks # for solving the maximum independent sets
using GenericTensorNetworks.ProblemReductions

Example 1: The 5-vertex graph

The five vertex demo graph in the paper.

Step 1: Prepare a source graph.

the demo graph in the main text

function demograph()
    g = SimpleGraph(5)
    for (i, j) in [(1, 2), (2, 4), (3, 4), (1, 3), (4, 5), (1, 5)]
        add_edge!(g, i, j)
    end
    return g
end

g5 = demograph()

show_graph(g5)

Step 2: Map the source graph to an unweighted King's subgraph (KSG)

The vertex order is optimized with the Branching path decomposition algorithm (MinhThi's Trick)

g5res = UnitDiskMapping.map_graph(g5; vertex_order=MinhThiTrick())

MappingResult{UnWeightedNode}(GridGraph{UnWeightedNode} (radius = 1.5)
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ● ● ● ⋅ ● ● ● ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ● ● ● ● ● ● ● ● ⋅ ● ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ , UnitDiskMapping.CopyLine[UnitDiskMapping.CopyLine 4: vslot → [1:1,1], hslot → [1,1:5], UnitDiskMapping.CopyLine 1: vslot → [2:2,2], hslot → [2,2:5], UnitDiskMapping.CopyLine 5: vslot → [1:3,3], hslot → [3,3:3], UnitDiskMapping.CopyLine 3: vslot → [1:3,4], hslot → [3,4:4], UnitDiskMapping.CopyLine 2: vslot → [1:3,5], hslot → [3,5:5]], 2, Tuple{Pattern, Int64, Int64}[(⋅ ◆ ⋅ ⋅ 
◆ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
● ⋅ ● ⋅ 
⋅ ● ⋅ ⋅ , 7, 18), (⋅ ◆ ⋅ 
◆ ◉ ● 
⋅ ● ⋅ 
  ↓
⋅ ● ⋅ 
● ● ● 
⋅ ● ⋅ , 7, 14), (⋅ ◆ ⋅ 
◆ ◉ ● 
⋅ ● ⋅ 
  ↓
⋅ ● ⋅ 
● ● ● 
⋅ ● ⋅ , 7, 10), (⋅ ● ⋅ ⋅ 
⋅ ● ● ⋅ 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ , 11, 18), (◆ ⋅ 
⋅ ◆ 
 ↓
● ⋅ 
⋅ ● , 4, 18), (⋅ ● ⋅ ⋅ 
⋅ ● ● ⋅ 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ , 11, 14), (⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ 
◆ ● ● 
⋅ ◆ ⋅ 
  ↓
⋅ ⋅ ⋅ 
⋅ ● ⋅ 
● ⋅ ● 
⋅ ● ⋅ , 2, 14), (⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ 
◆ ● ● 
⋅ ◆ ⋅ 
  ↓
⋅ ⋅ ⋅ 
⋅ ● ⋅ 
● ⋅ ● 
⋅ ● ⋅ , 2, 10), (⋅ ● ⋅ ⋅ 
⋅ ● ● ⋅ 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ , 11, 10), (⋅ ⋅ ⋅ ⋅ 
⋅ ● ● ● 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ● 
⋅ ⋅ ⋅ ⋅ , 3, 3), (⋅ ⋅ ⋅ ⋅ 
⋅ ● ● ● 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ● 
⋅ ⋅ ⋅ ⋅ , 3, 5), (⋅ ⋅ ⋅ ⋅ 
⋅ ● ● ● 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ● 
⋅ ⋅ ⋅ ⋅ , 3, 7), (⋅ ⋅ ⋅ ⋅ 
⋅ ● ● ● 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ● 
⋅ ⋅ ⋅ ⋅ , 7, 7), (⋅ ● ⋅ 
⋅ ● ⋅ 
⋅ ● ⋅ 
⋅ ⋅ ⋅ 
  ↓
⋅ ● ⋅ 
⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ , 9, 10), (⋅ ● ⋅ 
⋅ ● ⋅ 
⋅ ● ⋅ 
⋅ ⋅ ⋅ 
  ↓
⋅ ● ⋅ 
⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ , 9, 14), (⋅ ● ⋅ 
⋅ ● ⋅ 
⋅ ● ⋅ 
⋅ ⋅ ⋅ 
  ↓
⋅ ● ⋅ 
⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ , 9, 18)], 12)

Visualize the mapped KSG graph in terminal

print(g5res.grid_graph)

GridGraph{UnWeightedNode} (radius = 1.5)
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ● ● ● ⋅ ● ● ● ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ● ● ● ● ● ● ● ● ⋅ ● ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅

or in a plotting plane

show_graph(g5res.grid_graph)

Step 3: Solve the MIS size of the mapped graph

The independent set size can be obtained by solving the SizeMax() property using the generic tensor network method.

missize_g5_ksg = solve(GenericTensorNetwork(IndependentSet(SimpleGraph(g5res.grid_graph))), SizeMax())[]

15.0ₜ

The predicted MIS size for the source graph is:

missize_g5_ksg.n - g5res.mis_overhead

3.0

One of the best solutions can be obtained by solving the SingleConfigMax() property.

mis_g5_ksg = solve(GenericTensorNetwork(IndependentSet(SimpleGraph(g5res.grid_graph))), SingleConfigMax())[].c.data

0011010100110011010100110010110

Plot the solution

show_config(g5res.grid_graph, mis_g5_ksg)

Step 4: Map the KSG solution back

In the following, we will show how to obtain an MIS of the source graph from that of its KSG reduction.

mis_g5 = UnitDiskMapping.map_config_back(g5res, collect(mis_g5_ksg))

5-element Vector{Int64}:
 0
 1
 1
 0
 1

Show that the overhead in the MIS size is correct

Verify the result:

the extracted solution is an independent set

UnitDiskMapping.is_independent_set(g5, mis_g5)

true

and its size is maximized

count(isone, mis_g5)

solve(GenericTensorNetwork(IndependentSet(g5)), SizeMax())[].n

3.0

Example 2: The Petersen graph

We just quickly go through a second example, the Petersen graph.

petersen = smallgraph(:petersen)

show_graph(petersen)

We first map it to a grid graph (unweighted).

petersen_res = UnitDiskMapping.map_graph(petersen)

MappingResult{UnWeightedNode}(GridGraph{UnWeightedNode} (radius = 1.5)
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ● ● ● ⋅ ● ● ● ● ● ● ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ● ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ● ● ● ● ● ● ● ● ● ● ⋅ ● ● ● ● ● ● ● ⋅ ● ⋅ ⋅ ● ⋅ ● ● ⋅ ● ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ● ● ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ● ● ● ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ● ● ⋅ ⋅ ● ⋅ ⋅ ● ● ● ⋅ ● ● ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ● ● ⋅ ● ● ● ⋅ ● ● ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ⋅ ● ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ● ● ⋅ ● ● ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ● ⋅ ● ● ● ● ● ● ● ● ● ● ● ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ● ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ , UnitDiskMapping.CopyLine[UnitDiskMapping.CopyLine 10: vslot → [1:1,1], hslot → [1,1:6], UnitDiskMapping.CopyLine 9: vslot → [2:2,2], hslot → [2,2:7], UnitDiskMapping.CopyLine 8: vslot → [1:3,3], hslot → [3,3:8], UnitDiskMapping.CopyLine 7: vslot → [1:4,4], hslot → [4,4:9], UnitDiskMapping.CopyLine 6: vslot → [2:5,5], hslot → [5,5:10], UnitDiskMapping.CopyLine 5: vslot → [1:6,6], hslot → [6,6:10], UnitDiskMapping.CopyLine 4: vslot → [1:6,7], hslot → [1,7:8], UnitDiskMapping.CopyLine 3: vslot → [1:3,8], hslot → [2,8:9], UnitDiskMapping.CopyLine 2: vslot → [1:4,9], hslot → [1,9:10], UnitDiskMapping.CopyLine 1: vslot → [1:6,10], hslot → [2,10:10]], 2, Tuple{Pattern, Int64, Int64}[(⋅ ● ⋅ ⋅ 
⋅ ● ● ⋅ 
⋅ ● ● ⋅ 
⋅ ● ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ , 7, 38), (◆ ⋅ 
⋅ ◆ 
 ↓
● ⋅ 
⋅ ● , 4, 38), (⋅ ◆ 
◆ ⋅ 
 ↓
⋅ ● 
● ⋅ , 23, 38), (⋅ ◆ ⋅ ⋅ 
◆ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
● ⋅ ● ⋅ 
⋅ ● ⋅ ⋅ , 19, 38), (⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ● ● 
⋅ ● ● ⋅ 
⋅ ● ⋅ ⋅ 
   ↓
⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ● 
⋅ ⋅ ● ⋅ 
⋅ ● ⋅ ⋅ , 3, 34), (⋅ ◆ ⋅ ⋅ 
◆ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
● ⋅ ● ⋅ 
⋅ ● ⋅ ⋅ , 7, 34), (⋅ ◆ 
◆ ⋅ 
 ↓
⋅ ● 
● ⋅ , 15, 34), (⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
⋅ ● ● ● 
⋅ ● ● ⋅ 
⋅ ● ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
⋅ ⋅ ● ⋅ 
⋅ ● ⋅ ● 
⋅ ⋅ ● ⋅ 
⋅ ● ⋅ ⋅ , 6, 30), (◆ ⋅ 
⋅ ◆ 
 ↓
● ⋅ 
⋅ ● , 4, 30), (⋅ ◆ 
◆ ⋅ 
 ↓
⋅ ● 
● ⋅ , 11, 30)  …  (⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
⋅ ● ● ● 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
⋅ ⋅ ● ⋅ 
⋅ ⋅ ⋅ ● 
⋅ ⋅ ⋅ ⋅ , 14, 14), (⋅ ⋅ ● ⋅ ⋅ 
● ● ◉ ● ● 
⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ● ⋅ ⋅ 
    ↓
⋅ ⋅ ● ⋅ ⋅ 
● ● ● ● ● 
⋅ ● ● ● ⋅ 
⋅ ⋅ ● ⋅ ⋅ , 11, 13), (⋅ ◆ ⋅ 
◆ ◉ ● 
⋅ ● ⋅ 
  ↓
⋅ ● ⋅ 
● ● ● 
⋅ ● ⋅ , 7, 14), (⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ 
◆ ● ● 
⋅ ◆ ⋅ 
  ↓
⋅ ⋅ ⋅ 
⋅ ● ⋅ 
● ⋅ ● 
⋅ ● ⋅ , 2, 14), (⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
⋅ ● ● ● 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
⋅ ⋅ ● ⋅ 
⋅ ⋅ ⋅ ● 
⋅ ⋅ ⋅ ⋅ , 10, 10), (⋅ ⋅ ● ⋅ ⋅ 
● ● ◉ ● ● 
⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ● ⋅ ⋅ 
    ↓
⋅ ⋅ ● ⋅ ⋅ 
● ● ● ● ● 
⋅ ● ● ● ⋅ 
⋅ ⋅ ● ⋅ ⋅ , 7, 9), (⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ 
◆ ● ● 
⋅ ◆ ⋅ 
  ↓
⋅ ⋅ ⋅ 
⋅ ● ⋅ 
● ⋅ ● 
⋅ ● ⋅ , 2, 10), (⋅ ⋅ ⋅ ⋅ 
⋅ ● ● ● 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ● 
⋅ ⋅ ⋅ ⋅ , 3, 3), (⋅ ⋅ ⋅ ⋅ 
⋅ ● ● ● 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ● 
⋅ ⋅ ⋅ ⋅ , 3, 5), (⋅ ⋅ ⋅ ⋅ 
⋅ ● ● ● 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ⋅ ⋅ ⋅ 
⋅ ⋅ ⋅ ● 
⋅ ⋅ ⋅ ⋅ , 3, 7)], 88)

The MIS size of the petersen graph is 4.

missize_petersen = solve(GenericTensorNetwork(IndependentSet(petersen)), SizeMax())[]

4.0ₜ

The MIS size of the mapped KSG graph is much larger

missize_petersen_ksg = solve(GenericTensorNetwork(IndependentSet(SimpleGraph(petersen_res.grid_graph))), SizeMax())[]

92.0ₜ

The difference in the MIS size is:

petersen_res.mis_overhead

88

Find an MIS of the mapped KSG and map it back an MIS on the source graph.

mis_petersen_ksg = solve(GenericTensorNetwork(IndependentSet(SimpleGraph(petersen_res.grid_graph))), SingleConfigMax())[].c.data

mis_petersen = UnitDiskMapping.map_config_back(petersen_res, collect(mis_petersen_ksg))

10-element Vector{Int64}:
 1
 0
 0
 1
 0
 0
 1
 1
 0
 0

The obtained solution is an independent set and its size is maximized.

UnitDiskMapping.is_independent_set(petersen, mis_petersen)

count(isone, mis_petersen)

4

The number printed should be consistent with the MIS size of the petersen graph.

Extension: ProblemReductions

Unit-disk mapping implements the unified interface for reduction in package ProblemReductions.jl as an extension.

Step 1: perform the problem reduction.

source_problem = IndependentSet(smallgraph(:petersen))

ProblemReductions.IndependentSet{Graphs.SimpleGraphs.SimpleGraph{Int64}, Int64, ProblemReductions.UnitWeight}(Graphs.SimpleGraphs.SimpleGraph{Int64}(15, [[2, 5, 6], [1, 3, 7], [2, 4, 8], [3, 5, 9], [1, 4, 10], [1, 8, 9], [2, 9, 10], [3, 6, 10], [4, 6, 7], [5, 7, 8]]), [1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

the Independent set problem with 2D GridGraph topology, unweighted.

target_problem_type = IndependentSet{ProblemReductions.GridGraph{2}, Int, UnitWeight}

ProblemReductions.IndependentSet{ProblemReductions.GridGraph{2}, Int64, ProblemReductions.UnitWeight}

the result not only contains the target problem, but also the intermediate information

reduction_result = reduceto(target_problem_type, source_problem)

target_problem(reduction_result)

ProblemReductions.IndependentSet{ProblemReductions.GridGraph{2}, Int64, ProblemReductions.UnitWeight}(ProblemReductions.GridGraph{2}([(8, 8), (8, 9), (4, 10), (8, 10), (9, 10), (3, 11), (5, 11), (6, 11), (7, 11), (8, 11)  …  (14, 39), (15, 39), (16, 39), (17, 39), (18, 39), (19, 39), (21, 39), (22, 39), (23, 39), (20, 40)], 1.5), [1, 1, 1, 1, 1, 1, 1, 1, 1, 1  …  1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

Step 2: solve the target problem.

get single maximum independent set of the mapped problem

config = solve(GenericTensorNetwork(target_problem(reduction_result)), SingleConfigMax())[].c.data

01000110100100001110000110101010100000111100000111101010100000001111100000000101101010101010001000000001011010001001010110010101000100010001001010111000001111000100011111000011110001010100011110001110101010101010100101

Step 3. Extract the solution back

extracted_config = extract_solution(reduction_result, config)

10-element Vector{Int64}:
 0
 0
 1
 0
 1
 1
 1
 0
 0
 0

finally, we check the validity of the solution.

UnitDiskMapping.is_independent_set(source_problem.graph, extracted_config)

true

This page was generated using Literate.jl.