Matching Erosion

In the theory of finite undirected graph, a basic notion that is broadly studied is the notion of matching cut. A matching cut in a graph G is defined to be a matching subgraph of G that is also the edge set of a cut. A cut of a graph G = (V, E) is a partition of the vertex set V into two sets (A, B) such that A and B induces two disjoint induced subgraphs that were before incident to some crossing edges which are the edges in the corresponding so-called edge cut set. Specifically, the edge set of the cut (A, B) is then defined to be the subset of E containing all the edges with one endpoint in A and the other endpoint in B, i.e. those edges uv with u\in A and v\in B. A matching cut is formally defined to be the edge set of such a cut, whenever its edge cut set is indeed a matching. It is worth noting that a matching subgraph which removal increases the number of connected components of a graph G is not necessarily a matching cut, since it may contain edges inside the two separated induced subgraphs. It is a matching cut if it contains exactly the edges of the cut. In order to have more hard computational problems in our still very limited arsenal of proven hard problems, we want to restrict this notion further. We define a matching erosion as a matching cut (A, B) such that A is exactly one side of the matching. It means that each vertex v\in A has exactly one edges out of A, and for any two different vertices u, v\in A their crossing edges end in different vertices in B. Intuitively, such a matching erosion M=(A,B) visually ”peels” off A from G.

Formally, we define a matching erosion of an undirected graph as follows:

DEFINITION 1

Given an undirected graph G=(V, E), a matching erosion (A, B) is a partition of V into two disjoint sets V = A\cup B such that:

  • G[A] and G[B] are two disjoint induced subgraphs

  • The edge set of the cut is a matching: M = \{uv\in E\vert u\in A \land v\in B\} is a matching

  • Every u\in A is incident to an edge in M

Then, our problem naturally asks whether a given undirected graph G has a matching erosion.

DEFINITION 2

Matching Erosion of a graph:

Input: An undirected graph G(V, E)

Output: Yes if G has a matching erosion (A, B), otherwise No

In the next section, we will show that Matching Erosion is computationally hard.

We will reduce Exact 3-Set Cover problem to our problem. Exact 3-Set Cover is another decision problem defined as follows. In Exact 3-set Cover, we are given a universe set of elements U=\{e_1, e_2, \dots, e_{3n}\} and a collection F=\{s_1, s_2, \dots, s_m\} of subsets of U. Each subset s_j in F contains exactly 3 elements e_{s_j1}, e_{s_j2}, e_{s_j3}\in U. The decision problem asks whether there exists a subcollection F'\subseteq F such that each element e_i of U is contained in exactly one subset s_j in F'. Obviously, F' will contain exactly n subsets in the collection F. Such a collection F' is called an exact cover of U.

DEFINITION 3

Exact 3-Set Cover problem:

Input: a universe U = \{e_1, e_2, \dots, e_{3n}\} and a collection F=\{s_1, s_2, \dots, s_m\} of subsets of U, where each s_j contains 3 elements e_{s_j1}, e_{s_j2}, e_{s_j3}\in U

Output: Yes if there exists an exact cover F'\subseteq F, otherwise No

Exact 3-Set Cover is shown to be hard by Garey and Johnson. After describing and proving the correctness of the reduction in the next section, we will establish the following claim.

CLAIM 4

We have that Exact 3-Set Cover \leq_p Matching Erosion

Reducing EXACT 3-SET COVER to MATCHING EROSION

In this section, we prove the claim 4.

Proof:

Describing the construction: Given an instance (U, F) of Exact 3-Set Cover, we will construct an undirected graph G=(V, E) as the produced instance of our problem Matching Erosion. For each element e_i in the universe U, we create a new vertex e_i\in V. Similarly, for each subset s_j\in F, we create a new K_3 consisting of 3 new vertices s_{j,1}, s_{j,2}, s_{j,3}\in V. For each such subset s_j = \{e_{s_j1}, e_{s_j2}, e_{s_j3}\}, we add the 3 edges to E, namely s_{j,1}e_{s_j1}, s_{j,2}e_{s_j2}, s_{j,3}e_{s_j3}. Finally, we add all edges between pairs of two different vertices of the e_i‘s vertices to turn these into a K_{3n} clique.

Correctness of the construction:
Suppose that (U, F) has an exact cover F'\subseteq F consistig of n subsets in F, then based on that solution to Exact 3-Set Cover, we will easily construct a solution to the produced instance G(V, E) of our problem Matching Erosion. Namely, our matching erosion for G would have A to be the set of all the K_3‘s of the subsets included in the exact cover. Clearly, each vertex s_{j,k} (where s_j is included in the exact cover and 1\leq k\leq 3) in this set A is connected to exactly one vertex outside of A, namely its corresponding element e_{s_jk} in the universe U. Obviously, this is a matching cut that happens to be also a matching erosion.

Conversely, if G(V, E) has a matching erosion M = (A, B), we shall show that none of the elements e_i in the universe is included in A. Indeed, if some e_i is included in A then at most one e_l is not in A. This is because if there exist e_i\in A and e_{l1}, e_{l2}\not\in A then A cannot form one side of a matching erosion since e_i\in A is incident to two crossing edges e_ie_{l1}, e_ie_{l2}, recall that the universe U is turned into a K_{3n} in G. So, if one element in U is included in A, at most one element e_l can be in B, but this is also clearly not the case. Because if so, then all the other element e_i‘s (which are included in A) are connected to e_l\in B violating the definition of a matching erosion. So, we have shown that if some element e_i is included in A, then all of the K_{3n} corresponding to U in G are included in A. But, this also cannot be the case for a matching erosion. We need the following observation.

Observation: For each K_3 corresponding to a subset s_j, a vertex s_{j,k} in this K_3 is included in A iff. all the three vertices of this K_3 are included in A.

Proof (of the observation):
Obviously, by definition of a matching erosion.

Using this observation, we are able to show that a matching erosion cannot include all the K_{3n} to A. Indeed, if so, the matching erosion will then partition the K_3‘s into two disjoint sets of K_3‘s, those in A and those in B. The K_3‘s in B would then intuitively form an exact cover for U. But, unfortunately, in this case, those vertices of the K_3 in A cannot have any crossing edge in M, thus violating the definition of a matching erosion.

We have therefore shown that none of the elements e_i in the universe is included in A. This implies that B contains all the K_{3n}. So, the matching erosion needs to partition the set of K_3‘s into two disjoint sets of K_3‘s, those in A and those in B like before. But fortunately, the situation is now reversed. the K_3‘s in B does not need any crossing incident edge (this is only required in a matching split that also imposes the same requirement of A for B). And, the K_3‘s in A would form an exact cover for U.

Advertisements

Missing edges covered by two nodes

We extend the notion of clique to almost-clique wherein 100 edges are allowed not to be present but are required to be covered by at most two nodes. Given a graph G(V, E), we shall show that deciding whether G has an almost-clique of size k is a hard computational problem.

In the theory of finite undirected graph, a basic notion that is broadly studied is the notion of clique. A clique in a graph G is defined to be a complete subgraph of G. So, in a clique, there is an edge between every pair of vertices. In order to have more hard computational problems in our still very limited arsenal of proven hard problems, we want to extend this notion. We define an almost-clique as a subgraph such that to turn this into a complete graph (no longer a subgraph), we only need to add at most 100 edges. And the added edges are required to be covered by at most 2 vertices. Here, we use the notion of a vertex cover of a set of edges.

DEFINITION (Almost-clique of a graph):
Given an undirected graph G(V, E). An almost-clique is a subset of vertices C\subseteq V such that to turn the induced graph G[C] into a complete graph (on \mathrm{C}), we only need to add at most 100 edges. Moreover, the newly added edges are required to be covered by at most 2 vertices of G, using standard notion of vertex cover of a set of edges.

DEFINITION (Almost-Clique problem):
Input: An undirected graph G(V, E) and an integer k
Output: Yes if there exists an almost-clique of size k in G, otherwise No

We reduce CLIQUE problem to ours. CLIQUE is shown to be hard by Garey and Johnson.

CLAIM:
We have that CLIQUE \leq_p Almost-Clique

Inapproximability yields Turing completeness or gap-preserving reduction

It is well known that maximum clique size (also called clique number) of a graph is hard to approximate to within a factor of O(n^{1-\epsilon}), for every real \epsilon>0, unless \mathrm{P} = \mathrm{NP}. This is shown by Hastad. So, if we can solve Almost-Clique in polynomial time, we can even estimate the clique number to within an additive constant error of 100. In particular, after obtaining the maximum almost-clique of G, we can remove a vertex cover of the missing edges. The 100 missing edges can be covered by at most 100 vertices (this is indeed optimal in the case of disjoint matching). Having done that, we then obtain a normal clique of G. And since the size of the largest almost-clique is no less than the size of the largest clique, we have estimated the clique number to within additive constant error of 100.

For the decision problem, the above argument yields Turing completeness or a gap-preserving reduction of gap problems (which are kind of promise problem). So, in this paper, we seek to obtain Karp completeness of our problem and foreshadow about Karp hardness of its variants.

Further investigation

It seems to be tempted to extend our technique in the next section to mitigate the requirement of being covered by at most $2$ vertices. But, it turns out that we will be confused by whether the supposed-to-be {\it vertex cover} is located on which side of the constructed gadget (in fact, it can even be distributed on both sides). We leave the conjecture of hardness of this wider notion of weakly almost-clique for future investigation.

DEFINITION (Weakly Almost-clique of a graph):
Given an undirected graph G(V, E). An almost-clique is a subset of vertices C\subseteq V such that to turn the induced graph G\left[C\right] into a complete graph (on \mathrm{C}), we only need to add at most 100 edges. The requirement of a small vertex cover (namely, 2 in the previous problem) is removed.

DEFINITION (Weakly Almost-Clique problem):
Input: An undirected graph $G(V, E)$ and an integer k
Output: Yes if there exists a weakly almost-clique of size k in G, otherwise No

CONJECTURE
It is hard to decide whether a graph has a weakly almost-clique of size k.

In this section, we prove the main claim.

PROOF

Describing the construction:
Given an instance (G, k) of CLIQUE, we add two new cliques, namely a K_2 and a K_{50}. We connect all these 52 new vertices to all the original vertices in V(G). Call the obtained graph G'. The produced instance of Almost-Clique is (G', k + 52).

Correctness of the construction:
Suppose that G has a clique C of size k, then the union of C with 52 new vertices would be an almost-clique of G'. Indeed, every pair of vertices in C is already connected by an edge of G, as C is a clique of G. All the new 52 vertices are connected to every vertex in V, so they are also connected to every vertex in C. The missing edges are the 100 possible edges between a vertex in the K_2 and a vertex in the K_{50}. And, these 100 missing edges are covered by two vertices in the K_2. So, (G', k + 52) is also a Yes instance of Almost-Clique.

Conversely, if G' has an almost-clique C' of size k + 52, we shall show how to remove at most 52 vertices from C' to obtain a clique C of size k in G. We will consider several cases in the following.

  • C’ contains none of the K_2: in this case, we can remove all the vertices of C' in the K_{50}. At most 50 vertices of the K_{50} can so be removed. Then we remove at most 2 vertices in the vertex cover of the missing edges among vertices in C'\cap V. Totally, we have removed at most 52 vertices, and are left with a k-clique of G.
  • C’ contains one vertex of the K_2: in this case, we can have up to 50 missing edges among the two newly added cliques (if C' includes all of the K_{50}). We can therefore remove up to 51 vertices in the intersection of C' and the two added cliques. Note that we need at least 1 vertex to cover all the missing edges among the two added cliques. So, the missing edges among vertices in C'\cap V must be covered by one vertex in C'\cap V. We continue to remove that vertex from C'. In total, we have removed at most 52 vertices from C' to obtain a k-clique C of G
  • C’ contains both two vertices of the K_2: in this case, if C' does not include any vertex in the K_{50} then all the missing edges are among vertices in C'\cap V and are covered by two vertices among them. Simply removing these two vertices and the K_2, we obtain a clique as a solution to the (G, k) instance of CLIQUE. If C' contains at least two vertices in the K_{50} then we cannot have any missing edges in V'\cap C, since both of the two vertices in the K_2 are now involved in the missing edges already. So, just remove the intersection of C' and the K_2 and K_{50}. The number of removed vertices is likewise at most 52. We have obtained a k-clique in G. If C' contains K_2 and only one vertex of K_{50}, we can cover two missing edges by the one vertex in K_{50}. So, the missing edges among C'\cap V must be covered by one other vertex. So, by removing 4 vertices, we obtain a k-clique of G.

In all cases, we are able to remove at most 52 vertices from C' to obtain a k-clique of G.

“Regular” Spanning Tree

Given an undirected connected graph G(V, E), constructing a spanning tree is a well studied problem with polynomial time algorithms. If we restrict the spanning tree to be “regular” as defined below, it turns out that this becomes a very hard problem.

A spanning tree T(V, E_T) of an undirected connected graph G(V, E_G) is a connected subgraph of G with the same vertex set V and (maybe) different edge set E_T, such that T contains no cycle. The problem of constructing a spanning tree for a graph can be solved by depth-first search or breadth-first search. These are two frequently used techniques in graph algorithms. When the edges of the graph are weighted, we still can utilize Prim, Kruskal or Boruvka algorithms to build a minimum-weight spanning tree. The original unweighted version can be seen as special case of weighted version where all the edge weights are 1. In this paper, we concentrate on unweighted undirected graphs only.

In order to have more beautiful problems in our limited collection of NP-complete ones, we add just one requirement to the spanning tree problem. But, we first need some minor concepts. It is an elementary result from the very beginning of graph theory, back to Euler, that every tree must have at least one vertex of degree 1. These are also called hanging vertex. All the other vertices of a tree are called inner vertices. It is worth noting that since our tree is not rooted, hanging vertex is not leaf. A tree is a 4-“regular” one if apart from its hanging vertices, every inner vertex has degree exactly 4. We want to add the requirement that a spanning tree solution needs to be 4-“regular”.

The reduction is as follows:

Given an instance of X3C (exact cover by 3-sets), we will describe how to construct an undirected graph G(V, E_G). Suppose the background universe set is U = \{1, 2, \dots, n\}, for each element j \in U, we create a vertex j \in V. For each 3-set s_i, we create a vertex s_i. Suppose s_i = \{a, b, c\}, we add three edges to E_G, namely (s_i, a), (s_i, b), (s_i, c).

To force that each element j in U be covered by exactly one 3-set, we connect j to three dummy vertices.

In order to be possibly spanned by a 4-“regular” spanning tree, we need to collect the 3-set vertices “up”. We do it in a gradually incremental manner. Whenever there are two or more vertices left to be collected “up”, we pick two arbitrary ones and connect the two to a new vertex just above them. Having done this, we have created a binary tree with a root. To be 4-regular, we connect the root to two dummy vertices, and each vertex, which is not a 3-set vertex, to a dummy vertex. We do not add dummy vertices to 3-set vertices because they already have 4 adjacent vertices.

Now, if you still are unsure about the correctness of the above construction or just want to read in details. This note is in my opinion of appropriate length to be read.

 

Saturating all debts using few transactions

Given a list of debts between pairs of people, we want to minimize the number of transactions needed to clear all debts.

We give an example to intuitively demonstrate our problem. Suppose we have five people Alice, Bob, Carol and Eve, some pairs of them have debts. In particular, Alice owes Bob $3$ dollars, David owes Eve $10$ dollars. We may even have opposite debts, such as Bob also owes Alice $5$ dollars. All the debts are depicted in the following figure.

If these people want to clear all their debts, they have to make money transactions. It could be that, for each directed arc in the above graph, the two involving people make exactly the same money transaction. Clearly, doing like that requires the number of money transactions to be equal to the number of arcs in the graph. Our problem denoted by Min-Transfer asks whether $k$ money transactions are enough to saturate all the debts.

Definition is now given:
Definition (Min-Transfer problem):

Input: a directed graph G, a number k

Output: Can k money transactions saturate all the debt arcs of G?

Claim in this post is now ready to be stated.
Claim: We have that Subset Sum \leq_p Min-Transfer

Proof is very simple.

Multi-way cut

In Graph Partition SumSquared, we wish to partition a graph by removing e edges to maximize an objective function. The objective function computes for each of the resulting disjoint subgraphs the sum of its vertex weight, squares the obtained value, and divides by the number of vertices, and finally sum over all the disjoint subgraphs.

Formally put as follows:

Input: An integer e, and a connected graph G = (V, E) together with a vertex weight function w: V \to \mathbb{N}

Output: A partition of G, namely G_p = (V, E_p), obtained by removing e edges from E which maximizes:

\textrm{\bf max}\sum_{G_i\in\{G_1, G_2, \dots, G_k\}} {\frac{1}{\lvert G_i\rvert}}{(\sum_{v_j \in {V_i}}{w(v_j)})}^2

where G_p = G_1 \cup G_2 \cup \dots \cup G_k and elements of G_p are disjoint. And, V_i is the vertex set of G_i

Proof can be obtained here.

Taking quartic roots of 2

While working with modular polynomials, nothing can be more interesting and also striking than raising the degree of them. Previously, we discussed the equation x^2 \equiv -1 \:\textrm{mod} \:n where n can be any natural number.  Now, we want to deal with quartic equation of the form x^4 \equiv 2 \:\textrm{mod} \:p where p is a prime number.

The long story of this equation and variants has begun since 1749. Around that time, Euler conjectured the necessary and sufficient condition of p for the existence of a quartic root of 2 modulo p. His book Tractatus de numeroroum doctrina capita sedecim quae supersunt [1] was published in 1849, one hundred years after he wrote it. In this book, he conjectured that 2 is a fourth power residue (mod p) iff. p is of the form x^2 \:+ \:64y^2. For example, 2 is a fourth power residue (mod 73), since 73 = 3^2 + 64.

Gauss proved this conjecture in 1828 in his first monograph [2] on biquadratic reciprocity. Historically, Euler’s conjecture was widespread among mathematicians long before officially printed. Together with Fermat’s 4n \:+ \:1 theorem, we can see that such a prime p can be uniquely represented as a^2 + b^2, up to the swapping of a and b. Parity of a and b must be different as well. So, Gauss’s condition can be stated as that the even one among a and b must be divisible by eight. H. Davenport wrote an excellent book [3] on arithmetics, which contains, in much more details, various topics.

Modern mathematics has since developed so much fruitful ideas to solve polynomials both for real roots and modular roots. Zhi-Hong Sun [4] extends the condition for other values of natural number m \neq 2 to be quartic residue mod p.

Gauss’s condition can be seen as a polynomial-time reduction between computational problems. Some definitions are necessary.

DEFINITIONS

QUARTIC-2-MODULUS = {p | p is congruent to 1 modulo 4 and 2 is a quartic residue mod p}

FEASIBLE-QUAD-DIOPHANTINE = {<nd> | the Diophantine equation x^2 + dy^2 = n is feasible}

PROPERTY-OF-DIOPHANTINE-SOLUTION = {n | the Diophantine equation x^2 + y^2 = n is satisfied by a solution (a, b) where a or b is divisible by 8}

So, now the following claims are immediate from Gauss’s condition.

CLAIMS

Claim 1:

QUARTIC-2-MODULUS \leq_p FEASIBLE-QUAD-DIOPHANTINE

Claim 2:

QUARTIC-2-MODULUS \leq_p PROPERTY-OF-DIOPHANTINE-SOLUTION

If you have the ability to solve Diophantine equation, you have enough capabilities to deal with much of modular arithmetics. Even an algorithm to account for the existence of a solution to Diophantine equation is of vastly achievements.

[1] Euler, Leonhard (1849), Tractatus de numeroroum doctrina capita sedecim quae supersunt, Comment. Arithmet. 2

[2] Gauss, Carl Friedrich (1828), Theoria residuorum biquadraticorum, Commentatio prima, Göttingen: Comment. Soc. regiae sci, Göttingen 6

[3] H. Davenport, The Higher Arithmetic: An Introduction to the Theory of Numbers, Cambridge University Press

[4] Zhi-Hong Sun, Quartic residues and binary quadratic forms, Journal of Number theory 113 pp.10-52, Elsevier, 2005

Modular square roots of -1

As we have admitted in the last sentence of the first paragraph of the last post that the arsenal of number theory may some day be of utmost help, we try to show some nice related result in this post. Modular arithmetics plays a central role in mathematics. We may have been very curious the first time we learnt how the modular operators operate.

While we are in number theory land, our Sean is working very diligently in mathematical programming land. If we are lucky enough, we should try to merge the two fascinating fields in some future posts.

Most of the time, modular arithmetics theorems are beautiful results on additive, multiplicative modular properties. Though still, there are many classical and modern results on the modular square root, the number of them is far less than additive, multiplicative ones.

In other fields such as analysis, square roots of -1 are also pearls of mathematics achievements in history. By asking the same question, namely whether there exists a square root of -1 modulo a natural number n, we come up with yet another hard problem, this time of number-theoretic flavor, as shown in this writeup.