It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in time 2O(tw)|V|O(1) for graphs G=(V,E) with a given tree decomposition of width tw. However, for ...nonlocal problems, like the fundamental class of connectivity problems, for a long time we did not know how to do this faster than twO(tw)|V|O(1). Recently, Cygan et al. (FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity problems running in time ctw|V|O(1) for a small constant c, e.g., for Hamiltonian Cycle and Steiner Tree. Naturally, this raises the question whether randomization is necessary to achieve this runtime; furthermore, it is desirable to also solve counting and weighted versions (the latter without incurring a pseudo-polynomial cost in the runtime in terms of the weights).
We present two new approaches rooted in linear algebra, based on matrix rank and determinants, which provide deterministic ctw|V|O(1) time algorithms, also for weighted and counting versions. For example, in this time we can solve Traveling Salesman or count the number of Hamiltonian cycles. The rank based ideas provide a rather general approach for speeding up even straightforward dynamic programming formulations by identifying “small” sets of representative partial solutions; we focus on the case of expressing connectivity via sets of partitions, but the essential ideas should have further applications. The determinant-based approach uses the Matrix Tree Theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming.
Photo identification is an important tool for estimating abundance and monitoring population trends over time. However, manually matching photographs to known individuals is time‐consuming. Motivated ...by recent developments in image recognition, we hosted a data science challenge on the crowdsourcing platform Kaggle to automate the identification of endangered North Atlantic right whales (Eubalaena glacialis). The winning solution automatically identified individual whales with 87% accuracy with a series of convolutional neural networks to identify the region of interest on an image, rotate, crop, and create standardized photographs of uniform size and orientation and then identify the correct individual whale from these passport‐like photographs. Recent advances in deep learning coupled with this fully automated workflow have yielded impressive results and have the potential to revolutionize traditional methods for the collection of data on the abundance and distribution of wild populations. Presenting these results to a broad audience should further bridge the gap between the data science and conservation science communities.
Aplicación del Aprendizaje Profundo a la Identificación Fotográfica de la Ballena Franca
Resumen
La identificación fotográfica es una herramienta importante para la estimación de la abundancia y el monitoreo de las tendencias poblacionales en el tiempo. Sin embargo, corresponder las fotografías con los individuos conocidos requiere de mucho tiempo. Motivados por los avances recientes en el reconocimiento de imágenes, decidimos acoger un reto de datos científicos en la plataforma de colaboración masiva Kaggle para automatizar la identificación de ballenas francas del Atlántico norte (Eubalaena glacialis), especie que se encuentra en peligro de extinción. La solución ganadora identificó automáticamente a las ballenas individuales con una certeza del 87% y con una serie de redes neurales convolucionales para identificar la región de interés en una imagen, rotar, recortar, y crear fotografías estandarizadas de tamaño y orientación uniforme y después identificar al individuo correcto a partir de estas fotografías tamaño pasaporte. Los avances recientes en el aprendizaje profundo acoplados a este flujo de trabajo completamente automatizado han producido resultados impresionantes y tienen el potencial para revolucionar los métodos tradicionales de recolección de datos de abundancia y distribución de las poblaciones silvestres. La presentación de estos resultados ante un público amplio debería reducir aún más el vacío que existe entre los datos científicos y las comunidades científicas para la conservación.
摘要
照片识别是评估种群丰度和监测种群动态的重要工具。然而, 人工地将照片与已知个体进行比对需耗费大量时间。受到最近图像识别领域发展的启发, 我们在众包平台 Kaggle 网站举办了一项数据科学挑战, 来自动识别濒危的北太平洋露脊鲸 (Eubalaena glacialis) 。获胜的方案能以87%的准确率自动识别鲸鱼个体, 它利用一系列卷积神经网络来找到图像上关注的区域, 加以旋转、裁剪, 并创建统一尺寸和方向的标准化照片, 然后从这些类似护照的照片中正确识别出鲸鱼个体。目前深度学习领域的进展加上这种完全自动化的工作流程, 已取得了显著成果, 并有可能给野生动物种群丰度和分布的传统数据收集方法带来变革。我们将这些结果呈现给广大受众, 以期进一步缩小数据科学和保护科学群体之间的距离。【翻译: 胡怡思; 审校: 聂永刚】
Article impact statement: Convolutional neural networks identified region, rotated, and cropped images, standardized photos, and identified correctly individual whales.
In the family of clustering problems we are given a set of objects (vertices of the graph), together with some observed pairwise similarities (edges). The goal is to identify clusters of similar ...objects by slightly modifying the graph to obtain a cluster graph (disjoint union of cliques). Hüffner et al. (Theory Comput. Syst.
47
(1), 196–217,
2010
) initiated the parameterized study of
Cluster Vertex Deletion
, where the allowed modification is vertex deletion, and presented an elegant
𝓞
min
(
2
k
k
6
log
k
+
n
3
,
2
k
km
n
log
n
)
-time fixed-parameter algorithm, parameterized by the solution size. In the last 5 years, this algorithm remained the fastest known algorithm for
Cluster Vertex Deletion
and, thanks to its simplicity, became one of the textbook examples of an application of the iterative compression principle. In our work we break the 2
k
-barrier for
Cluster Vertex Deletion
and present an
𝓞
(
1.910
2
k
(
n
+
m
)
)
-time branching algorithm. We achieve this improvement by a number of structural observations which we incorporate into the algorithm’s branching steps.
On Problems as Hard as CNF-SAT Cygan, Marek; Dell, Holger; Lokshtanov, Daniel ...
ACM transactions on algorithms,
06/2016, Letnik:
12, Številka:
3
Journal Article
Recenzirano
Odprti dostop
The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems has thrived since the mid-2000s. While exhaustive search remains asymptotically the fastest known ...algorithm for some basic problems, non-trivial exponential time algorithms have been found for a myriad of problems, including G
raph
C
oloring
, H
amiltonian
P
ath
, D
ominating
S
et
, and 3-CNF-S
at
. In some instances, improving these algorithms further seems to be out of reach. The CNF-S
at
problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time
O
(2
n
), where
n
is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-S
at
that run in time
o
(2
n
), no algorithm was able to improve the
growth rate
2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The
strong exponential time hypothesis
(SETH) by Impagliazzo and Paturi JCSS 2001 goes a little bit further and asserts that, for every ϵ < 1, there is a (large) integer
k
such that
k
-CNF-S
at
cannot be computed in time 2
ϵ
n
.
In this article, we show that, for every ϵ < 1, the problems H
itting
S
et
, S
et
S
plitting
, and NAE-S
at
cannot be computed in time
O
(2
ϵ
n
) unless SETH fails. Here
n
is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for S
et
C
over
and prove that, under this assumption, the fastest known algorithms for S
teiner
T
ree
, C
onnected
V
ertex
C
over
, S
et
P
artitioning
, and the pseudo-polynomial time algorithm for S
ubset
S
um
cannot be significantly improved. Finally, we justify our assumption about the hardness of S
et
C
over
by showing that the parity of the number of solutions to S
et
C
over
cannot be computed in time
O
(2
ϵ
n
) for any ϵ < 1 unless SETH fails.
We present Polite Teacher, a simple yet effective method for the task of semi-supervised instance segmentation. The proposed architecture relies on the Teacher-Student mutual learning framework. To ...filter out noisy pseudo-labels, we use confidence thresholding for bounding boxes and mask scoring for masks. The approach has been tested with CenterMask, a single-stage anchor-free detector. Tested on the COCO 2017 val dataset, our architecture significantly (approx. +8 pp. in mask AP) outperforms the baseline at different supervision regimes. To the best of our knowledge, this is one of the first works tackling the problem of semi-supervised instance segmentation and the first one devoted to an anchor-free detector. The code is available: github.com/AI-Clearing/PoliteTeacher.
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.
We introduce a concept of parameterizing a problem above the optimum solution of its natural linear programming relaxation and prove that the
node multiway cut
problem is fixed-parameter tractable ...(FPT) in this setting. As a consequence we prove that node multiway cut is FPT, when parameterized above the maximum separating cut, resolving an open problem of Razgon.
Our results imply
O
*
(4
k
) algorithms for vertex cover above maximum matching and almost 2-SAT as well as an
O
*
(2
k
) algorithm for node multiway cut with a standard parameterization by the solution size, improving previous bounds for these problems.
For an even integer
t
≥ 2, the Matching Connectivity matrix
H
t
is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph on
t
vertices; an entry
H
t
M
1
,
M
...2
is 1 if
M
1
and
M
2
form a Hamiltonian cycle and 0 otherwise. Motivated by applications for the Hamiltonicity problem, we show that
H
t
has rank exactly 2
t
/2−1
over GF(2). The upper bound is established by an explicit factorization of
H
t
as the product of two submatrices; the matchings labeling columns and rows, respectively, of the submatrices therefore form a basis
X
t
of
H
t
. The lower bound follows because the 2
t
/2−1
× 2
t
/2−1
submatrix with rows and columns labeled by
X
t
can be seen to have full rank.
We obtain several algorithmic results based on the rank of
H
t
and the particular structure of the matchings in
X
t
. First, we present a 1.888
n
n
O
(1)
time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Second, we give a Monte Carlo algorithm that solves the problem in (2 + √ 2)
pw
n
O
(1)
time when provided with a path decomposition of width pw for the input graph. Moreover, we show that this algorithm is best possible under the Strong Exponential Time Hypothesis, in the sense that an algorithm with running time (2 + √2 − ϵ)
pw
n
O
(1)
, for any ϵ > 0, would imply the breakthrough result of a (2 − ϵ
′
)
n
-time algorithm for CNF-Sat for some ϵ
′
> 0.
PDF
