SEZ - Editorial

PROBLEM LINK:

Practice
Contest

Author: Gaoyuan Chen
Tester: Kevin Atienza
Editorialist: Ajay K. Verma
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Hall’s Marriage Theorem, Linear Programming, Total Unimodularity

PROBLEM:

Given an undirected graph G = (V, E), find the maximum value of (\| S \| - \| N(S) \|), where S is an independent set of G, and N(S) denotes the neighborhood of S.

QUICK EXPLANATION:

The condition of S being an independent set can be relaxed without affecting the answer (see Lemma 1 below). Hence, the problem reduces to finding the maximum value of (\| S \| - \| N(S) \|), where S varies over all subsets of V. This can be solved either by using Hall’s marriage theorem (which reduces the problem to bipartite matching), or by formulating the problem as an integer linear programming, and then use the total unimodularity of the formulated problem (which means the integer constraint can be relaxed, and any linear programming solver can be used).

EXPLANATION:

We are given an undirected graph G = (V, E) with N vertices and M edges. The objective is to find an independent subset S of G, for which the difference between its size and size of its neighborhood is maximum.

For a given subset S, we can define two values x_v and y_v for each vertex v in the following way:

x_v = 1, if v \in S, and 0 otherwise.
y_v = 1, if at least one of the neighbors of v is in the set S, and 0 otherwise.

In other words
y_v = 1, iff there exist an edge (u, v) such that x_u = 1.
y_v = \text{max} (x_u), where u varies over all neighbors of v.

Note that,
\| S \| = x_1 + x_2 + \cdots + x_N
\| N(S) \| = y_1 + y_2 + \cdots + y_N

Since S must be an independent set, hence there should be no vertex v for which both x_v and y_v are 1 (i.e., x_v + y_v \leq 1). Therefore, the task is to pick values x_1, x_2, \ldots, x_N from the set \{0, 1\}, such that the constraint about S being an independent set is satisfied, and the value of the objective function \text{obj} (S) = (x_1 + x_2 + \cdots + x_N) - (y_1 + y_2 + \cdots + y_N) is maximum.

For smaller value of N this can be done by considering all possible assignments, and pick the one which gives the best value of objective function, as shown below.

int best = 0;
// iterate through all subsets of V.
for (int S = 0; S < (1 << N); ++S) {
  int x[N] = {0};
  int y[N] = {0};

  for (int j = 0; j < N; ++j)
    if (S & (1 << j))
      x[j] = 1;

  for each edge e = (u, v) {
    y[u] = max(y[u], x[v]);
    y[v] = max(y[v], x[u]);
  }

  int obj = 0;
  for (int j = 0; j < N; ++j) {
    // S is not an independent set.
    if (x[j] == 1 && y[j] == 1) {
      obj = -1;
      break;
    }
    obj += x[j] - y[j];
  }
  best = max(best, obj);
}

The complexity of the above code is O (E2^N), and should be enough for the smaller task. One could also reduce the complexity to O (N2^N) by using bitmasks.

Next, we discuss how to solve the problem for larger graphs. First we prove that the constraint of S being an independent set can be relaxed without affecting the answer.

Lemma 1: For each set S, there exist an independent set S1, such that (\| S \| - \| N(S) \|) \leq (\| S1 \| - \| N(S1) \|).
Proof: We can compute the x and y values for the given set S as described above.
\text{obj} (S) = \sum (x_i - y_i)

The vertices of set S, can be split into two sets A and B as follows:
A = \{v \in S \mid \forall (u, v), u \notin S\}
B = \{v \in S \mid \exists (u, v), u \in S\}
In other words, all neighbors of vertices in A lie outside S, while each vertex of B has at least one neighbor in S, equivalently,
v \in A \iff (x_v = 1, y_v = 0)
v \in B \iff (x_v = y_v = 1)

Since all neighbors of A lie outside S, there cannot be any edge between the vertices in A and B, also there would be no edge between two vertices of A (i.e., A is an independent set). Now, if we shrink the set S to S1 = A, and compute the new x' and y' values corresponding to this set, we can observe the following:

v \in A \implies (x'_v = 1, y'_v = 0) // S1 = A is an independent set
v \in B \implies (x'_v = y'_v = 0) // There is no edge between A and B
v \notin S \implies (x'_v = x_v = 0, y'_v \leq y_v) // S1 is a subset of S.

This means (x_v - y_v) \leq (x'_v - y'_v), holds for all vertices v. Hence, the objective function for this new set S1 should be at least as large that of S. This completes the proof of the lemma.

Based of the lemma, we can relax the constraint of S being an independent set, and just find the maximum value of (\| S \| - \| N(S) \|). If the maximum value is obtained for a non-independent set, we can shrink it to an independent set, with the same value of objective function.

Next, we present two ways to solve the problem: The first is based on Hall’s marriage theorem, and the second is based on linear programming.

Hall’s Marriage Theorem based Approach:

Let us make a bipartite graph H = (L, R, E), where each side contains N vertices: left side containing (u_1, u_2, \ldots, u_N) and right side containing (v_1, v_2, \ldots v_N). For any edge (a, b) in the original graph G, we add edges (u_a, v_b) and (u_b, v_a) in the new graph. For any subset S of L, the size of N(S) is the same as the size of the neighborhood of the corresponding set in G, hence our task reduces to finding a subset S of L, for which (\| S \| - \| N(S) \|) is maximum.

Hall’s marriage theorem states that in a bipartite graph, the size of the maximum matching is the same as the number of vertices on left side if and only each subset of the vertices on the left side has a neighborhood, whose size is at least as large as this subset, i.e., (\| S \| \leq \| N(S) \|), for each subset S of L.

This means that if we have a perfect matching in H, then (\| S \| \leq \| N(S) \|) will hold for each subset of L, hence, the maximum value of (\| S \| - \| N(S) \|) will be zero. In fact, we can use a generalized form of Hall’s theorem which establishes a relationship between the size of matching matching of H, and the maximum value of (\| S \| - \| N(S) \|).

Lemma 2: In a bipartite graph with N vertices on the left side, the maximum value of (\| S \| - \| N(S) \|), S being a subset of left side vertices, will be (N - k), where k is the size of the maximum matching (Theorem 6.3 in this paper)
Proof:
We first prove that the (\| S \| - \| N(S) \|) \leq (N - k).
The size of the maximum matching is k, hence exactly (N - k) vertices on the left side are unmatched. Now, if we add (N - k) vertices on the right side of the bipartite graph, and connect them with each vertex of the left side, the resulting graph will have a matching of size N. Also we have increased the neighborhood of each non-empty subset of the left side vertices by (N - k). According to Hall’s theorem, in the new graph each subset of left side vertices will have a neighborhood at least as large as the subset itself, i.e., (\| S \| \leq \| N(S) \|) + (N - k), or in other words, \text{max} (\| S \| - \| N(S) \|) \leq (N - k).

On the other hand, if the maximum value of (\| S \| - \| N(S) \|) is x, then we add x vertices on the right side and connect them with each vertex of the left side, which will increase the neighborhood of each subset S by x, i.e., in the new graph each subset of the left side vertices will have a neighborhood at least as large the subset. This means the new graph must have a matching of size of N according to Hall’s theorem. Since, we have added only x vertices, we can increase the size of maximum matching by at most x, i.e., N \leq (k + x) (equivalently, (N - k) \leq x). This completes the proof of the lemma.

This means, in order to solve our problem, we only need to compute the size of maximum matching in the graph H, which can be done in O (EN^{0.5}) time using Hopcroft-Karp algorithm.

Linear Programming based Approach:

In this section, we discuss an approach based on linear programming, which is slower than the maximum matching based solution, but still runs in polynomial time, and will fit in time for the given constraints.

Let us formulate our problem in terms of linear constraints. We have discussed in the first section that the problem is equivalent to picking x_1, x_2, \cdots, x_N and y_1, y_2, \cdots, y_N from the set \{0, 1\}, such that the following constraints are satisfied:

If vertex i has neighbors j_1, j_2, \cdots, j_k, then
y_i = \text{max} (x_{j_1}, x_{j_2}, \cdots, x_{j_k}).

We can write this in terms of linear constraints as follows:
x_{j_1} \leq y_i
x_{j_2} \leq y_i

x_{j_k} \leq y_i
y_i \leq (x_{j_1} + x_{j_2} + \cdots + x_{j_k})

We also have boundary constraints on the value of $x_i$’s
0 \leq x_i \leq 1
The boundary constraints of the value of y_i's will be satisfied implicitly by the above constraints. The objective is to maximize the function.
(x_1 + x_2 + \cdots + x_N) - (y_1 + y_2 + \cdots + y_N)

Note that, the optimization function will decrease if we increase the value of $y_i$’s, hence, we can remove the constraint
y_i \leq (x_{j_1} + x_{j_2} + \cdots + x_{j_k}),
as it will be forced by the optimization function anyway.

So, our Integer Linear programming formulation looks as follows:
0 \leq x_i \leq 1
For edge (u, v): x_u \leq y_v, x_v \leq y_u
\text{maximize} (x_1 + x_2 + \cdots + x_N) - (y_1 + y_2 + \cdots + y_N)

We have 2 (N + M) linear constraints, and an extra constraint that all x_i and $y_i$’s must be integers. The extra constraint makes the problem hard.

Relaxation of Integer Constraints:

Some instances of integer linear programming satisfy the property of being totally unimodular, which allows us to relax the integer constraint without affecting the answer. In fact, it can be proved that our linear programming formulation is totally unimodular using the criteria mentioned in this paper, however, we provide a simpler proof indicating why integer constraints can be relaxed in our linear programming formulation.

Lemma 3: Any solution of the above mentioned linear programming can be converted to a solution, where integer constraints are satisfied, and the value of the objective function remains the same.
Proof: Let us say that we found a solution of the aforementioned linear programming problem where some of the x_i's and y_i's take fractional values.

Pick the x_i's which take fractional values, and sort them. Let us say that x_{i_1}, x_{i_2}, \cdots, x_{i_m} are the ones with largest fractional value f. Now find the neighbors of vertices i_1, i_2, \cdots, i_m, which do not have any neighbor, whose x is assigned value 1. Let us say that these neighbors are j_1, j_2, \cdots, j_n.

x_{i_1} = x_{i_2} = \cdots = x_{i_m} = f
y_{j_1} = y_{j_2} = \cdots = y_{j_n} = f

The second equality holds because each of the j_k is connected to at least one the picked i_l vertex, but to none of the vertex with x value 1.

We can observe that we can increase of decrease the value of f slightly (i.e., f \pm \epsilon), and all the constraints will still be satisfied. The contribution of these x_i and y_j's values in the objective function is (m - n) f. Now, if (m > n), then we increase the value of f to f + \epsilon, without affecting any constraints but increasing the value of the objective function. On the other hand, if (m < n), then we decrease the value of f to f - \epsilon, which will increase the objective function. Since, we have the optimal solution of the linear programming, hence none of two cases should happen, i.e., (m = n). In this case, we can increase the value of f to 1, without affecting the constraints or objective value. The same process can be repeated to convert the remaining fractional values to integer ones without affecting the value of objective function. This completes the proof of the lemma.

The implication of the above lemma is that we can now use any linear programming solver, e.g., Simplex method, to solve our problem.

Reduction in the Number of Constraints:

The current formulation has 2N variables and 2 (N + M) constraints, which we can be reduced into half as many variables and constraints. Suppose we found a solution of the linear programming. We can partition the vertices into 4 sets A, B, C, D according to their x and y values.

v \in A \iff (x_v = 1, y_v = 0)
v \in B \iff (x_v = 1, y_v = 1)
v \in C \iff (x_v = 0, y_v = 0)
v \in D \iff (x_v = 0, y_v = 1)
\text{obj} = \| A \| - \| D \|

According to Lemma 1, we can remove the set B by assigning x_v = y_v = 0 in this set. So now, we have only sets A, C, and D. Note that, the set C corresponds to those vertices, which lie outside our chosen set, and also do not have any neighbors in the chosen set. We can actually change the values of x_v and y_v of this set to 0.5 without affecting any constraint (This is because all neighbors of this set will have y value either 0.5, or 1, which is no less than x value of any vertex of the set). Hence,

v \in A \iff (x_v = 1, y_v = 0)
v \in C \iff (x_v = 0.5, y_v = 0.5)
v \in D \iff (x_v = 0, y_v = 1)
\text{obj} = \| A \| - \| D \|

However, now we have an additional property in the solution that (x_v + y_v) = 1, for each vertex. This means any solution of our linear programming solution can be converted into one satisfying this property. In other words, we can add this extra constraints without affecting the value of objective function.

The implication of this additional constraint is that we can remove the variable y_i's and replace them by (1 - x_i)'s. After the replacement, we get the following instance.
0 \leq x_i \leq 1
For edge (u, v): x_u + x_v \leq 1
\text{maximize} 2 (x_1 + x_2 + \cdots + x_N) - N

This formulation has only N variables and 2 N + M constraints. Also one can notice that this formulation is the same as the one used for computing the maximum independent set of a graph.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

2 Likes

My solution was:

  1. Check whether any vertex has exactly 0 or 1 neighbour.
  2. If there exist 0 neighbour, increment the answer by 1 and remove the vertex from consideration.
  3. If 1 neighbour, remove the two vertices(said vertex and its neighbour) from consideration.
  4. Repeat these steps until either all vertices have been removed or no vertices with exactly 0 or 1 neighbours can be found.
    Return answer.
    This gave correct answer for 8 out of the 10 test cases but failed for the last two. Can anyone help?

@d_taxman: Your approach will fail, for example, for the graph containing 5 nodes (1…5) that has following chains of edges: 1-2-5, 1-3-5, 1-4-5. Your algorithm choose no nodes to be in SEZ, as all nodes have at least 2 neighbours, but the coorect solution is to choose nodes 2, 3, 4 to be in SEZ, that gives happiness equal to +1.

Why was there only 1 test case per file?

Initially, I wanted to “hack” the problem as follows (but my wife didn’t let me, saying it’s not ethical, etc. :slight_smile: , so I ended up solving it for real):

  1. Compute some hash value for each test file, in order to be able to uniquely identify in the source code each file - for instance, hash value 5 corresponds to test file 1, hash value 13 corresponds to test file 2, etc.

  2. Make 201 submissions. Submission i (0 <= i <= 200) would simply output the value i (each answer is between 0 and 200, due to the constraints).

  3. Visually look at all the 201 submissions and see the exact answer for each test case (the current interface shows AC/WA/TLE/etc. for all the test files when you make a submission)

  4. Enter the information in the source code from point 1: e.g. if hash value is 5 then it’s test 1 and from points 2-3 I know that the answer for test 1 is 117, then : if hash value is 5 print 117.

  5. Get AC without really thinking about how to solve the problem at all :slight_smile:

Of course, the above strategy wouldn’t work if there is more than 1 test case per file (e.g. with 2 test cases per file there are 201x201 combinations which would need to be tested in order to find the correct answer for each file, which would be way too much).

Probably no one actually did what I wrote above (I was planning to do it closer to the end of the contest as a proof of concept :slight_smile: but I ended up spending that time working on the challenge problem), but still… why only 1 test case per file?

12 Likes

Just out of curiosity, does your wife also does like algorithm research as a career? If so, why doesn’t she attend codechef too? :smiley:

1 Like

My approach is same as d_taxman but instead of checking only exactly 0 and 1 neighbour, i did something different. But still it gives wrong answer on last test case.
My approach is as follow:

first insert all vertices with its degree in a set.After that repeat while loop until set becomes empty. first of all get the first element from set(which is obvious having lowest degree) and increase x by 1 and mark all its neighbour(with increase y by one each time) and also marked popped node. Then for each unmarked node which is neighbour of popped node neighbour, decreases its degree by one each time and reinsert it in to set. And each time i take maximum of x-y. My code is -

vector V[505];
int deg[505];
bool chk[505];
int n,m;
int main()
{
int u,v;
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d %d",&u,&v);
V[u].push_back(v);
V[v].push_back(u);
deg[u]++;
deg[v]++;
}

memset(chk,0,sizeof(chk));
set<pair<int,int> > S;
for(int i=1;i<=n;i++)
{
    S.insert(make_pair(deg[i],i));
}
int x=0,y=0;
int ans=0;
while(!S.empty()){
    pair<int,int> P=*S.begin();
    S.erase(S.begin());

    u=P.second;
    if(chk[u]==1)
        continue;

    chk[u]=1;
    ans=max(x-y,ans);
    x+=1;
    for(int i=0;i<V[u].size();i++)
    {
        if(chk[V[u][i]]==0){
        chk[V[u][i]]=1;
        y+=1;
        int k=V[u][i];
        for(int j=0;j<V[k].size();j++){
           if(chk[V[k][j]]==0){
            S.erase(S.find(make_pair(deg[V[k][j]],V[k][j])));
            deg[V[k][j]]--;
            S.insert(make_pair(deg[V[k][j]],V[k][j]));
            }
        }
        }
    }
     ans=max(x-y,ans);
}
ans=max(x-y,ans);
//ans=n-1;
printf("%d\n",ans);
return 0;

}

please tell me where am I wrong and if possible give testcases on which my code fails.

@asvikr Your approach will fail, for example, for the graph containing 5 nodes (1…5) that has following chains of edges: 1-2-5, 1-3-5, 1-4-5. Your algorithm choose no nodes to be in SEZ, as all nodes have at least 2 neighbours, but the coorect solution is to choose nodes 2, 3, 4 to be in SEZ, that gives happiness equal to +1.

Fantastic problem and editorial!

For those wondering, this: “Also one can notice that this formulation is the same as the one used for computing the maximum independent set of a graph.” doesn’t mean that the problem is equivalent to Maximum Independent Set (that would be impossible because MIS is NP-hard). The reason is that MIS contains another requirement: the solution must be integer; and this property is lost in the last step, when we go from 2N variables to N variables (an optimal solution can now have values equal to 0.5).

So this shows that relaxed linear programming problem corresponding to MIS is equivalent to maximum bipartite matching. Is this a new result?