We study the complexity of the C
hannel
A
ssignment
problem. An open problem asks whether C
hannel
A
ssignment
admits an
O
(
c
n
) (times a polynomial in the bit size) time algorithm, where
n
is a ...number of the vertices, for a constant
c
independent of the weights on the edges. We answer this question in the negative. Indeed, we show that in the standard Word RAM model, there is no 2
o
(
n
log
n
)
(times a polynomial in the bit size) time algorithm solving C
hannel
A
ssignment
unless the exponential time hypothesis fails. Note that the currently best known algorithm works in time
O
*(
n
!) = 2
O
(
n
log
n
)
, so our lower bound is tight (where the
O
*() notation suppresses polynomial factors).
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.
Given a traveling salesman problem (TSP) tour
H
in graph
G
, a
k
-move is an operation that removes
k
edges from
H
and adds
k
edges of
G
so that a new tour
H
′
is formed. The popular
k
-OPT heuristic ...for TSP finds a local optimum by starting from an arbitrary tour
H
and then improving it by a sequence of
k
-moves.
Until 2016, the only known algorithm to find an improving
k
-move for a given tour was the naive solution in time
O
(
n
k
). At ICALP’16, de Berg, Buchin, Jansen, and Woeginger showed an
O
(
n
⌊2
k
/3⌋+1
)-time algorithm.
We show an algorithm that runs in
O
(
n
(1/4+ϵ
k
)
k
) time, where lim
k
→ ∞
ϵ
k
= 0. It improves over the state of the art for every
k
≥ 5. For the most practically relevant case
k
= 5, we provide a slightly refined algorithm running in
O
(
n
3.4
) time. We also show that for the
k
= 4 case, improving over the
O
(
n
3
)-time algorithm of de Berg et al. would be a major breakthrough: An
O
(
n
3−ϵ
)-time algorithm for any ϵ > 0 would imply an
O
(
n
3−δ
)-time algorithm for the A
ll
P
airs
S
hortest
P
aths
problem, for some δ > 0.
We present three results on the complexity of Minimax Approval Voting. First, we study Minimax Approval Voting parameterized by the Hamming distance d from the solution to the votes. We show Minimax ...Approval Voting admits no algorithm running in time O*(2o(d log d)), unless the Exponential Time Hypothesis (ETH) fails. This means that the O*(d2d) algorithm of Misra, Nabeel and Singh is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time O*((3/ε)2d), which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized approximation scheme for Minimax Approval Voting, which runs in time nO(1/ε2⋅log(1/ε))⋅poly(m), where n is a number of voters and m is a number of alternatives. It almost matches the running time of the fastest known PTAS for Closest String due to Ma and Sun.
We study the complexity of the
Channel Assignment
problem. By applying the meet-in-the-middle approach we get an algorithm for the
ℓ
-bounded
Channel Assignment
(when the edge weights are bounded by
...ℓ
) running in time
O
∗
(
(
2
ℓ
+
1
)
n
)
. This is the first algorithm which breaks the
(
O
(
ℓ
)
)
n
barrier. We extend this algorithm to the counting variant, at the cost of slightly higher polynomial factor. Very recently the second author showed that
Channel Assignment
does not admit a
O
(
c
n
)
-time algorithm, for a constant
c
independent of
ℓ
. We consider a similar question for
Generalized
T
-
Coloring
, a CSP problem that generalizes
Channel Assignment
. We show that
Generalized
T
-
Coloring
does not admit a
2
2
o
n
poly
(
r
)
-time algorithm, where
r
is the size of the instance.
In the
multicoloring
problem, also known as (
a
:
b
)-
coloring
or
b-fold coloring
, we are given a graph
G
and a set of
a
colors, and the task is to assign a subset of
b
colors to each vertex of
G
...so that adjacent vertices receive disjoint color subsets. This natural generalization of the classic coloring problem (the
b
=1 case) is equivalent to finding a homomorphism to the Kneser graph
KG
a,b
and gives relaxations approaching the fractional chromatic number.
We study the complexity of determining whether a graph has an (
a
:
b
)-coloring. Our main result is that this problem does not admit an algorithm with runtime
f
(
b
)ċ 2
o
(log
b
)ċ
n
for any computable
f(b)
unless the Exponential Time Hypothesis (ETH) fails. A (
b
+1)
n
ċ poly(
n
)-time algorithm due to Nederlof 33 shows that this is tight. A direct corollary of our result is that the graph homomorphism problem does not admit a 2
O
(
n
+
h
)
algorithm unless the ETH fails even if the target graph is required to be a Kneser graph. This refines the understanding given by the recent lower bound of Cygan et al. 9.
The crucial ingredient in our hardness reduction is the usage of
detecting matrices
of Lindström 28, which is a combinatorial tool that, to the best of our knowledge, has not yet been used for proving complexity lower bounds. As a side result, we prove that the runtime of the algorithms of Abasi et al. 1 and of Gabizon et al. 14 for the
r
-monomial detection problem are optimal under the ETH.
In the
k
-
Leaf Out-Branching
and
k
-
Internal Out-Branching
problems we are given a directed graph
D
with a designated root
r
and a nonnegative integer
k
. The question is whether there exists an ...outbranching rooted at
r
that has at least
k
leaves, or at least
k
internal vertices, respectively. Both these problems have been studied from the points of view of parameterized complexity and kernelization, and in particular for both of them kernels with
O
(
k
2
)
vertices are known on general graphs. In this work we show that
k
-
Leaf Out-Branching
admits a kernel with
O
(
k
) vertices on
H
-minor-free graphs, for any fixed family of graphs
H
, whereas
k
-
Internal Out-Branching
admits a kernel with
O
(
k
) vertices on any graph class of bounded expansion.
Live Memory analysis on the Linux platform has traditionally been difficult to perform. Memory analysis requires precise knowledge of struct layout information in memory, usually obtained through ...debugging symbols generated at compile time. The Linux kernel is however, highly configurable, implying that debugging information is rarely applicable to systems other than the ones that generated it. For incident response applications, obtaining the relevant debugging information is currently a slow and manual process, limiting its usefulness in rapid triaging. We have developed a tool dubbed, the Layout Expert which is able to calculate memory layout of critical kernel structures at runtime on the target system without requiring extra tools, such as the compiler tool-chain to be pre-installed. Our approach specifically addresses the need to adapt the generated profile to customized Linux kernels – an important first step towards a general version agnostic system. Our system is completely self sufficient and allows a live analysis tool to operate automatically on the target system. The layout expert operates in two phases: First it pre-parses the kernel source code into a preprocessor AST (Pre-AST) which is trimmed and stored as a data file in the analysis tool's distribution. When running on the target system, the running system configuration is used to resolve the Pre-AST into a C-AST, and combined with a pre-calculated layout model. The result is a running system specific profile with precise struct layout information. We evaluate the effectiveness of the Layout Expert in producing profiles for analysis of two very differently configured kernels. The produced profiles can be used to analyze the live memory through the /proc/kcore device without resorting to local or remote compilers. We finally consider future applications of this technique, such as memory acquisition.
PDF
