CHN10 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest

Author: ???
Tester: Kevin Atienza, Jingbo Shang
Editorialist: Kevin Atienza

PREREQUISITES:

Counting, combinatorics, graphs, isomorphism

PROBLEM:

Given a simple undirected graph with n nodes with the property that the degree of each node is \ge n-3, find the number of simple undirected graphs on the same set of nodes that are isomorphic to the given graph.

QUICK EXPLANATION:

Two simple graphs are isomorphic if and only if their complement graphs are isomorphic. The complement of a graph is just a graph such that for i \not= j, the edge (i,j) is in the complement if and only if it is not in the original graph.

The degree of each node in the complement is at most 2, so each connected component is only of three types:

  • A singleton.
  • A path.
  • A cycle.

Let s be the number of singletons and p_k and c_k be the number of paths and cycles of length k > 1, respectively. Then using some counting arguments, we can determine the answer to be n! divided by:

s!\prod_{k=2}^n\,(2k)^{c_k}\,2^{p_k}\,c_k!\,p_k!

s, p_k and c_k can all be computed with a single traversal of the complement graph. A component with L > 1 nodes can be determined to be a path or cycle depending on the number of edges E in it. If E = L, then it is a cycle, otherwise E = L - 1 and it is a path.

EXPLANATION:

That the problem deals with graph isomorphism makes one worry that the problem might be NP hard. However, we will see shortly that this problem is easier because of the property that each node has degree \ge n-3.

Such a graph has a lot of edges. In fact, each node is connected to all other nodes except for at most two nodes. This suggests to us that we should consider instead the complement of the input graph. We define the complement of a graph as the graph such that for i \not= j, the edge (i,j) is in the complement if and only if it is not in the original graph. Note that studying instead the complement is valid because of the following intuitive statement:

Two simple graphs are isomorphic if and only if their complement graphs are isomorphic.

Now, since each degree is \ge n-3, the degree of each node in the complement is \le 2. (This is because if a node has degree k, then it has degree n-1-k in the complement.) A graph such that each degree is \le 2 is actually very easy to characterize. Any branching occurs in a node with degree at least 3, so no branching can occur, and we can’t even form any interesting “tree”-like structure, even the simple ones. In fact, we can characterize each connected component of the graph easily:

A connected component where the degree of each node is \le 2 is either a path graph or a cycle graph.

You can show this by starting at some node in a connected component, and traversing both directions until they meet or find a dead end. You can show that among all the possible structures, only a path or a cycle can occur.

This is great, because the number of structures is now more manageable. We are left with at most 2n types of paths and cycles (one for each length of path and cycle). Notice that paths of the same length are isomorphic to one another (the same is true for cycles), so we only need to know the count of each length of path (and cycle). This makes the problem more amenable to counting techniques!

Furthermore, notice that a cycle of length 1 or 2 does not exist (because the graph is simple), so actually there are only 2n-2 types.

Counting problem

We’re now ready to count the number of graphs isomorphic to our graph consisting of paths and cycles. For our purposes, we only need to know the following values:

  • p_k, the number of paths of length k, and
  • c_k, the number of cycles of length k. (Note that c_1 = c_2 = 0.)

These values can be computed with a single traversal, and the only nontrivial part is figuring out whether a connected component just traversed is a cycle or a path. But this is easy too: if the number of edges is equal to the number of nodes, then it is a cycle, otherwise it is a path :slight_smile:

Okay, now we have n nodes, and we must structure these nodes so that we have the desired paths / cycles. The first thing is to do is to select which path / cycle each node will be in. This can be done straightforwardly using Multinomial coefficients:

\frac{n!}{1!^{c_1} \cdot 2!^{c_2} \cdot 3!^{c_3}\cdots n!^{c_n}\cdot 1!^{p_1} \cdot 2!^{p_2} \cdot 3!^{p_3}\cdots n!^{p_n}}\,\cdots

But there’s a problem with this. Note that paths of the same length should be indistinguishable from each other. This means that we need to divide further so that all possible orderings of paths/cycles among themselves are counted only once. The adjusted count is the following:

\frac{n!}{1!^{c_1} \cdot 2!^{c_2} \cdot 3!^{c_3}\cdots n!^{c_n}\cdot 1!^{p_1} \cdot 2!^{p_2} \cdot 3!^{p_3}\cdots n!^{p_n}}\cdot \frac{1}{c_1!c_2!\cdots c_n!\cdot p_1!p_2!\cdots p_n!}\,\cdots

At this point, let’s use the \prod notation to make it shorter:

\frac{n!}{\prod_{k=1}^n k!^{c_k}\, k!^{p_k}\, c_k!\, p_k!}\,\cdots

Now that we have selected which nodes will go to which components, it’s time to count how many ways to form the components themselves. Let’s look at a cycle of length k. How many distinct cycles on k nodes are there? If you will remember, there are (k-1)! ways to arrange k nodes in a circle. So this must also be the number of cycles… right? Actually, we need to divide by 2, because the direction (clockwise or counterclockwise) we place the nodes in a circle doesn’t matter!

What about paths? Well, this time there are k! ways to arrange k nodes in a line. But again, we must divide by 2 because the order we arrange the nodes in doesn’t matter again.

Finally, the case of a length-1 path must be handled separately. If we follow the formula above, then we’ll get \frac{1}{2} ways to create a length-1 path, which is clearly false. The actual number is simply 1.

Thus, the answer must be:

\frac{n!}{\prod_{k=1}^n k!^{c_k}\, k!^{p_k}\, c_k!\, p_k!}\cdot \prod_{k=2}^n \left(\frac{(k-1)!}{2}\right)^{c_k} \prod_{k=2}^n \left(\frac{k!}{2}\right)^{p_k}

By remembering that c_1 = 0, we can rearrange the above as follows:

\begin{aligned} &= \frac{n!}{c_1! \prod_{k=2}^n k!^{c_k}\, k!^{p_k}\, c_k!\, p_k!}\cdot \prod_{k=2}^n \left(\frac{(k-1)!}{2}\right)^{c_k} \prod_{k=2}^n \left(\frac{k!}{2}\right)^{p_k} \\\ &= \frac{n!}{c_1!} \prod_{k=2}^n \frac{1}{k!^{c_k}\, k!^{p_k}\, c_k!\, p_k!}\cdot \prod_{k=2}^n \left(\frac{(k-1)!}{2}\right)^{c_k} \prod_{k=2}^n \left(\frac{k!}{2}\right)^{p_k} \\\ &= \frac{n!}{c_1!} \prod_{k=2}^n \frac{1}{k!^{c_k}\, k!^{p_k}\, c_k!\, p_k!}\cdot \left(\frac{(k-1)!}{2}\right)^{c_k} \left(\frac{k!}{2}\right)^{p_k} \\\ &= \frac{n!}{c_1!} \prod_{k=2}^n \frac{1}{k^{c_k}\,c_k!\, p_k!}\cdot \left(\frac{1}{2}\right)^{c_k} \left(\frac{1}{2}\right)^{p_k} \\\ &= \frac{n!}{c_1!} \prod_{k=2}^n \frac{1}{(2k)^{c_k}\,2^{p_k} \,c_k!\, p_k!} \\\ &= \frac{n!}{c_1! \displaystyle\prod_{k=2}^n (2k)^{c_k}\,2^{p_k} \,c_k!\, p_k!} \end{aligned}

We now have a simple formula for the answer! This can be computed in O(n) time by precomputing some values such as factorials and powers of two. Just remember to reduce all intermediate values modulo 10^9 + 7!

The overall running time is just O(n^2), dominated by the traversal of the graph (and taking complements).

Time Complexity:

O(n^2)

AUTHOR’S AND TESTER’S SOLUTIONS:

[setter][333]
[tester][444]
[editorialist][555]

[333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[555]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.