Chapter XIII Clique Cover

Reducing in Kotlin

Kotlin's data classes and extension functions make it easy to express "the same problem from another angle."

01

Define a Graph as a set of vertices and a set of unordered edge pairs. Kotlin's Set<Set<Int>> is a fine, immutable representation for small problems.
```
data class Graph(val n: Int, val edges: Set<Set<Int>>) {
    fun adjacent(u: Int, v: Int) = setOf(u, v) in edges
}
```

The complement graph swaps "edge" and "non-edge." A one-line extension function turns the original problem into a graph-coloring problem.

fun Graph.complement(): Graph {
    val es = mutableSetOf<Set<Int>>()
    for (u in 0 until n) for (v in u + 1 until n)
        if (!adjacent(u, v)) es += setOf(u, v)
    return Graph(n, es)
}

Greedy coloring (Welsh–Powell) on the complement gives an upper bound on the clique cover number. Sort vertices by degree descending; assign the smallest color that doesn't clash with already-colored neighbors.

fun Graph.greedyColor(): IntArray {
    val color = IntArray(n) { -1 }
    val order = (0 until n).sortedByDescending { v ->
        edges.count { v in it }
    }
    for (v in order) {
        val used = (0 until n).filter { adjacent(v, it) && color[it] >= 0 }
                              .map { color[it] }.toSet()
        var c = 0
        while (c in used) c++
        color[v] = c
    }
    return color
}

Read off the clique cover by grouping vertices by color in the complement. Same color = independent set in complement = clique in original. The reduction is the algorithm.

fun Graph.cliqueCover(): List<List<Int>> {
    val color = complement().greedyColor()
    return color.withIndex()
        .groupBy({ it.value }, { it.index })
        .values.toList()
}

Grammar — Kotlin

Kotlin is Java with the rough edges sanded off — null safety in the type system, expression-flavored control flow, and extension functions that let you add methods to types you don't own.

data class C(val a: A): a data class — a value-typed record with auto-generated equals, hashCode, copy, and destructuring.
val x = ...: an immutable binding. Use `var` for mutable.
fun name(p: T): R: a function declaration. Type after the colon, return type after the `:` post-args.
fun T.method(): an extension function — adds method() to T without modifying T. Inside, `this` refers to the receiver.
setOf(a, b): an immutable set. Pair with mutableSetOf<T>() for a mutable one.
{ x -> body }: a lambda. Arg list before the arrow.
it: the implicit name of a single-arg lambda parameter — saves you from naming it.
x?.method(): safe call: if x is null, the whole expression evaluates to null instead of throwing.
(a..b): a range. Use `until` for exclusive: `0 until n`.

Extending Graph with a complement() function turns "swap edges and non-edges" into a one-line method on the type, even though Graph itself stays immutable.

data class Graph(val n: Int, val edges: Set<Set<Int>>)

fun Graph.complement(): Graph {
    val es = mutableSetOf<Set<Int>>()
    for (u in 0 until n) for (v in u + 1 until n) {
        val pair = setOf(u, v)
        if (pair !in edges) es += pair
    }
    return Graph(n, es)
}

val g = Graph(3, setOf(setOf(0, 1)))
g.complement().edges  // setOf(setOf(0, 2), setOf(1, 2))

Kotlin Playground — official, in-browser →