We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph
G
to graph
H
cannot be done in time |
V
(
H
)|
o
(|
V
(
G
)|)
. We also show an ...exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of |
V
(
H
)|
o
(|
V
(
H
)|)
-time algorithm deciding if graph
G
is a subgraph of
H
. For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems.
Moreover, as a consequence of our reductions, conditional lower bounds follow for other related problems such as Locally Injective Homomorphism, Graph Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic Assignment Problem.
Let
B
n
,
m
be the set of all Boolean functions from {0, 1}
n
to {0, 1}
m
,
B
n
=
B
n
, 1
and
U
2
=
B
2
∖{⊕, ≡}. In this paper, we prove the following two new lower bounds on the circuit size over
U
...2
.
A lower bound
C
U
2
(
f
)
≥
5
n
−
o
(
n
)
for a linear function
f
∈
B
n
− 1,log
n
. The lower bound follows from the following more general result: for any matrix
A
∈ {0, 1}
m
×
n
with
n
pairwise different non-zero columns and
b
∈ {0, 1}
m
,
C
U
2
(
A
x
⊕
b
)
≥
5
(
n
−
m
)
.
A lower bound
C
U
2
(
f
)
≥
7
n
−
o
(
n
)
for
f
∈
B
n
,
n
. Again, this is a consequence of the following result: for any
f
∈
B
n
satisfying a certain simple property,
C
U
2
(
g
(
f
)
)
≥
min
{
C
U
2
(
f
|
x
i
=
a
,
x
j
=
b
)
:
x
i
≠
x
j
,
a
,
b
,
∈
{
0
,
1
}
}
+
2
n
−
Θ
(
1
)
where
g
(
f
) ∈
B
n
,
n
is defined as follows:
g
(
f
) = (
f
⊕
x
1
, … ,
f
⊕
x
n
) (to get a 7
n
−
o
(
n
) lower bound it remains to plug in a known function
f
∈
B
n
, 1
with
C
U
2
(
f
)
≥
5
n
−
o
(
n
)
).
Families with Infants Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan
ACM transactions on algorithms,
06/2016, Letnik:
12, Številka:
3
Journal Article
Recenzirano
Assume that a group of
n
people is going to an excursion and our task is to seat them into buses with several constraints each saying that a pair of people does not want to see each other in the same ...bus. This is a well-known graph coloring problem (with
n
being the number of vertices) and it can be solved in
O
*(2
n
) time by the inclusion-exclusion principle as shown by Björklund, Husfeldt, and Koivisto in 2009. Another approach to solve this problem in
O
*(2
n
) time is to use the Fast Fourier Transform (FFT). For this, given a graph
G
one constructs a polynomial
P
G
(
x
) of degree
O
*(2
n
) with the following property:
G
is
k
-colorable if and only if the coefficient of
x
m
(for some particular value of
m
) in the
k
-th power of
P
(
x
) is nonzero. Then, it remains to compute this coefficient using FFT.
Assume now that we have additional constraints: the group of people contains several infants and these infants should be accompanied by their relatives in a bus. We show that if the number of infants is linear, then the problem can be solved in
O
*((2 − ε)
n
) time, where ε is a positive constant independent of
n
. We use this approach to improve known bounds for several NP-hard problems (the traveling salesman problem, the graph coloring problem, the problem of counting perfect matchings) on graphs of bounded average degree, as well as to simplify the proofs of several known results.
We prove that the Hadwiger number of an n-vertex graph G (the maximum size of a clique minor in G) cannot be computed in time no(n), unless the Exponential Time Hypothesis (ETH) fails. This resolves ...a well-known open question in the area of exact exponential algorithms. The technique developed for resolving the Hadwiger number problem has a wider applicability. We use it to rule out the existence of no(n)-time algorithms (up to the ETH) for a large class of computational problems concerning edge contractions in graphs.
It is still not known whether a shortest common superstring (SCS) of n input strings can be found faster than in O...(2...) time (O...(-) suppresses polynomial factors of the input length). In this ...short note, this paper shows that for any constant r , SCS for strings of length at most r can be solved in time O...(2(...) where c(r)=(1+2r...)... For this, this paper introduces so-called hierarchical graphs that allow them to reduce SCS on strings of length at most r to the directed rural postman problem on a graph with at most k=(1-c(r))n weakly connected components. One can then use a recent O...(2...) time algorithm by Gutin, Wahlstrom, and Yeo. (ProQuest: ... denotes formulae/symbols omitted.)
It is still not known whether a shortest common superstring (SCS) of n input strings can be found faster than in O⁎(2n) time (O⁎(⋅) suppresses polynomial factors of the input length). In this short ...note, we show that for any constant r, SCS for strings of length at most r can be solved in time O⁎(2(1−c(r))n) where c(r)=(1+2r2)−1. For this, we introduce so-called hierarchical graphs that allow us to reduce SCS on strings of length at most r to the directed rural postman problem on a graph with at most k=(1−c(r))n weakly connected components. One can then use a recent O⁎(2k) time algorithm by Gutin, Wahlström, and Yeo.
•We study the shortest common superstring problem on string of length r (r-SCS).•We introduce hierarchical graphs to reduce the r-SCS problem to the directed rural postman problem (DRPP).•We bound the number of weakly connected components in hierarchical graphs and call recent algorithm by Gutin et al.•The main result is a randomized 2n(1−Ω(r−2))-time algorithm for r-SCS.
It is still not known whether a shortest common superstring (SCS) of n input strings can be found faster than in O super(*)(2 super(n))O*(2n) time (O super(*)( times )O*( times ) suppresses ...polynomial factors of the input length). In this short note, we show that for any constant r , SCS for strings of length at most r can be solved in time O super(*)(2 super((1-c(r))n))O*(2(1-c(r))n) where c(r)=(1+2r super(2)) super(-1)c(r)=(1+2r2)-1. For this, we introduce so-called hierarchical graphs that allow us to reduce SCS on strings of length at most r to the directed rural postman problem on a graph with at most k=(1-c(r))nk=(1-c(r))n weakly connected components. One can then use a recent O super(*)(2 super(k))O*(2k) time algorithm by Gutin, Wahlstrom, and Yeo.
We prove that a modification of Andreev's function is not computable by (3 + α − ε) log n depth De Morgan formula with (2α − ε) log n layers of AND gates at the top for any 0 < α < 1/5 and any ...constant ε > 0. In order to do this, we prove a weak variant of Karchmer-Raz-Wigderson conjecture. To be more precise, we prove the existence of two functions f: {0, 1}n → {0, 1} and g: {0, 1}n → {0, 1}n such that f(g(x) ⊕ y) is not computable by depth (1 + α − ε)n formulas with (2α − ε)n layers of AND gates at the top. We do this by a top-down approach, which was only used before for depth-3 model.
Our technical contribution includes combinatorial insights into structure of composition with random boolean function, which led us to introducing a notion of well-mixed sets. A set of functions is well-mixed if, when composed with a random function, it does not have subsets that agree on large fractions of inputs. We use probabilistic method to prove the existence of well-mixed sets.
PDF
