Information Technology Reference
In-Depth Information
d
Theorem 2.
In every arrangement of hyperplanes in general position in
R
(with
d
=
O
(1)
), there exists a subset of the hyperplanes of size at most
n
−
ʩ
(
n
1
/d
)
such that every cell is bounded by at least one hyperplane in the subset.
Proof.
We will prove that every such arrangement has an
independent set
of size
ʩ
(
n
1
/d
), where an independent set is defined as the complement of a guard-
ing set, that is, a subset of the hyperplanes such that no cell is bounded by
hyperplanes of the subset only.
Let
H
be a set of
n
hyperplanes, and consider an arbitrary, inclusionwise
maximal independent set
I
. For each hyperplane
h
I
, there must be a
cell
c
h
of the arrangement that is bounded by a set of hyperplanes
C
∈
H
\
∪{
h
}
with
C
I
, since otherwise we could add
h
to
I
,and
I
would not be maximal. If
c
h
has size at least
d
+ 1, i.e., if
c
h
is incident to at least
d
+ 1 hyperplanes, then
there must be a vertex of the arrangement induced by
I
that is also a vertex
of
c
h
. We charge
h
to this vertex. Note that each vertex can only be charged
2
d
ↆ
1)-tuple
of hyperplanes of
I
bounding
c
h
. This tuple can also be charged at most
O
(1)
times. Therefore
=
O
(1) times. If
c
h
has size
d
, we charge
h
to the remaining (
d
−
2
d
d
)+
O
(
d
−
1
)
|
H
\
I
|
=
n
−|
I
|≤
·
O
(
|
I
|
|
I
|
=
ʩ
(
n
1
/d
)
.
|
I
|
4 Acyclic Orientations
Given a graph
G
=(
V,E
) we wish to find a subset
S
ↆ
E
such that for every
acyclic orientation of
G
, there exists a
flippable
edge
e
S
such that changing the orientation of
e
does not create any cycle. Let us call
such a set a
guarding set
for
G
. Note that an oriented edge
e
=
uv
in an acyclic
orientation is flippable if and only if it is not
transitive
, that is, if and only if
uv
is the only oriented path from
u
to
v
.
∈
S
, that is, an edge
e
∈
4.1 Complexity
Theorem 3.
Given a graph
G
=(
V,E
)
and a subset
S
E
of its edges, the
problem of deciding whether
S
is a guarding set is coNP-complete, even if
G
is
a complete graph.
ↆ
Proof.
The set
S
is not a guarding set if and only if there exists an acyclic
orientation of
G
in which all edges
e
S
are transitive.
Consider a simple graph
H
on the vertex set
V
, and define
G
as the complete
graph on
V
,and
S
as the set of non-edges of
H
. We claim that
S
is a guarding
set for
G
if and only if
H
does not have a Hamilton path. Since deciding the
existence of a Hamilton path is NP-complete, this proves the result.
To prove the claim, first suppose that
H
has a Hamilton path, and consider
the acyclic orientation of
G
that corresponds to the order of the vertices in
∈
Search WWH ::
Custom Search