Dimitris Achlioptas ( ).Invited TalkAlgorithmic Barriers from Phase Transitions in Graphs Abstract: For a number of optimization problems on random graphs and hypergraphs, e.g., k-colorings, there is a very big gap between the largest average degree for which known polynomial-time algorithms can find solutions, and the largest average degree for which solutions provably exist. We study this phenomenon by examining how sets of solutions evolve as edges are added. We prove in a precise mathematical sense that, for each problem studied, the barrier faced by algorithms corresponds to a phase transition in the problem’s solution-space geometry. Roughly speaking, at some problem-specific critical density, the set of solutions shatters and goes from being a single giant ball to exponentially many, well-separated, tiny pieces. All known polynomial-time algorithms work in the ball regime, but stop as soon as the shattering occurs. Besides giving a geometric view of the solution space of random instances our results provide novel constructions of one-way functions.Erik Demaine ( ).Invited TalkAlgorithmic Graph Minors and Bidimensionality Abstract: Graph Minor Theory, developed by Robertson and
Seymour over two decades, provides powerful structural results about a
wide family of graph classes (anything closed under deletion and
contraction). In recent years, this theory has been extended and
generalized to apply to many algorithmic problems. Bidimensionality
theory is one approach to algorithmic graph minor theory. This theory
provides general tools for designing fast (constructive, often
subexponential) fixed-parameter algorithms, kernelizations, and
approximation algorithms (often PTASs), for a wide variety of NP-hard
graph problems for graphs excluding a fixed minor. For example, some of
the most general algorithms for feedback vertex set and connected
dominating set are based on bidimensionality. Another approach is
``deletion and contraction decompositions'', which split any graph
excluding a fixed minor into a bounded number of small-treewidth
graphs. For example, this approach has led to some of the most general
algorithms for graph coloring and the Traveling Salesman Problem on
graphs. I will describe these and other approaches to efficient
algorithms through graph minors.Yota Otachi, Hans L. Bodlaender and Erik Jan van Leeuwen. Complexity Results for the Spanning Tree Congestion Problem Abstract: We study the
problem of determining the spanning tree congestion of a graph. We
present some sharp contrasts in the complexity of this problem. First,
we show that for every fixed k and d the problem to determine whether a
given graph has spanning tree congestion at most k can be solved in
linear time for graphs of degree at most d. In contrast, if we allow
only one vertex of unbounded degree, the problem immediately becomes
NP-complete for any fixed k >= 10. For very small values of k
however, the problem becomes polynomially solvable. We also show that it
is NP-hard to approximate the spanning tree congestion within a factor
better than 11/10. On planar graphs, we prove the problem is NP-hard in
general, but solvable in linear time for fixed k. Marcin Kaminski. Max-Cut and containment relations in graphs Abstract:
We study (Simple) Max-Cut in classes of graphs deﬁned by forbidding a
single graph as a subgraph, induced subgraph, or minor. For the ﬁrst two
containment relations, we prove dichotomy theorems. For the minor
order, we show how to solve Max-Cut in polynomial time for the class
obtained by forbidding a graph with crossing number at most one (this
generalizes a known result for K5-minor-free graphs) and identify an
open problem which is the missing case for a dichotomy theorem. Stavros Nikolopoulos and Kyriaki Ioannidou. The Longest Path Problem is Polynomial on Cocomparability Graphs Abstract: The
longest path problem is the problem of finding a path of maximum length
in a graph. As a generalization of the Hamiltonian path problem, it is
NP-complete on general graphs and, in fact, on every class of graphs
that the Hamiltonian path problem is NP-complete. Polynomial solutions
for the longest path problem have recently been proposed for weighted
trees, ptolemaic graphs, bipartite permutation graphs, interval graphs,
and some small classes of graphs. Although the Hamiltonian path problem
on cocomparability graphs was proved to be polynomial almost two decades
ago~\cite{Damasc92}, the complexity status of the longest path problem
on cocomparability graphs has remained open until now; actually, the
complexity status of the problem has remained open even on the smaller
class of permutation graphs. In this paper, we present a polynomial-time
algorithm for solving the longest path problem on the class of
cocomparability graphs. Our result resolves the open question for the
complexity of the problem on such graphs, and since cocomparability
graphs form a superclass of both interval and permutation graphs,
extends the polynomial solution of the longest path problem on interval
graphs~\cite{Ioan-Mer-Nik09} and provides polynomial solution to the
class of permutation graphs. Petr Golovach, Dieter Kratsch and Jean-Francois Couturier. Colorings With Few Colors: Counting, Enumeration and Combinatorial Bounds Abstract:
Enumeration and counting problems on edge colorings, total colorings and
$L(2,1)$-labelings of graphs are studied. The major part deals with the
enumeration of three types of colorings with few colors: edge
$3$-colorings, total $4$-colorings and the $L(2,1)$-labelings of span
$5$ in connected cubic graphs. Branching algorithms to enumerate the
colorings in connected cubic graphs are established. They imply upper
bounds on the maximum number of colorings in any $n$-vertex connected
cubic graphs. Lower bounds are also provided. Particularly, for edge
$3$-colorings the following is achieved: there is a branching algorithm
to enumerate all edge $3$-colorings of a connected cubic graph in time
$O^*(2^{5n/8})$. This implies that the maximum number of edge
$3$-colorings in an $n$-vertex connected cubic graph is
$O^*(2^{5n/8})$. Finally the maximum number of edge $3$-colorings in
an $n$-vertex connected cubic graph is lower bounded by $12^{n/10}$.
Dynamic programming algorithms to count the number of edge $k$-colorings
and total $k$-colorings for graphs of bounded pathwidth are presented.
We also provide a dynamic programming algorithm to count the number of
$L(2,1)$-labelings of span $4$ for graphs of maximum degree three. Tamas Fleiner. On stable matchings and flows Abstract: We
describe a flow model that generalizes ordinary network flows the same
way as stable matchings generalize the bipartite matching problem. We
prove that there always exists a stable flow, generalize the lattice
structure of stable marriages to stable flows. Hajo Broersma, Petr Golovach, Daniel Paulusma and Jian Song. Narrowing down the gap on the complexity of coloring P_k-free graphs Abstract:
A graph is P_k-free if it does not contain an induced subgraph
isomorphic to a path on k vertices. We show that deciding whether a
P_8-free graph can be colored with at most four colors is an NP-complete
problem. This improves a result of Le, Randerath, and Schiermeyer, who
showed that 4-coloring is NP-complete for P_9$-free graphs, and a result
of Woeginger and Sgall, who showed that 5-coloring is NP-complete for
P_8-free graphs. Additionally, we prove that the pre-coloring extension
version of 4-coloring is NP-complete for P_7-free graphs, but that the
pre-coloring extension version of 3-coloring is polynomially solvable
for (P_4+P_2)-free graphs, a subclass of P_7-free graphs. Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov and Jesper Nederlof. Computing the cutwidth of bipartite permutation graphs in linear time Abstract:
The problem of determining the cutwidth of a graph is a notoriously
hard problem which remains NP-complete under severe restrictions on
input graphs. Until recently, non-trivial polynomial-time cutwidth
algorithms were known only for subclasses of graphs of bounded
treewidth. In WG 2008, Heggernes et al.~initiated the study of cutwidth
on graph classes containing graphs of unbounded treewidth, and showed
that a greedy algorithm computes the cutwidth of threshold graphs. We
continue this line of research and present the first polynomial-time
algorithm for computing the cutwidth of bipartite permutation graphs.
Our algorithm runs in linear time. We stress that the cutwidth problem
is NP-complete on bipartite graphs and its computational complexity is
open even on small subclasses of permutation graphs, such as trivially
perfect graphs. Mathieu Liedloff, Ioan Todinca and Yngve Villanger. Solving Capacitated Dominating Set by using Covering by Subsets and Maximum Matching Abstract: The Capacitated
Dominating Set problem is the problem of finding a dominating set of
minimum cardinality where each vertex has been assigned a bound on the
number of vertices it has capacity to dominate. Cygan et al. showed in
2009 that this problem can be solved in $O(n^3 m {n \choose n/3})$ or in
$O^*(1.89^n)$ time using maximum matching algorithm. An alternative way
to solve this problem is to use dynamic programming over subsets. By
exploiting structural properties of instances that can not be solved
fast by the maximum matching approach, and "hiding" additional cost
related to considering subsets of large cardinality in the dynamic
programming, an improved algorithm is obtained. We show that the {\sc
Capacitated Dominating Set} problem can be solved in $O^*(1.8463^n)$
time. Frederic Dorn, Hannes Moser, Rolf Niedermeier and Mathias Weller. Efficient Algorithms for Eulerian Extension Abstract:
Eulerian extension problems aim at making a given (directed)
(multi-)graph Eulerian by adding a minimum-cost set of edges (arcs).
These problems have natural applications in scheduling and routing and
are closely related to the CHINESE POSTMAN and RURAL POSTMAN problems.
Our main result is to show that the NP-hard WEIGHTED MULTIGRAPH EULERIAN
EXTENSION is fixed-parameter tractable with respect to the number k of
extension edges (arcs). The corresponding running time amounts to 4^k *
n^O(1). This implies a fixed-parameter tractability result for the
"equivalent" RURAL POSTMAN problem. In addition, we develop several
polynomial-time algorithms for natural Eulerian extension problems. Ge Xia and Yong Zhang. On the Small Cycle Transversal of Planar Graphs Abstract: We consider the problem of finding a $k$-edge
transversal set that covers all (simple) cycles of length at most $s$
in a planar graph, where $s \geq 3$ is a constant. This problem,
referred to as {\sc Small Cycle Transversal}, is known to be
NP-complete. We present a polynomial-time algorithm that computes a
linear kernel of size $36 s^3k$ for {\sc Small Cycle Transversal}. In
order to achieve this kernel, we extend the region decomposition
technique of Alber et al. [J. ACM, 2004] by considering a {\em unique}
region decomposition that is defined by shortest paths. Unlike the
previous results on linear kernels of problems on planar graphs, our
results are not subsumed by the recent meta-theorems on kernelization
of~Bodlaender et al. [FOCS, 2009]. Panos Giannopoulos, Christian Knauer, Mike Fellows, Christophe Paul, Frances Rosamond, Sue Whitesides and Nathan Yu. Milling a Graph with Turn Costs: a Parameterized Complexity Perspective Abstract: The
Abstract Milling problem is a natural and quite general graph-theoretic
model for geometric milling problems: Given a graph, one asks for a walk
that covers all its vertices with a minimum number of turns, as
specified in the graph model by a 0/1 turncost function f_{x} at each
vertex x giving, for each ordered pair of edges (e,f) incident at x, the
turn cost at x of a walk that enters the vertex on edge e and departs
on edge f. We describe an initial study of the parameterized complexity
of the problem. Karin Arikushi, Radoslav Fulek, Balazs Keszegh, Filip Moric and Csaba Toth. Drawing Graphs with Orthogonal Crossings Abstract: We consider {\em right angle
crossing (RAC) drawings} of graphs in which the edges are represented by
polygonal arcs and any two edges can cross only at a right angle. We
show that if a graph with $n$ vertices admits an RAC drawing with at
most 1 bend or 2 bends per edge, then the number of edges is at most
$6.5n$ and $74.2n$, respectively. This is a strengthening of a recent
result of Didimo {\em et al.} Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk and Jakub Wojtaszczyk. Kernelization hardness of connectivity problems in d-degenerate graphs Abstract: A
graph is d-degenerate if its every subgraph contains a vertex of degree
at most d. For instance, planar graphs are 5-degenerate. Inspired by
recent work by Philip, Raman and Sikdar, who have shown the existence of
a polynomial kernel for DOMINATING SET in d-degenerate graphs, we
investigate kernelization hardness of problems that include connectivity
requirement in this class of graphs. Our main contribution is the proof
that CONNECTED DOMINATING SET does not admit a polynomial kernel in
d-degenerate graphs for d >= 2 unless the polynomial hierarchy
collapses up to the third level. We prove this by introducing a new
problem — CONNECTED COLOURS — that nicely encapsulates the hardness of
the connectivity requirement. We extend our analysis by showing that,
unless PH = sigma_p^3, there do not exist polynomial kernels for STEINER
TREE, CONNECTED FEEDBACK VERTEX SET and CONNECTED ODD CYCLE TRANSVERSAL
in d-degenerate graphs for d >= 2. On the other hand, we show a
polynomial kernel for CONNECTED VERTEX COVER in graphs that do not
contain the biclique K(i,j) as a subgraph. Isolde Adler, Binh-Minh Bui-Xuan, Yuri Rabinovich, Gabriel Renault, Jan Arne Telle and Martin Vatshelle. On the boolean-width of a graph: structure and applications Abstract: Boolean-width is a recently
introduced graph invariant. Similar to tree-width, it measures the
structural complexity of graphs. Given any graph $G$ and a decomposition
of $G$ of boolean-width $k$, we give algorithms solving a large class
of vertex subset and vertex partitioning problems in time
$O^*(2^{O(k^2)})$. We relate the boolean-width of a graph to its
branch-width and to the boolean-width of its incidence graph. For this
we use a constructive proof method that also allows much simpler proofs
of similar results on rank-width by Oum (JGT 2008). For a random graph
on $n$ vertices we show that almost surely its boolean-width is
$\Theta(\log^2 n)$ -- setting boolean-width apart from other graph
invariants -- and it is easy to find a decomposition witnessing this.
Combining our results gives algorithms that on input a random graph on
$n$ vertices will solve a large class of vertex subset and vertex
partitioning problems in quasi-polynomial time $O^*(2^{O(\log ^4 n)})$. Pinar Heggernes, Daniel Lokshtanov, Jesper Nederlof, Christophe Paul and Jan Arne Telle. Generalized graph clustering: recognizing (p,q)-cluster graphs Abstract: Cluster Editing is a classical graph
theoretic approach to tackle the problem of data set clustering: it
consists of modifying a similarity graph into a disjoint union of
cliques, i.e, clusters. As pointed out in a number of recent papers, the
cluster editing model is too rigid to capture common features of real
data sets. Several generalizations have thereby been proposed. In this
paper, we introduce (p,q)-cluster graphs, where each cluster misses at
most p edges to be a clique, and there are at most q edges between a
cluster and other clusters. Our generalization is the first one that
allows a large number of false positives and negatives in total, while
bounding the number of these locally for each cluster by p and q. We
show that recognizing (p,q)-cluster graphs is NP-complete when p and q
are input. On the positive side, we show that (0,q)-cluster,
(p,1)-cluster, (p,2)-cluster, and (1,3)-cluster graphs can be recognized
in polynomial time. Konrad Dabrowski, Vadim Lozin, Rajiv Raman and Bernard Ries. Colouring vertices of triangle-free graphs Abstract:
The vertex colouring problem is known to be NP-complete in the class of
triangle-free graphs. Moreover, it remains NP-complete even if we
additionally exclude a graph $F$ which is not a forest. We study the
computational complexity of the problem in $(K_3, F)$-free graphs with
$F$ being a forest. From known results it follows that for any forest
$F$ on 5 vertices the vertex colouring problem is polynomial-time
solvable in the class of $(K_3, F)$-free graphs. In the present paper,
we show that the problem is also polynomial-time solvable in many
classes of $(K_3, F)$-free graphs with $F$ being a forest on 6 vertices.
Geevarghese Philip, Venkatesh Raman and Yngve Villanger. A Quartic Kernel for Pathwidth-One Vertex Deletion Abstract:
The pathwidth of a graph is a measure of how path-like the graph is.
Given a graph G and an integer k, the problem of finding whether there
exist at most k vertices in G whose deletion results in a graph of
pathwidth at most one is NP- complete. We initiate the study of the
parameterized complexity of this problem, parameterized by k. We show
that the problem has a quartic vertex-kernel: We show that, given an
input instance (G = (V, E), k) where |V| = n, we can construct, in
polynomial time, an instance (G', k') such that (i) (G, k) is a YES
instance if and only if (G', k') is a YES instance, (ii) G has O(k^4)
vertices, and (iii) k' ≤ k. We also give a fixed parameter tractable
(FPT) algorithm for the problem that runs in O*(7^k · n^3) time. These
figures compare favorably with the best results known for the closely
related, and extensively studied, Feedback Vertex Set problem. Jeremie Chalopin, Paola Flocchini, Bernard Mans and Nicola Santoro. Network Exploration by Silent and Oblivious Robots Abstract: In
this paper we investigate the basic problem of {\em Exploration} of a
graph by a group of identical mobile computational entities, called
robots, operating autonomously and asynchronously. In particular we are
concerned with what graphs can be explored, and how, if the robots do
not remember the past and have no explicit means of communication. This
model of robots is used when the spatial universe in which the robots
operate is {\em continuous} (e.g., a curve, a polygonal region, a plane,
etc.). The case when the spatial universe is {\em discrete} (i.e., a
graph) has been also studied but only for the classes of acyclic graphs
and of simple cycles. In this paper we consider networks of arbitrary
topology modeled as connected graphs with local orientation (locally
distinct edge labels). We concentrate on class ${\cal H}_k$ of
asymmetric configurations with $k$ robots. Our results indicate that the
explorability of graphs in this class depends on the number $k$ of
robots participating in the exploration. In particular, exploration is
impossible for $k<3$ robots. When there are only $k=3$ robots, only a
subset of ${\cal H}_3$ can be explored; we provide a complete
characterization of the networks that can be explored, and present an
exploration algorithm. When there are $k=4$ robots, we prove that all
networks in ${\cal H}_4$ can be explored; the proof is constructive, and
the algorithm is (unfortunately) quite involved. Finally, we prove that
for any odd $k>4$ all networks in ${\cal H}_k$ can be explored by
presenting a general algorithm. The determination of which networks can
be explored when $k>4$ is even, is still open but can be reduced to
the existence of a rendezvous algorithm for ${\cal H}_k$. Annabell Berger and Matthias Müller-Hannemann. Uniform Sampling of Undirected and Directed Graphs with a Fixed Degree Sequence Abstract:
Many applications in network analysis require algorithms to sample
uniformly at random from the set of all graphs with a prescribed degree
sequence. We present a Markov chain based approach which converges to
the uniform distribution of all realizations for both the directed and
undirected case. It remains an open challenge whether these Markov
chains are rapidly mixing. For the case of directed graphs, we also
explain in this paper that a popular switching algorithm fails in
general to sample uniformly at random because the state graph of the
Markov chain decomposes into different isomorphic components. We call
degree sequences for which the state graph is strongly connected arc
swap sequences. To handle arbitrary degree sequences, we develop two
different solutions. The first uses an additional operation (a
reorientation of induced directed 3-cycles) which makes the state graph
strongly connected, the second selects randomly one of the isomorphic
components and samples inside it. Our main contribution is a precise
characterization of arc swap sequences, leading to an efficient
recognition algorithm. Finally, we point out some interesting
consequences for network analysis. René van Bevern, Christian Komusiewicz, Hannes Moser and Rolf Niedermeier. Measuring Indifference: Unit Interval Vertex Deletion Abstract:
Making a graph unit interval by a minimum number of vertex deletions is
NP-complete. The problem is motivated by applications in seriation and
measuring indifference between data items. We present a fixed-parameter
algorithm based on the iterative compression technique that finds in
O((14k+14)^{k+1} k n^6) time a set of k vertices whose deletion from an
n-vertex graph makes it unit interval. Dániel Marx and Ildikó Schlotter. Parameterized Complexity of the Arc-Preserving Subsequence Problem Abstract: We study the
Arc-Preserving Subsequence (APS) problem with unlimited annotations.
Given two arc-annotated sequences P and T, this problem asks if it is
possible to delete characters from T to obtain P. Since even the unary
version of APS is NP-hard, we used the framework of parameterized
complexity, focusing on a parameterization of this problem where the
parameter is the number of deletions we can make. We present a
linear-time FPT algorithm for a generalization of APS, applying
techniques originally designed to give an FPT algorithm for Induced
Subgraph Isomorphism on interval graphs. Steven Chaplick, Marisa Gutierrez, Benjamin Lévêque and Silvia Tondato. From path graphs to directed path graphs Abstract: We present a
linear time algorithm to greedily orient the edges of a path graph
model to obtain a directed path graph model (when possible). Moreover
we extend this algorithm to find an odd sun when the method fails. This
algorithm has several interesting consequences concerning the
relationship between path graphs and directed path graphs. One is that
for a directed path graph, path graph models and directed path graph
models are the same. Another consequence concerns the difference
between path graphs and directed path graphs in terms of forbidden
induced subgraphs. This can be used to deduce the forbidden induced
subgraph characterization of directed path graphs from the forbidden
induced subgraph characterization of path graphs. The last consequence
is algorithmic and shows that the recognition of directed path graphs
is not more difficult than the recognition of path graphs. Nicolas Bonichon, Cyril Gavoille, nicolas hanusse and David ILCINKAS. Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces Abstract: $\Theta_k$-graphs are geometric
graphs that appear in the context of graph navigation. The
shortest-path metric of these graphs is known to approximate the
Euclidean complete graph up to a factor depending on the cone number
$k$ and the dimension of the space. TD-Delaunay graphs, a.k.a.
triangular-distance Delaunay triangulations introduced by Chew, have
been shown to be plane $2$-spanners of the 2D Euclidean complete graph,
i.e., the distance in the TD-Delaunay graph between any two points is
no more than twice the distance in the plane. Orthogonal surfaces are
geometric objects defined from independent sets of points of the
Euclidean space. Orthogonal surfaces are well studied in combinatorics
(orders, integer programming) and in algebra. From orthogonal surfaces,
geometric graphs, called geodesic embeddings can be built. In this
paper, we introduce a specific subgraph of the $\TG$-graph defined in
the 2D Euclidean space, namely the $\DTG$-graph, composed of the
even-cone edges of the $\TG$-graph. Our main contribution is to show
that these graphs are exactly the TD-Delaunay graphs, and are strongly
connected to the geodesic embeddings of orthogonal surfaces of coplanar
points in the 3D Euclidean space. Using these new bridges between
these three fields, we establish: - Every $\TG$-graph is the union of
two spanning TD-Delaunay graphs. In particular, $\TG$-graphs are
$2$-spanners of the Euclidean graph, and the bound of~$2$ on the
stretch factor is best possible. It was not known that
$\Theta_6$-graphs are $t$-spanners for some constant $t$, and
$\Theta_7$-graphs were only known to be $t$-spanners for $t \approx
7.562$. - Every plane triangulation is TD-Delaunay realizable, i.e.,
every combinatorial plane graph for which all its interior faces are
triangles is the TD-Delaunay graph of some point set in the plane.
Such realizability property does not hold for classical Delaunay
triangulations. Robert Elsaesser and Adrian Ogierman. Efficient Broadcasting in Random Power Law Networks Abstract: In
this paper, we consider the broadcasting problem in random power law
graphs. For the underlying communication we use a simple modification of
the so-called random phone call model introduced by Karp,
Schindelhauer, Shenker, and V\"ocking (FOCS 2000). In the phone call
model, every time step each node calls on a randomly chosen neighbor,
and establishes a communication channel to this node. The communication
channels can then be used to transmit messages in both directions. We
show that if we allow every node to choose \textit{$\rho$ different
neighbors} instead of one, where $\rho$ is some constant, then the
average number of message transmissions per node decreases to an
(almost) optimal value in certain random power law graphs. Formally, we
present an algorithm that completes broadcasting in time $O(\log n)$ and
uses $O(n \log\log n)$ transmissions per message, with probability
$1-n^{-\Omega(1)}$, where $n$ is the size of the underlying network. Padmini Mukkamala, Janos Pach and Deniz Sarioz. Graphs with large obstacle numbers Abstract: Motivated by questions in computer
vision and sensor networks, Alpert et al. introduced the following
definitions. Given a graph G, an obstacle representation of G is a set
of points in the plane representing the vertices of G, together with a
set of connected obstacles such that two vertices of G are joined by an
edge if an only if the corresponding points can be connected by a
segment which avoids all obstacles. The obstacle number of G is the
minimum number of obstacles in an obstacle representation of G. It was
known that there exist graphs of n vertices with obstacle number at
least sqrt(logn). We use extremal graph theoretic tools to show that (1)
there exist graphs of n vertices with obstacle number at least n/(log
n)^2, and (2) the total number of graphs on n vertices with bounded
obstacle number is at most 2^{o(n^2)}. Better results are proved if we
are allowed to use only convex obstacles or polygonal obstacles with a
small number of sides. Edyta Szymanska. The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Codegree Abstract:
In this note we consider the problem of deciding whether a given
$r$-uniform hypergraph $H$ with minimum vertex degree at least
$c|V(H)|$, has a vertex $2-$coloring and a strong vertex $k$-coloring.
Motivated by an old result of Edwards for graphs, we summarize what can
be deduced from his method about the complexity of these problems for
hypergraphs. We obtain the first optimal dichotomy results for
2-colorings of 3- and 4-uniform hypergraphs. In addition, we determine
the computational complexity of strong $k$-colorings of 3-uniform
hypergraphs for some $c,$ leaving a gap which vanishes as $k\rightarrow
\infty$. Colin McDiarmid and Tobias Mueller. The number of bits needed to represent a unit disk graph Abstract: We
prove that for sufficiently large $n$, there exist unit disk graphs on
$n$ vertices such that for every representation with disks in the plane
at least $\gamma^{\sqrt{n}}$ bits are needed to write down the
coordinates of the centers of the disks, for some $\gamma > 1$. Jannik Matuschke and Britta Peis. Lattices and maximum flow algorithms in planar graphs Abstract: We show that the left/right
relation on the set of s-t-paths of a plane graph induces a so-called
"submodular" lattice. If the embedding of the graph is s-t-planar, this
lattice is even consecutive. This implies that Ford and Fulkerson's
uppermost path algorithm for maximum flow in such graphs is indeed a
special case of a two-phase greedy algorithm on lattice polyhedra. We
also show that the properties submodularity and consecutivity cannot be
achieved simultaneously by any partial order on the paths if the graph
is planar but not s-t-planar, thus providing a characterization of this
class of graphs. |