TryAlgo

Encoding edges by weights

Warning

This post describes a solution to the problem stated in the above link, which was the last problem of the competition Battle Dev Hello Work November 2019. However it will not be accepted by the judge, because the intended problem was a different one. In the stated problem the condition is that x[u]+x[v]>y if and only if (u,v) is an edge. In the intended problem, the condition should be that $\sum_{u\in S} x[u] > y$ if and only if $S\subseteq V$ is a clique in the graph. The solution to the intended problem is described here.

Problem statement

Given an undirected graph G(V,E), we ask whether it is possible to encode the edges using non-negative integers y and x[v] for every vertex v such that

In addition y should be minimized.

Properties

The key observation is that the inequality x[u] + x[v] > y is monotone in x[v]. Hence the neighborhoods N of two vertices v and v’, must be included in each other. This statement is a bit subtle as v or v’ could be missing from one of the neighborhoods, because the graph has no self-loops. So the precise statement is, using $N[v]:=\{u:(u,v) \in E\}$ and $d(v)=|N[v]|$,

So we have a necessary condition which we can check in time $O(|V|^2)$, by ordering first the vertices in increasing degree, and checking inclusion of every two successive vertices in this order. The complexity is ok, given the bound $|V|\leq 1000$ from the problem statement.

I claim that the condition is also sufficient. Consider the adjacency matrix of the given graph, using the degree ordering of the vertices.

Consider the example 5 of the input samples:

Example graph

We obtain the following adjacency matrix M, where we showed in gray the edges and in white the non-edges.

Adjacency matrix

We can observe that the grid partitions into k by k blocks, the row or column of a block corresponds to vertices which have the same degree. k is defined as the number of distinct degrees. In our example k=6. There are only two kind of blocks, those that do not contain any edge, and those that are completely filled with edges, except for the diagonal. Moreover these gray blocks are in the lower right triangle of the matrix, and contain or do not contain the anti-diagonal cells, depending whether there is a vertex of degree 0. Hence this condition will be important for the solution.

Clearly vertices of different degree need different x-values. Hence max x[v] ≥ k-1, and y ≥ k-1. Since we want to minimize y, it seems good to have the smallest increase in x between adjacent blocks. Hence we suggest the following solution: