Intersection Inference

4.16.2 Intersection Inference

Definition

Given a finite set U of size n, and a collection A₁,…,A_m of subsets of U, each with a corresponding integer , c_i, where 1 ≤ i ≤ m. There exist a set X ⊂ U, so that X ∩ A_i = c_i,1 ≤ i ≤ m. Such set is called Intersection Inference.

Polynomial Certifier

Given a finite set U of size n, and a collection A₁,…,A_m of subsets of U, each with a corresponding integer , c_i, where 1 ≤ i ≤ m. Does there exist a set X ⊂ U, so that X ∩ A_i = c_i,1 ≤ i ≤ m?

Input: Given a finite set U of size n, and a collection A₁,…,A_m of subsets of U, each with a corresponding integer, c_i, where 1 ≤ i ≤ m
Certificate: A set X ⊂ U
Certifier: We can create a polynomial-time certifier that checks, if X is a subset of U, and continuously check |X ∩ A_i| = c_i holds.
Time Complexity: O(m ⋅ n²)

Reduction from 3D-Matching from simple case to general case

We construct the reduction in polynomial time as follow:
Let U = T
∀x ,A_x = {(x,y,z) T|y ,z },c_x = 1
∀y ,A_y = {(x,y,z) T|x ,z },c_y = 1
∀z ,A_z = {(x,y,z) T|x ,y },c_z = 1

Claim 4.16.2.1. 3D-Matching ≤_p Intersection Inference (This construction of 3-D Matching leads to is a special case of Intersection Inference)
Given ,,,T, the 3D-Matching holds, if and only if there also exists an Intersection Inference.

Given ,,,T, the 3D-Matching holds, ⇒ there also exists an Intersection Inference.

Proof. Given a 3D-Matching instance, < U,X,Y,Z >, we can build a Intersection Inference instance from the construction above, it is easy to see that there exists a subset of U, W ⊂ U, such that ∀x ,|W ∩ A_x| = c_x = 1. Similarly for ∀y ,∀z . Therefore, W is an Intersection Inference. __

Given ,,T, there also exists an Intersection Inference ⇒ The 3D-Matching holds,

Proof. Given a set W ⊂ U, if |W ∩ A_x| = c_x = 1 holds, then this means that each x appear in T exactly once. Same thing to ∀y ,∀z . Thus, 3D -Matching holds. __

[next] [prev] [prev-tail] [front] [up]