A harmonious coloring of a k-uniform hypergraph H is a rainbow vertex coloring such that each k-set of colors appears on at most one edge. A rainbow coloring of H is achromatic if each k-set of ...colors appears on at least one edge. The harmonious number (resp. achromatic number) of H, denoted by h(H) (resp. ψ(H)) is the minimum (resp. maximum) possible number of colors in a harmonious (resp. achromatic) coloring of H. A class H of hypergraphs is fragmentable if for every H∈H, H can be fragmented into components of a bounded size by removing a “small” fraction of vertices.
We show that for every fragmentable class H of bounded degree hypergraphs, for every ϵ>0 and for every hypergraph H∈H with m≥m0(H,ϵ) edges we have h(H)≤(1+ϵ)k!mk and ψ(H)≥(1−ϵ)k!mk.
As corollaries, we answer a question posed by Blackburn concerning the maximum length of t-subset packing sequences of constant radius and derive an asymptotically tight bound on the minimum number of colors in a vertex-distinguishing edge coloring of cubic planar graphs, which is a step towards confirming a conjecture of Burris and Schelp.
A harmonious coloring of a k-uniform hypergraph H is a rainbow vertex coloring such that each k-set of colors appears on at most one edge. A rainbow coloring of H is achromatic if each k-set of ...colors appears on at least one edge. The harmonious (resp. achromatic) number of H, denoted by h(H) (resp. ψ(H)) is the minimum (resp. maximum) possible number of colors in a harmonious (resp. achromatic) coloring of H. A class H of hypergraphs is fragmentable if for every H∈H, H can be fragmented to components of a bounded size by removing a “small” fraction of vertices.
We show that for every fragmentable class H of bounded degree hypergraphs, for every ϵ>0 and for every hypergraph H∈H with m≥m0(H,ϵ) edges we have h(H)≤(1+ϵ)k!mk and ψ(H)≥(1−ϵ)k!mk.
As corollaries, we answer a question posed by Blackburn (concerning the maximum length of packing t-subset sequences of constant radius) and derive an asymptotically tight bound on the minimum number of colors in a vertex-distinguishing edge coloring of cubic planar graphs (which is a step towards confirming a conjecture of Burris and Schelp).
Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class
∃
R
plays a crucial role in the study of geometric problems. Sometimes
∃
R
is referred to as the ...‘real analog’ of
NP
. While
NP
is a class of computational problems that deals with existentially quantified
boolean
variables,
∃
R
deals with existentially quantified
real
variables. In analogy to
Π
2
p
and
Σ
2
p
in the famous polynomial hierarchy, we study the complexity classes
∀
∃
R
and
∃
∀
R
with
real
variables. Our main interest is the
Area
Universality
problem, where we are given a plane graph
G
, and ask if for each assignment of areas to the inner faces of
G
, there exists a straight-line drawing of
G
realizing the assigned areas. We conjecture that
Area
Universality
is
∀
∃
R
-complete and support this conjecture by proving
∃
R
- and
∀
∃
R
-completeness of two variants of
Area
Universality
. To this end, we introduce tools to prove
∀
∃
R
-hardness and membership. Finally, we present geometric problems as candidates for
∀
∃
R
-complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.
We consider subexponential algorithms finding weighted homomorphisms from intersection graphs of curves (string graphs) with n vertices to a fixed graph H. We provide a complete dichotomy: if H has ...no two vertices sharing two common neighbors, then the problem can be solved in time 2O(n2/3logn), otherwise there is no subexponential algorithm, assuming the ETH. Then we consider locally constrained homomorphisms. We show that for each target graph H, the locally injective and locally bijective homomorphism problems can be solved in time 2O(nlogn) in string graphs. For locally surjective homomorphisms we show a dichotomy for H being a path or a cycle. If H is P3 or C4, then the problem can be solved in time 2O(n2/3log3/2n) in string graphs; otherwise, assuming the ETH, there is no subexponential algorithm. As corollaries, we obtain new results concerning the complexity of homomorphism problems in Pt-free graphs.
Abstract
Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class
$$\exists \mathbb {R}$$
∃
R
plays a crucial role in the study of geometric problems. ...Sometimes
$$\exists \mathbb {R}$$
∃
R
is referred to as the ‘real analog’ of
NP
. While
NP
is a class of computational problems that deals with existentially quantified
boolean
variables,
$$\exists \mathbb {R}$$
∃
R
deals with existentially quantified
real
variables. In analogy to
$$\Pi _2^p$$
Π
2
p
and
$$\Sigma _2^p$$
Σ
2
p
in the famous polynomial hierarchy, we study the complexity classes
$$\forall \exists \mathbb {R}$$
∀
∃
R
and
$$ \exists \forall \mathbb {R}$$
∃
∀
R
with
real
variables. Our main interest is the
Area
Universality
problem, where we are given a plane graph
G
, and ask if for each assignment of areas to the inner faces of
G
, there exists a straight-line drawing of
G
realizing the assigned areas. We conjecture that
Area
Universality
is
$$\forall \exists \mathbb {R}$$
∀
∃
R
-complete and support this conjecture by proving
$$\exists \mathbb {R}$$
∃
R
- and
$$\forall \exists \mathbb {R}$$
∀
∃
R
-completeness of two variants of
Area
Universality
. To this end, we introduce tools to prove
$$\forall \exists \mathbb {R}$$
∀
∃
R
-hardness and membership. Finally, we present geometric problems as candidates for
$$\forall \exists \mathbb {R}$$
∀
∃
R
-complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.
A graph is called Pt-free if it does not contain the path on t vertices as an induced subgraph. Let H be a multigraph with the property that any two distinct vertices share at most one common ...neighbour. We show that the generating function for (list) graph homomorphisms from G to H can be calculated in subexponential time 2Otnlog(n) for n=|V(G)| in the class of Pt-free graphs G. As a corollary, we show that the number of 3-colourings of a Pt-free graph G can be found in subexponential time. On the other hand, no subexponential time algorithm exists for 4-colourability of Pt-free graphs assuming the Exponential Time Hypothesis. Along the way, we prove that Pt-free graphs have pathwidth that is linear in their maximum degree.
Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class
\documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
...\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\exists \mathbb {R}$$\end{document}
∃
R
plays a crucial role in the study of geometric problems. Sometimes
\documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\exists \mathbb {R}$$\end{document}
∃
R
is referred to as the ‘real analog’ of
NP
. While
NP
is a class of computational problems that deals with existentially quantified
boolean
variables,
\documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\exists \mathbb {R}$$\end{document}
∃
R
deals with existentially quantified
real
variables. In analogy to
\documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\Pi _2^p$$\end{document}
Π
2
p
and
\documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\Sigma _2^p$$\end{document}
Σ
2
p
in the famous polynomial hierarchy, we study the complexity classes
\documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\forall \exists \mathbb {R}$$\end{document}
∀
∃
R
and
\documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$ \exists \forall \mathbb {R}$$\end{document}
∃
∀
R
with
real
variables. Our main interest is the
Area
Universality
problem, where we are given a plane graph
G
, and ask if for each assignment of areas to the inner faces of
G
, there exists a straight-line drawing of
G
realizing the assigned areas. We conjecture that
Area
Universality
is
\documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\forall \exists \mathbb {R}$$\end{document}
∀
∃
R
-complete and support this conjecture by proving
\documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\exists \mathbb {R}$$\end{document}
∃
R
- and
\documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\forall \exists \mathbb {R}$$\end{document}
∀
∃
R
-completeness of two variants of
Area
Universality
. To this end, we introduce tools to prove
\documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\forall \exists \mathbb {R}$$\end{document}
∀
∃
R
-hardness and membership. Finally, we present geometric problems as candidates for
\documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$\forall \exists \mathbb {R}$$\end{document}
∀
∃
R
-complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.
In the Feedback Vertex Set problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The Subset Feedback Vertex Set problem requires S to intersect only those cycles that ...include a vertex of some specified set T. We also consider the Weighted Subset Feedback Vertex Set problem, where each vertex u has weight w(u)>0 and we ask that S has small weight. By combining known NP-hardness results with new polynomial-time results we prove full complexity dichotomies for Subset Feedback Vertex Set and Weighted Subset Feedback Vertex Set for H-free graphs, that is, graphs that do not contain a graph H as an induced subgraph.
PDF
