5.88. cutset

DESCRIPTIONLINKSGRAPH
Origin

[FagesLal03]

Constraint

𝚌𝚞𝚝𝚜𝚎𝚝(πš‚π™Έπš‰π™΄_π™²πš„πšƒπš‚π™΄πšƒ,π™½π™Ύπ™³π™΄πš‚)

Arguments
πš‚π™Έπš‰π™΄_π™²πš„πšƒπš‚π™΄πšƒπšπšŸπšŠπš›
π™½π™Ύπ™³π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,𝚜𝚞𝚌𝚌-πšœπš’πš—πš,πš‹πš˜πš˜πš•-πšπšŸπšŠπš›)
Restrictions
πš‚π™Έπš‰π™΄_π™²πš„πšƒπš‚π™΄πšƒβ‰₯0
πš‚π™Έπš‰π™΄_π™²πš„πšƒπš‚π™΄πšƒβ‰€|π™½π™Ύπ™³π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(π™½π™Ύπ™³π™΄πš‚,[πš’πš—πšπšŽπš‘,𝚜𝚞𝚌𝚌,πš‹πš˜πš˜πš•])
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰₯1
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰€|π™½π™Ύπ™³π™΄πš‚|
πšπš’πšœπšπš’πš—πšŒπš(π™½π™Ύπ™³π™΄πš‚,πš’πš—πšπšŽπš‘)
π™½π™Ύπ™³π™΄πš‚.πš‹πš˜πš˜πš•β‰₯0
π™½π™Ύπ™³π™΄πš‚.πš‹πš˜πš˜πš•β‰€1
Purpose

Consider a digraph G with n vertices described by the π™½π™Ύπ™³π™΄πš‚ collection. Enforces that the subset of kept vertices of cardinality n-πš‚π™Έπš‰π™΄_π™²πš„πšƒπš‚π™΄πšƒ and their corresponding arcs form a graph without circuit.

Example
1,πš’πš—πšπšŽπš‘-1𝚜𝚞𝚌𝚌-{2,3,4}πš‹πš˜πš˜πš•-1,πš’πš—πšπšŽπš‘-2𝚜𝚞𝚌𝚌-{3}πš‹πš˜πš˜πš•-1,πš’πš—πšπšŽπš‘-3𝚜𝚞𝚌𝚌-{4}πš‹πš˜πš˜πš•-1,πš’πš—πšπšŽπš‘-4𝚜𝚞𝚌𝚌-{1}πš‹πš˜πš˜πš•-0

The 𝚌𝚞𝚝𝚜𝚎𝚝 constraint holds since the vertices of the π™½π™Ύπ™³π™΄πš‚ collection for which the πš‹πš˜πš˜πš• attribute is set to 1 correspond to a graph without circuit and since exactly one (πš‚π™Έπš‰π™΄_π™²πš„πšƒπš‚π™΄πšƒ=1) vertex has its πš‹πš˜πš˜πš• attribute set to 0.

Typical
πš‚π™Έπš‰π™΄_π™²πš„πšƒπš‚π™΄πšƒ>0
πš‚π™Έπš‰π™΄_π™²πš„πšƒπš‚π™΄πšƒβ‰€|π™½π™Ύπ™³π™΄πš‚|
|π™½π™Ύπ™³π™΄πš‚|>1
Symmetry

Items of π™½π™Ύπ™³π™΄πš‚ are permutable.

Usage

The article [FagesLal03] introducing the 𝚌𝚞𝚝𝚜𝚎𝚝 constraint mentions applications from various areas such that deadlock breaking or program verification.

Remark

The undirected version of the 𝚌𝚞𝚝𝚜𝚎𝚝 constraint corresponds to the minimum feedback vertex set problem.

Algorithm

The filtering algorithm presented inΒ [FagesLal03] uses graph reduction techniques inspired from Levy and LowΒ [LevyLow88] as well as from Lloyd, Soffa and WangΒ [LloydSoffaWang88].

Keywords

application area: deadlock breaking, program verification.

constraint type: graph constraint.

final graph structure: circuit, directed acyclic graph, acyclic, no loop.

problems: minimum feedback vertex set.

Arc input(s)

π™½π™Ύπ™³π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš—πš˜πšπšŽπšœ1,πš—πš˜πšπšŽπšœ2)

Arc arity
Arc constraint(s)
β€’ πš’πš—_𝚜𝚎𝚝(πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘,πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌)
β€’ πš—πš˜πšπšŽπšœ1.πš‹πš˜πš˜πš•=1
β€’ πš—πš˜πšπšŽπšœ2.πš‹πš˜πš˜πš•=1
Graph property(ies)
β€’ πŒπ€π—_𝐍𝐒𝐂𝐂≀1
β€’ 𝐍𝐕𝐄𝐑𝐓𝐄𝐗=|π™½π™Ύπ™³π™΄πš‚|-πš‚π™Έπš‰π™΄_π™²πš„πšƒπš‚π™΄πšƒ

Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

We use a set of integers for representing the successors of each vertex. Because of the arc constraint, all arcs such that the πš‹πš˜πš˜πš• attribute of one extremity is equal to 0 are eliminated; Therefore all vertices for which the πš‹πš˜πš˜πš• attribute is equal to 0 are also eliminated (since they will correspond to isolated vertices). The graph property πŒπ€π—_𝐍𝐒𝐂𝐂 ≀ 1 enforces the size of the largest strongly connected component to not exceed 1; Therefore, the final graph can't contain any circuit.

PartΒ (A) of FigureΒ 5.88.1 shows the initial graph from which we have chosen to start. It is derived from the set associated with each vertex. Each set describes the potential values of the 𝚜𝚞𝚌𝚌 attribute of a given vertex. PartΒ (B) of FigureΒ 5.88.1 gives the final graph associated with the Example slot. Since we use the 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 graph property, the vertices of the final graph are stressed in bold. The 𝚌𝚞𝚝𝚜𝚎𝚝 constraint holds since the final graph does not contain any circuit and since the number of removed vertices πš‚π™Έπš‰π™΄_π™²πš„πšƒπš‚π™΄πšƒ is equal to 1.

Figure 5.88.1. Initial and final graph of the 𝚌𝚞𝚝𝚜𝚎𝚝 set constraint
ctrs/cutsetActrs/cutsetB
(a) (b)