5.176. k_cut

DESCRIPTIONLINKSGRAPH
Origin

E.Β Althaus

Constraint

πš”_𝚌𝚞𝚝(𝙺,π™½π™Ύπ™³π™΄πš‚)

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

Select some arcs of a digraph in order to have at least 𝙺 connected components (an isolated vertex, i.e.Β a vertex without any ingoing or outgoing arc, is counted as one connected component).

Example
3,πš’πš—πšπšŽπš‘-1𝚜𝚞𝚌𝚌-βˆ…,πš’πš—πšπšŽπš‘-2𝚜𝚞𝚌𝚌-{3,5},πš’πš—πšπšŽπš‘-3𝚜𝚞𝚌𝚌-{5},πš’πš—πšπšŽπš‘-4𝚜𝚞𝚌𝚌-βˆ…,πš’πš—πšπšŽπš‘-5𝚜𝚞𝚌𝚌-{2,3}

The πš”_𝚌𝚞𝚝 constraint holds since the graph corresponding to the π™½π™Ύπ™³π™΄πš‚ collection contains 3 connected components (i.e.,Β two connected components respectively involving vertices 1 and 4 and a third connected component containing the remaining vertices 2, 3 and 5), and since the first argument 𝙺 enforces to have at least 3 connected components.

Typical
|π™½π™Ύπ™³π™΄πš‚|>1
Symmetries
  • 𝙺 can be decreased to any value β‰₯1.

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

See also

common keyword: πš•πš’πš—πš”_𝚜𝚎𝚝_𝚝𝚘_πš‹πš˜πš˜πš•πšŽπšŠπš—πšœΒ (constraint involving set variables).

used in graph description: πš’πš—_𝚜𝚎𝚝.

Keywords

constraint arguments: constraint involving set variables.

constraint type: graph constraint.

filtering: linear programming.

final graph structure: connected component.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πš—πš˜πšπšŽπšœ1.πš’πš—πšπšŽπš‘=πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘βˆ¨πš’πš—_𝚜𝚎𝚝(πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘,πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌)
Graph property(ies)
𝐍𝐂𝐂β‰₯𝙺

Graph model

πš—πš˜πšπšŽπšœ1.πš’πš—πšπšŽπš‘=πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘ holds if πš—πš˜πšπšŽπšœ1 and πš—πš˜πšπšŽπšœ2 correspond to the same vertex. It is used in order to enforce keeping all the vertices of the initial graph. This is because an isolated vertex counts always as one connected component. Within the context of the Example slot, partΒ (A) of FigureΒ 5.176.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.176.1 gives the final graph associated with the example of the Example slot. The πš”_𝚌𝚞𝚝 constraint holds since we have at least 𝙺=3 connected components in the final graph.

Figure 5.176.1. Initial and final graph of the πš”_𝚌𝚞𝚝 set constraint
ctrs/k_cutActrs/k_cutB
(a) (b)