A phylogenetic tree is a graphical representation of an evolutionary history of taxa in which the leaves correspond to the taxa and the non-leaves correspond to speciations. One of important problems ...in phylogenetic analysis is to assemble a global phylogenetic tree from small phylogenetic trees, particularly, quartet trees.
Quartet
Compatibility
is the problem of deciding whether there is a phylogenetic tree inducing a given collection of quartet trees, and to construct such a phylogenetic tree if it exists. It is known that
Quartet
Compatibility
is NP-hard and that there are only a few results known for polynomial-time solvable subclasses. In this paper, we introduce two novel classes of quartet systems, called complete multipartite quartet system and full multipartite quartet system, and present polynomial-time algorithms for
Quartet
Compatibility
for these systems.
Fan-planar
graphs were recently introduced as a generalization of 1-
planar
graphs. A graph is
fan-planar
if it can be embedded in the plane, such that each edge that is crossed more than once, is ...crossed by a bundle of two or more edges incident to a common vertex. A graph is
outer-fan-planar
if it has a fan-planar embedding in which every vertex is on the outer face. If, in addition, the insertion of an edge destroys its outer-fan-planarity, then it is
maximal outer-fan-planar
. In this paper, we present a linear-time algorithm to test whether a given graph is
maximal outer-fan-planar
. The algorithm can also be employed to produce an outer-fan-planar embedding, if one exists. On the negative side, we show that testing fan-planarity of a graph is NP-complete, for the case where the
rotation system
(i.e., the cyclic order of the edges around each vertex) is given.
Subgraph Complementation Fomin, Fedor V.; Golovach, Petr A.; Strømme, Torstein J. F. ...
Algorithmica,
07/2020, Letnik:
82, Številka:
7
Journal Article
Recenzirano
Odprti dostop
A
subgraph complement
of the graph
G
is a graph obtained from
G
by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph
G
and ...graph class
G
, is there a subgraph complement of
G
which is in
G
? We show that this problem can be solved in polynomial time for various choices of the graphs class
G
, such as bipartite,
d
-degenerate, or cographs. We complement these results by proving that the problem is
NP
-complete when
G
is the class of regular graphs.
Let
C
be an arithmetic circuit of size
s
, given as input that computes a polynomial
f
∈
F
x
1
,
x
2
,
…
,
x
n
, where
F
is a finite field or the field of rationals. Using the Hadamard product of ...polynomials, we obtain new algorithms for the following two problems first studied by Koutis and Williams (Faster algebraic algorithms for path and packing problems, 2008,
https://doi.org/10.1007/978-3-540-70575-8_47
; ACM Trans Algorithms 12(3):31:1–31:18, 2016,
https://doi.org/10.1145/2885499
; Inf Process Lett 109(6):315–318, 2009,
https://doi.org/10.1016/j.ipl.2008.11.004
):
(
k
,
n
)
-
M
L
C
: is the problem of computing the sum of the coefficients of all degree-
k
multilinear monomials in the polynomial
f
. We obtain a deterministic algorithm of running time
n
↓
k
/
2
·
n
O
(
log
k
)
·
s
O
(
1
)
. This improvement over the
O
(
n
k
)
time brute-force search algorithm answers positively a question of Koutis and Williams (2016). As applications, we give exact counting algorithms, faster than brute-force search, for counting the number of copies of a tree of size
k
in a graph, and also the problem of exact counting of
m
-dimensional
k
-matchings.
k
-
M
M
D
: is the problem of checking if there is a degree-
k
multilinear monomial in the polynomial
f
with non-zero coefficient. We obtain a randomized algorithm of running time
O
(
4
.
32
k
·
n
O
(
1
)
)
. Additionally, our algorithm is polynomial space bounded.
Other results include fast deterministic algorithms for
(
k
,
n
)
-
M
L
C
and
k
-
M
M
D
problems for depth three circuits.
Budget Feasible Mechanisms on Matroids Leonardi, Stefano; Monaco, Gianpiero; Sankowski, Piotr ...
Algorithmica,
05/2021, Letnik:
83, Številka:
5
Journal Article
Recenzirano
Odprti dostop
Motivated by many practical applications, in this paper we study
budget feasible mechanisms
with the goal of procuring an independent set of a matroid. More specifically, we are given a matroid
M
=
(
...E
,
I
)
. Each element of the ground set
E
is controlled by a selfish agent and the cost of the element is private information of the agent itself. A budget limited buyer has additive valuations over the elements of
E
. The goal is to design an incentive compatible budget feasible mechanism which procures an independent set of the matroid of largest possible value. We also consider the more general case of the pair
M
=
(
E
,
I
)
satisfying only the hereditary property. This includes matroids as well as matroid intersection. We show that, given a polynomial time deterministic algorithm that returns an
α
-approximation to the problem of finding a maximum-value independent set in
M
, there exists an individually rational, truthful and budget feasible mechanism which is
(
3
α
+
1
)
-approximated and runs in polynomial time, thus yielding also a 4-approximation for the special case of matroids.
We study the problem of finding the minimum number of edges that, when cut, form a partition of the vertices into
k
sets of equal size. This is called the
k
-BALANCED PARTITIONING problem. The ...problem is known to be inapproximable within any finite factor on general graphs, while little is known about restricted graph classes.
We show that the
k
-BALANCED PARTITIONING problem remains APX-hard even when restricted to unweighted tree instances with constant maximum degree. If instead the diameter of the tree is constant we prove that the problem is NP-hard to approximate within
n
c
, for any constant
c
<1.
If vertex sets are allowed to deviate from being equal-sized by a factor of at most 1+
ε
, we show that solutions can be computed on weighted trees with cut cost no worse than the minimum attainable when requiring equal-sized sets. This result is then extended to general graphs via decompositions into trees and improves the previously best approximation ratio from
O
(log
1.5
(
n
)/
ε
2
) Andreev and Räcke in Theory Comput. Syst. 39(6):929–939,
2006
to
O
(log
n
). This also settles the open problem of whether an algorithm exists for which the number of edges cut is independent of
ε
.
We study algorithmic properties of the graph class
C
H
O
R
D
A
L
-
k
e
, that is, graphs that can be turned into a chordal graph by adding at most
k
edges or, equivalently, the class of graphs of ...fill-in at most
k
. It appears that a number of fundamental intractable optimization problems being parameterized by
k
admit
subexponential
algorithms on graphs from
C
H
O
R
D
A
L
-
k
e
. More precisely, we identify a large class of optimization problems on
C
H
O
R
D
A
L
-
k
e
solvable in time
2
O
(
k
log
k
)
·
n
O
(
1
)
. Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on
C
H
O
R
D
A
L
-
k
e
when parameterized by
k
but do not admit subexponential in
k
algorithms unless ETH fails. Besides subexponential time algorithms, the class of
C
H
O
R
D
A
L
-
k
e
graphs appears to be appealing from the perspective of kernelization (with parameter
k
). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in
k
kernels on
C
H
O
R
D
A
L
-
k
e
graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for
Weighted Clique
on
C
H
O
R
D
A
L
-
k
e
graphs. For (unweighted)
Independent Set
we design polynomial kernels on two interesting subclasses of
C
H
O
R
D
A
L
-
k
e
, namely,
I
N
T
E
R
V
A
L
-
k
e
and
S
P
L
I
T
-
k
e
graphs.
Ailon et al. (SIAM J Comput 40(2):350–375,
2011
) proposed a self-improving sorter that tunes its performance to an unknown input distribution in a training phase. The input numbers
x
1
,
x
2
,
…
,
x
...n
come from a product distribution, that is, each
x
i
is drawn independently from an arbitrary distribution
D
i
. We study two relaxations of this requirement. The first extension models hidden classes in the input. We consider the case that numbers in the same class are governed by linear functions of the same hidden random parameter. The second extension considers a hidden mixture of product distributions.
In the
k
-mismatch problem we are given a pattern of length
n
and a text and must find all locations where the Hamming distance between the pattern and the text is at most
k
. A series of recent ...breakthroughs have resulted in an ultra-efficient streaming algorithm for this problem that requires only
O
(
k
log
n
k
)
space and
O
(
log
n
k
(
k
log
k
+
log
3
n
)
)
time per letter (Clifford, Kociumaka, Porat, SODA 2019). In this work, we consider a strictly harder problem called dictionary matching with
k
mismatches. In this problem, we are given a dictionary of
d
patterns, where the length of each pattern is at most
n
, and must find all substrings of the text that are within Hamming distance
k
from one of the patterns. We develop a streaming algorithm for this problem with
O
(
k
d
log
k
d
polylog
n
)
space and
O
(
k
log
k
d
polylog
n
+
|
output
|
)
time per position of the text. The algorithm is randomised and outputs correct answers with high probability. On the lower bound side, we show that any streaming algorithm for dictionary matching with
k
mismatches requires
Ω
(
k
d
)
bits of space.
We show that there is a better-than-brute-force algorithm that, when given a small constant-depth Boolean circuit
C
made up of gates that compute constant-degree Polynomial Threshold functions or ...PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to
C
in significantly better than brute-force time. Formally, for any constants
d
,
k
, there is an
ε
>
0
such that the zero-error randomized algorithm counts the number of satisfying assignments to a given depth-
d
circuit
C
made up of
k
-PTF gates such that
C
has at most
n
1
+
ε
many wires. The algorithm runs in time
2
n
-
n
Ω
(
ε
)
.
Before our result, no algorithm for beating brute-force search was known for counting the number of satisfying assignments even for a single degree-
k
PTF (which is a depth-1 circuit with linearly many wires).We give two different algorithms for the case of a single PTF. The first uses a learning algorithm for learning degree-1 PTFs (or Linear Threshold Functions) using comparison queries due to Kane, Lovett and Moran (STOC 2018), and the second uses a proof of Hofmeister (COCOON 1996) for converting a degree-1 PTF to a depth-two threshold circuit with small weights. We show that both these ideas fit nicely into a memoization approach that yields the #SAT algorithms.
PDF
