Kernelization of 3-Hitting Set Introduction
Definition 1 (Hypergraph).
Hypergraph is a pair G = (V, E) where V is set of elements called
vertices or nodes and E ⊆ {e ⊂ V | |e| ≥ 2} is set of elements called
hyperedges or edges.
Definition 2 (Hitting Set).
Let (S, C) be a hypergraph. A set H ⊆ S is a hitting set of (S, C) if and
only if H has nonempty intersection with every element of C.
In case the sizes of the elements of C are bounded from above by
some fixed d, the problem is called d-hitting set.
Definition 3 (Hitting Set Problem).
Given hypergraph (S, C) and parameter k, decide if there is a hitting
set H of (S, C) such that |H| ≤ k.
1 / 22
Kernelization of 3-Hitting Set Introduction
Definition 4 (Crown decomposition).
Let G = (V, E) be a graph, then a (H, I, M) is crown decomposition of
G if and only if the following holds:
I is a non-empty independent set of G.
H is NG(I)
M is H-saturating matching of the (bipartite) graph GM = (VM, EM)
where VM = I ∪ H and E = {{u, v} | u ∈ I ∧ v ∈ H}.
2 / 22
Kernelization of 3-Hitting Set Introduction
Lemma 5.
Graph G = (V, E) has crown decomposition if and only if there is a
non-empty independent set I of G such that |I| ≥ |NG(I)|.
Proof.
⇒: Immediate.
⇐: Using Hall’s Marriage Theorem.
There is an algorithm that for given graph G and its independent set I
such that |I| ≥ |NG(I)| finds, in polynomial time, crown decomposition
(H , I , M) of G such that H ⊆ NG(I), I ⊆ I. We will refer to this
algorithm as Construct-Crown.
3 / 22
Kernelization of 3-Hitting Set Introduction
Definition 6 (Crown decomposition for hypergraphs).
Let G = (V, E) be a hypergraph, then (H, I, M) is crown decomposition
of G if and only if the following holds:
I is an independent set of G.
H = {J ⊂ V | ∃x ∈ I . J ∪ {x} ∈ C}.
M is matching of the (bipartite) graph GM = (VM, GM) where
VM = I ∪ H
EM = {(x, J) | x ∈ I ∧ J ∈ H ∧ ({x} ∪ J) ∈ C}.
Every element of H is matched under M.
4 / 22
Kernelization of 3-Hitting Set Introduction
Lemma 7.
Let (S, C, k) be an instance of 3HS and let (H, I, M) be a crown of
(S, C). Then (S, C, k) is equivalent to the instance
(S − I, (C − E(I)) ∪ H, k).
Proof.
Let A be a solution for 3HS instance (S, C, k). Let B ⊆ H be a set that
contains exactly the edges of H with nonempty intersection with A.
Then for every pair {x, y} from (H − B) there is an edge
{{x, y}, z} ∈ M where z ∈ A ∩ I is used to cover the edge
{x, y, z} ∈ C. Replacing z by any element of {x, y} produces another
hitting set A such that |A | ≤ |A|.
5 / 22
Kernelization of 3-Hitting Set Introduction
Lemma 8 (High-Degree rule 3HS).
If x ∈ S has more than k edges whose pairwise intersection is {x},
then:
Add x to any potential solution for (S, C, k).
Remove elements of E(x) from the instance and decrease k by 1.
Proof.
Soundness of the rule is obvious.
To verify that the condition holds for some vertex x is to find a
matching M of the simple graph obtained by deleting x from E(x) such
that |M| > k. This can be done in polynomial time.
If the high degree rule does not apply to any vertex of 3HS instance
(S, C, k), we shall say that (S, C, k) is reduced.
6 / 22
Kernelization of 3-Hitting Set Introduction
Definition 9 (Weakly related edges).
Let (S, C, k) be a 3HS instance. Two distinct elements e1, e2 of C are
weakly related edges if and only if |e1 ∩ e2| ≤ 1. Set W ⊆ C is
maximal collection of weakly related edges if every edge of C is either
in W or there is some e ∈ W such that |e ∩ e | ≥ 2.
7 / 22
Kernelization of 3-Hitting Set Introduction
Lemma 10.
Let (S, C, k) be a reduced yes instance of 3HS and let W be a
collection of weakly related edges of (S, C), then |W| ≤ k2.
Proof.
There is some set A ⊆ S such that it covers all the edges in W and
|A| ≤ k. Since the instance is reduced, by the high-degree rule, every
vertex of A belongs to at most k edges of W.
We can construct maximal set W of weakly related edges by a simple
greedy approach, starting with (any) singleton set and filing it with
elements of C as long as there is one that satisfies the condition.
We will construct W while reducing the instance (using the
high-degree rule) at the same time.
8 / 22
Kernelization of 3-Hitting Set Introduction
Lemma 11 (Crown properties).
Let (S, C, k) be reduced yes instance of 3HS and let W be a maximal
set of weakly related edges of (S, C), I = {x ∈ S | x /∈ V(W)} and
H = {{x, y} | ∃e ∈ W . {x, y} ⊂ e}. WLOG assume that W contains
all edges of C of size less than 3.
1. I is an independent set.
2. |S − I| ≤ 2k2 + k.
3. Every edge e of size three that contains element x ∈ I consists of
x and a pair from H.
4. |H| ≤ 3k2.
9 / 22
Kernelization of 3-Hitting Set Introduction
Crown properties.
1. Assume that there is an edge e containing two elements of I, such
an edge could be added to W (by definition of I), which
contradicts the maximality of W.
2. The vertices from S − I are exactly the vertices that are contained
in some edge from W. We know that there is some solution A (of
size at most k) that covers all elements of W. Since the instance
is reduced, every element x of A belongs to at most k elements of
W. This gives us at most 2k vertices of V(W) per one vertex of A.
Thus S − I contains at most 2k2 + k vertices.
10 / 22
Kernelization of 3-Hitting Set Introduction
Crown properties.
3. Assume that e = {x, y, z} such that {x, y} /∈ H, thus intersection
of e with any element of W would contain at most one element,
which would contradict the maximality of W.
4. Each edge of size (at most) three gives rise to (at most) three
(unique) elements of H.
11 / 22
Kernelization of 3-Hitting Set Introduction
Consider the simple bipartite graph GI,H = (H ∪ I, EI) where edges of
EI are simple edges connecting an element x ∈ I to an element
{y, z} ∈ H if {x, y, z} ∈ C.
By Lemma 5, we can apply Construct-Crown to find crown
(H , I , M) for GI,H. It is easy to see that this crown is also crown for the
original hypergraph.
12 / 22
Kernelization of 3-Hitting Set Introduction
Algorithm 1 Kernelization of 3HS
while C contains singleton set {x} do
Add x to A
Delete all edges that contain x from C
Decrement k
end while
Reduce the instance and construct W of the reduced instance
if |W| > k2 then
Return false
end if
if |I| ≥ |H| then
(H , I , M) ← Construct-Crown(GI,H)
S ← S − I
C ← (C − E(I )) ∪ H
end if
Return the (possibly) new instance.
13 / 22
Kernelization of 3-Hitting Set Introduction
Theorem 12.
There is a polynomial time algorithm that, for an arbitrary input
instance (S, C, k) of 3HS, either determines that the instance does not
have a solution or computes a kernel whose order is bounded from
above by 5k2 + k.
Proof.
In case |I| < |H| we have |S| = |S − I| + |I| ≤ 2k2 + k + 3k2 = 5k2 + k.
In case |I| ≥ |H|:
1. |I − I | ≤ |H − H |.
2. No edges of W were removed from the instance and W is still
maximal.
14 / 22
Kernelization d-Hitting Set
Definition 13 (Subedge).
Let G = (S, C) be a hypergraph. Set e ⊆ S is subedge of G if and only
if (∃e ∈ C . e ⊆ e ). We say that subedge e is j-subedge if and only if
|e| = j.
Lemma 14 (High-degree rule for dHS).
If e ⊂ S is a (d − 2) subedge and e is the pairwise intersection of more
than k edges, then delete all elements of C that contain e as a subset
and add e to C.
Proof.
Soundness of the rule is obvious.
15 / 22
Kernelization d-Hitting Set
Definition 15 (Reduced instance).
If the high-degree rule can not be applied to a dHS instance (S, C, k),
we shall say that (S, C, k) is reduced.
Verifying that (d − 2)-subedge satisfies the condition of the
high-degree rule is equivalent to solving the maximum matching
problem in the (simple) graph given by edges Ee = {e | e ∪ e ∈ C}.
Thus it can be verified in polynomial time.
16 / 22
Kernelization d-Hitting Set
Definition 16 (Weakly related edges).
Two edges are weakly related if their intersection is not larger than
(d − 2) and if neither one of them is a subset of the other.
17 / 22
Kernelization d-Hitting Set
Lemma 17.
Let A be a solution of reduced instance (S, C, k) of dHS, and let W be
maximal set of weakly related edges. Denote by We the set of edges
of W that properly contain e. If e is (d − 2)-subedge then, by the
high-degree rule, |We| ≤ k.
Algorithm 2 High-occurence rule
for i = d − 2 → 1 do
for each i-subedge e of W do
if |We| > kd−1−i then
Delete (from C and W) all edges containing e
Add e to W (and thus C)
end if
end for
end for
18 / 22
Kernelization d-Hitting Set
Soundness of the high-occurence rule.
By induction on i:
1. Base follows directly from high-degree rule (since the instance is
reduced).
2. Assuming that i-th iteration is correct, we will show that every
(i − 1)-subsedge e such that |We| > kd−i has non-empty
intersection with any solution A.
19 / 22
Kernelization d-Hitting Set
Lemma 18.
Let (S, C, k) be a reduced yes instance of dHS and let W be a
maximal set of weakly related edges given by the high-occurrence
rule. Then |W| ≤ kd−1.
Proof.
Every 1-subedge occurs in at most kd−2 edges. The elements of some
solution of size (at most) k form (at most) k singleton subedges. Every
element of W has to be covered by one of these subedges, thus the
number of edges in W can not be greater than kd−1.
20 / 22
Kernelization d-Hitting Set
Lemma 19 (Crown properties).
Let (S, C, k) be our yes instance of dHS after applying the high-degree
and high-occurrence rule and let W be the resulting set of weakly
related edges of the instance. Let I = {x ∈ S | x /∈ V(W)} and H is a
set of (d − 1)-subedges of W. Then:
1. I is an independent set.
2. |S − I| ≤ (d − 1)kd−1 + k.
3. Every edge e of size d that contains element x ∈ I consists of x
and (d − 1)-subedge from H.
4. |H| ≤ dkd−1.
21 / 22
Kernelization d-Hitting Set
Proof.
Analogous to the 3HS case.
As was the case for 3HS, we can find the crown of GH,I using the
Construct-Crown algorithm. The resulting algorithm for dHS
kernelization follows the same pattern as the one for 3HS.
22 / 22