Twin-width I: Tractable FO Model Checking Bonnet, Édouard; Kim, Eun Jung; Thomassé, Stéphan ...
Journal of the ACM,
02/2022, Letnik:
69, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Inspired by a
width
invariant defined on permutations by Guillemot and Marx SODA’14, we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width ...graphs, map graphs,
K
t
-free unit
d
-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a
sequence of
d
-contractions
, witness that the twin-width is at most
d
. We show that FO model checking, that is deciding if a given first-order formula ϕ evaluates to true for a given binary structure
G
on a domain
D
, is FPT in |ϕ| on classes of bounded twin-width, provided the witness is given. More precisely, being given a
d
-contraction sequence for
G
, our algorithm runs in time
f
(
d
,|ϕ |) · |D| where
f
is a computable but non-elementary function. We also prove that bounded twin-width is preserved under FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarský et al. FOCS’15.
In this paper, we show that the problems
Disjoint Cycles and
Disjoint Paths do not have polynomial kernels, unless
N
P
⊆
c
o
N
P
/
p
o
l
y
. Thus, these problems do not allow polynomial time ...preprocessing that results in instances whose size is bounded by a polynomial in the parameter at hand. We build upon recent results by Bodlaender et al.
6 and Fortnow and Santhanam
20, that show that NP-complete problems that are ‘or-compositional’ do not have polynomial kernels, unless
N
P
⊆
c
o
N
P
/
p
o
l
y
. To this machinery, we add a notion of transformation, and obtain that
Disjoint Cycles, and
Disjoint Paths do not have polynomial kernels, unless
N
P
⊆
c
o
N
P
/
p
o
l
y
. For the proof, we introduce a problem on strings, called
Disjoint Factors, and first show that this problem has no polynomial kernel unless
N
P
⊆
c
o
N
P
/
p
o
l
y
. We also show that the related
Disjoint Cycles Packing problem has a kernel of size
O
(
k
log
k
)
.
Twin-width and Polynomial Kernels Bonnet, Édouard; Kim, Eun Jung; Reinald, Amadeus ...
Algorithmica,
11/2022, Letnik:
84, Številka:
11
Journal Article
Recenzirano
Odprti dostop
We study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main result is that a ...polynomial kernel for
k
-Dominating Set
on graphs of twin-width at most 4 would contradict a standard complexity-theoretic assumption. The reduction is quite involved, especially to get the twin-width upper bound down to 4, and can be tweaked to work for
Connected
k
-Dominating Set
and
Total
k
-Dominating Set
(albeit with a worse upper bound on the twin-width). The
k
-Independent Set
problem admits the same lower bound by a much simpler argument, previously observed ICALP ’21, which extends to
k
-Independent Dominating Set
,
k
-Path
,
k
-Induced Path
,
k
-Induced Matching
, etc. On the positive side, we obtain a simple quadratic vertex kernel for
Connected
k
-Vertex Cover
and
Capacitated
k
-Vertex Cover
on graphs of bounded twin-width. Interestingly the kernel applies to graphs of Vapnik–Chervonenkis density 1, and does not require a witness sequence. We also present a more intricate
O
(
k
1.5
)
vertex kernel for
Connected
k
-Vertex Cover
. Finally we show that deciding if a graph has twin-width at most 1 can be done in polynomial time, and observe that most optimization/decision graph problems can be solved in polynomial time on graphs of twin-width at most 1.
We provide a O(k2logk) vertex kernel for cograph edge editing. This improves a cubic kernel found by Guillemot, Havet, Paul and Perez (Guillemot et al., 2010) which involved four reduction rules. We ...generalize one of their rules, based on packing of induced paths of length four, by introducing t-modules, which are modules up to t edge modifications. The key fact is that large t-modules cannot be edited more than t times, and this allows to obtain a near quadratic kernel. The extra logk factor seems tricky to remove as it is necessary in the combinatorial lemma on trees which is central in our proof. Nevertheless, we think that a quadratic bound should be reachable.
Let G=(V,E) be a graph. A k-neighborhood in G is a set of vertices consisting of all the vertices at distance at most k from some vertex of G. The hypergraph on vertex set V whose edge set consists ...of all the k-neighborhoods of G for all k is the neighborhood hypergraph of G. Our goal in this paper is to investigate the complexity of a graph in terms of its neighborhoods. Precisely, we define the distance VC-dimension of a graph G as the maximum taken over all induced subgraphs G′ of G of the VC-dimension of the neighborhood hypergraph of G′. For a class of graphs, having bounded distance VC-dimension both generalizes minor closed classes and graphs with bounded clique-width.
Our motivation is a result of Chepoi et al. (2007) asserting that every planar graph of diameter 2ℓ can be covered by a bounded number of balls of radius ℓ. In fact, they obtained the existence of a function f such that every set F of balls of radius ℓ in a planar graph admits a hitting set of size f(ν) where ν is the maximum number of pairwise disjoint elements of F.
Our goal is to generalize the proof of Chepoi et al. (2007) with the unique assumption of bounded distance VC-dimension of neighborhoods. In other words, the set of balls of fixed radius in a graph with bounded distance VC-dimension has the Erdős–Pósa property.
We show that there exist convex n-gons P and Q such that the largest convex polygon in the Minkowski sum P+Q has size Θ(nlogn). This matches an upper bound of Tiwary.
Clique covers of H-free graphs Nguyen, Tung; Scott, Alex; Seymour, Paul ...
European journal of combinatorics,
20/May , Letnik:
118
Journal Article
Recenzirano
It takes n2/4 cliques to cover all the edges of a complete bipartite graph Kn/2,n/2, but how many cliques does it take to cover all the edges of a graph G if G has no Kt,t induced subgraph? We prove ...that O(n2−1/(2t)) cliques suffice for every n-vertex graph; and also prove that, even for graphs with no stable set of size four, we may need more than linearly many cliques. This settles two questions discussed at a recent conference in Lyon.
In this paper, we investigate the complexity of
Maximum Independent Set
(
MIS
) in the class of
H
-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem ...remains
NP
-hard for most graphs
H
, we study its fixed-parameter tractability and make progress towards a dichotomy between FPT and
W
1-hard cases. We first show that
MIS
remains
W
1-hard in graphs forbidding simultaneously
K
1
,
4
, any finite set of cycles of length at least 4, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski et al. concerning
C
4
-free graphs. Then we extend the polynomial algorithm of Alekseev when
H
is a disjoint union of edges to an FPT algorithm when
H
is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of
iterative expansion
accompanied by the extraction of a particular structure using Ramsey’s theorem. Iterative expansion is a maximization version of the so-called
iterative compression
. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs
H
.
We show that for every ℓ, there exists dℓ such that every 3-edge-connected graph with minimum degree dℓ can be edge-partitioned into paths of length ℓ (provided that its number of edges is divisible ...by ℓ). This improves a result asserting that 24-edge-connectivity and high minimum degree provides such a partition. This is best possible as 3-edge-connectivity cannot be replaced by 2-edge connectivity.
The maximum stable set problem is NP-hard, even when restricted to triangle-free graphs. In particular, one cannot expect a polynomial time algorithm deciding if a bull-free graph has a stable set of ...size
k
, when
k
is part of the instance. Our main result in this paper is to show the existence of an FPT algorithm when we parameterize the problem by the solution size
k
. A polynomial kernel is unlikely to exist for this problem. We show however that our problem has a polynomial size Turing-kernel. More precisely, the hard cases are instances of size
O
(
k
5
)
. As a byproduct, if we forbid odd holes in addition to the bull, we show the existence of a polynomial time algorithm for the stable set problem. We also prove that the chromatic number of a bull-free graph is bounded by a function of its clique number and the maximum chromatic number of its triangle-free induced subgraphs. All our results rely on a decomposition theorem for bull-free graphs due to Chudnovsky which is modified here, allowing us to provide extreme decompositions, adapted to our computational purpose.
PDF
