Let
M
=(
E
,
I
) be a matroid and let
S
={
S
1
, ċ ,
S
t
} be a family of subsets of
E
of size
p
. A subfamily
Ŝ
⊆
S
is
q
-
representative
for
S
if for every set
Y
⊆
E
of size at most
q
, if there is ...a set
X
∈
S
disjoint from
Y
with
X
∪
Y
∈
I
, then there is a set
Xˆ
∈
Ŝ
disjoint from
Y
with
Xˆ
∪
Y
∈
I
. By the classic result of Bollobás, in a uniform matroid, every family of sets of size
p
has a
q
-representative family with at most (
p
+
q
p
) sets. In his famous “two families theorem” from 1977, Lovász proved that the same bound also holds for any matroid representable over a field F. We give an efficient construction of a
q
-representative family of size at most (
p
+
q
p
) in time bounded by a polynomial in (
p
+
q
p
),
t
, and the time required for field operations.
We demonstrate how the efficient construction of representative families can be a powerful tool for designing single-exponential parameterized and exact exponential time algorithms. The applications of our approach include the following:
—In the L
ong
D
irected
C
ycle
problem, the input is a directed
n
-vertex graph
G
and the positive integer
k
. The task is to find a directed cycle of length at least
k
in
G
, if such a cycle exists. As a consequence of our 6.75
k
+
o
(
k
)
n
O
(1)
time algorithm, we have that a directed cycle of length at least log
n
, if such a cycle exists, can be found in polynomial time.
—In the M
inimum
E
quivalent
G
raph
(MEG) problem, we are seeking a spanning subdigraph
D
′ of a given
n
-vertex digraph
D
with as few arcs as possible in which the reachability relation is the same as in the original digraph
D
.
—We provide an alternative proof of the recent results for algorithms on graphs of bounded treewidth showing that many “connectivity” problems such as H
amiltonian
C
ycle
or S
teiner
T
ree
can be solved in time 2
O
(
t
)
n on
n
-vertex graphs of treewidth at most
t
.
For the special case of uniform matroids on
n
elements, we give a faster algorithm to compute a representative family. We use this algorithm to provide the fastest known deterministic parameterized algorithms for
k
-P
ath
,
k
-T
ree
, and, more generally,
k
-S
ubgraph
I
somorphism
, where the
k
-vertex pattern graph is of constant treewidth.
For more than 40 years, Branch & Reduce exponential-time backtracking algorithms have been among the most common tools used for finding exact solutions of NP-hard problems. Despite that, the way to ...analyze such recursive algorithms is still far from producing tight worst-case running time bounds. Motivated by this, we use an approach, that we call “Measure & Conquer”, as an attempt to step beyond such limitations. The approach is based on the careful design of a nonstandard measure of the subproblem size; this measure is then used to lower bound the progress made by the algorithm at each branching step. The idea is that a smarter measure may capture behaviors of the algorithm that a standard measure might not be able to exploit, and hence lead to a significantly better worst-case time analysis.
In order to show the potentialities of Measure & Conquer, we consider two well-studied NP-hard problems: minimum dominating set and maximum independent set. For the first problem, we consider the current best algorithm, and prove (thanks to a better measure) a much tighter running time bound for it. For the second problem, we describe a new, simple algorithm, and show that its running time is competitive with the current best time bounds, achieved with far more complicated algorithms (and standard analysis).
Our examples show that a good choice of the measure, made in the very first stages of exact algorithms design, can have a tremendous impact on the running time bounds achievable.
Low-rank binary matrix approximation is a generic problem where one seeks a good approximation of a binary matrix by another binary matrix with some specific properties. A good approximation means ...that the difference between the two matrices in some matrix norm is small. The properties of the approximation binary matrix could be: a small number of different columns, a small binary rank or a small Boolean rank. Unfortunately, most variants of these problems are NP-hard. Due to this, we initiate the systematic algorithmic study of low-rank binary matrix approximation from the perspective of parameterized complexity. We show in which cases and under what conditions the problem is fixed-parameter tractable, admits a polynomial kernel and can be solved in parameterized subexponential time.
(Meta) Kernelization Bodlaender, Hans L; Fomin, Fedor V; Lokshtanov, Daniel ...
Journal of the ACM,
12/2016, Letnik:
63, Številka:
5
Journal Article
Recenzirano
Odprti dostop
In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a ...polynomial in k while preserving the answer. In this work, we give two meta-theorems on kernelization. The first theorem says that all problems expressible in counting monadic second-order logic and satisfying a coverability property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker coverability property admit a linear kernel on graphs of bounded genus. These theorems unify and extend all previously known kernelization results for planar graph problems.
Graph searching encompasses a wide variety of combinatorial problems related to the problem of capturing a fugitive residing in a graph using the minimum number of searchers. In this annotated ...bibliography, we give an elementary classification of problems and results related to graph searching and provide a source of bibliographical references on this field.
Diverse collections in matroids and graphs Fomin, Fedor V.; Golovach, Petr A.; Panolan, Fahad ...
Mathematical programming,
2024/3, Letnik:
204, Številka:
1-2
Journal Article
Recenzirano
Odprti dostop
We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the
Weighted Diverse Bases
problem consists of a matroid
M
, ...a weight function
ω
:
E
(
M
)
→
N
, and integers
k
≥
1
,
d
≥
1
. The task is to decide if there is a collection of
k
bases
B
1
,
⋯
,
B
k
of
M
such that the weight of the symmetric difference of any pair of these bases is at least
d
. The input to the
Weighted Diverse Common Independent Sets
problem consists of two matroids
M
1
,
M
2
defined on the same ground set
E
, a weight function
ω
:
E
→
N
, and integers
k
≥
1
,
d
≥
1
. The task is to decide if there is a collection of
k
common independent sets
I
1
,
⋯
,
I
k
of
M
1
and
M
2
such that the weight of the symmetric difference of any pair of these sets is at least
d
. The input to the
Diverse Perfect Matchings
problem consists of a graph
G
and integers
k
≥
1
,
d
≥
1
. The task is to decide if
G
contains
k
perfect matchings
M
1
,
⋯
,
M
k
such that the symmetric difference of any two of these matchings is at least
d
. We show that none of these problems can be solved in polynomial time unless
P
=
NP
. We derive fixed-parameter tractable (
FPT
) algorithms for all three problems with
(
k
,
d
)
as the parameter, and present a
p
o
l
y
(
k
,
d
)
-sized kernel for
Weighted Diverse Bases
.
For a graph
H
, a graph
G
is an
H
-graph if it is an intersection graph of connected subgraphs of some subdivision of
H
.
H
-graphs naturally generalize several important graph classes like interval ...graphs or circular-arc graph. This class was introduced in the early 1990s by Bíró, Hujter, and Tuza. Recently, Chaplick et al. initiated the algorithmic study of
H
-graphs by showing that a number of fundamental optimization problems like M
aximum
C
lique
, M
aximum
I
ndependent
S
et
, or M
inimum
D
ominating
S
et
are solvable in polynomial time on
H
-graphs. We extend and complement these algorithmic findings in several directions. First we show that for every fixed
H
, the class of
H
-graphs is of logarithmically-bounded boolean-width (via mim-width). Pipelined with the plethora of known algorithms on graphs of bounded boolean-width, this describes a large class of problems solvable in polynomial time on
H
-graphs. We also observe that
H
-graphs are graphs with polynomially many minimal separators. Combined with the work of Fomin, Todinca and Villanger on algorithmic properties of such classes of graphs, this identify another wide class of problems solvable in polynomial time on
H
-graphs. The most fundamental optimization problems among the problems solvable in polynomial time on
H
-graphs are M
aximum
C
lique
, M
aximum
I
ndependent
S
et
, and M
inimum
D
ominating
S
et
. We provide a more refined complexity analysis of these problems from the perspective of parameterized complexity. We show that M
aximum
I
ndependent
S
et
and M
inimum
D
ominating
S
et
are W1-hard being parameterized by the size of
H
plus the size of the solution. On the other hand, we prove that when
H
is a tree, then M
inimum
D
ominating
S
et
is fixed-parameter tractable parameterized by the size of
H
. For M
aximum
C
lique
we show that it admits a polynomial kernel parameterized by
H
and the solution size.
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.
We give a new general approach for designing exact exponential-time algorithms for
subset problems
. In a subset problem the input implicitly describes a family of sets over a universe of size
n
and ...the task is to determine whether the family contains at least one set. A typical example of a subset problem is W
EIGHTED
d
-SAT. Here, the input is a CNF-formula with clauses of size at most
d
, and an integer
W
. The universe is the set of variables and the variables have integer weights. The family contains all the subsets
S
of variables such that the total weight of the variables in
S
does not exceed
W
and setting the variables in
S
to 1 and the remaining variables to 0 satisfies the formula. Our approach is based on “monotone local search,” where the goal is to extend a partial solution to a solution by adding as few elements as possible. More formally, in the extension problem, we are also given as input a subset
X
of the universe and an integer
k
. The task is to determine whether one can add at most
k
elements to
X
to obtain a set in the (implicitly defined) family. Our main result is that a
c
k
n
O(1)
time algorithm for the extension problem immediately yields a randomized algorithm for finding a solution of any size with running time
O
((2−1/
c
)
n
).
In many cases, the extension problem can be reduced to simply finding a solution of size at most
k
. Furthermore, efficient algorithms for finding small solutions have been extensively studied in the field of parameterized algorithms. Directly applying these algorithms, our theorem yields in one stroke significant improvements over the best known exponential-time algorithms for several well-studied problems, including
d
-H
ITTING
S
ET
, F
EEDBACK
V
ERTEX
S
ET
, N
ODE
U
NIQUE
L
ABEL
C
OVER
, and W
EIGHTED
d
-SAT. Our results demonstrate an interesting and very concrete connection between parameterized algorithms and exact exponential-time algorithms.
We also show how to derandomize our algorithms at the cost of a subexponential multiplicative factor in the running time. Our derandomization is based on an efficient construction of a new pseudo-random object that might be of independent interest. Finally, we extend our methods to establish new combinatorial upper bounds and develop enumeration algorithms.
In the classic
Integer Programming Feasibility
(IPF) problem, the objective is to decide whether, for a given
m
×
n
matrix
A
and an
m
-vector
b
=
(
b
1
,
⋯
,
b
m
)
, there is a non-negative integer
n
...-vector
x
such that
A
x
=
b
. Solving (IPF) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input. The classic pseudo-polynomial time algorithm of Papadimitriou J. ACM 1981 for instances of (IPF) with a constant number of constraints was only recently improved upon by Eisenbrand and Weismantel SODA 2018 and Jansen and Rohwedder ITCS 2019. Jansen and Rohwedder designed an algorithm for (IPF) with running time
O
(
m
Δ
)
m
log
(
Δ
)
log
(
Δ
+
‖
b
‖
∞
)
+
O
(
m
n
)
. Here,
Δ
is an upper bound on the absolute values of the entries of
A
. We continue this line of work and show that under the Exponential Time Hypothesis (ETH), the algorithm of Jansen and Rohwedder is nearly optimal, by proving a lower bound of
n
o
(
m
log
m
)
·
‖
b
‖
∞
o
(
m
)
. We also prove that assuming ETH, (IPF) cannot be solved in time
f
(
m
)
·
(
n
·
‖
b
‖
∞
)
o
(
m
log
m
)
for any computable function
f
. This motivates us to pick up the line of research initiated by Cunningham and Geelen IPCO 2007 who studied the complexity of solving (IPF) with non-negative matrices in which the number of constraints may be unbounded, but the branch-width of the column-matroid corresponding to the constraint matrix is a constant. We prove a lower bound on the complexity of solving (IPF) for such instances and obtain optimal results with respect to a closely related parameter, path-width. Specifically, we prove
matching
upper and lower bounds for (IPF) when the
path-width
of the corresponding column-matroid is a constant .
PDF
