Search

Front Matter, Table of Contents, Preface, Conference Organization

Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. Although edge-colorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question. We show that the problem remains NP-complete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. We also give hardness of approximation results for both bipartite and split graphs. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertex-connected optimally in polynomial time.

This report documents the program and the outcomes of Dagstuhl Seminar 14071 "Graph Modification Problems". The seminar was held from February 9 to February 14, 2014. This report contains abstracts for presentations about the recent developments on algorithms and structural results for graph modification problems, as well as related areas. Furthermore, the report contains a summary of open problems in this area of research.

This report documents the program and the outcomes of Dagstuhl Seminar 11182 ``Exploiting graph structure to cope with hard problems'' which has been held in Schloss Dagstuhl -- Leibniz Center for Informatics from May 1st, 2011 to May 6th, 2011. During the seminar experts with a common focus on graph algorithms presented various new results in how to attack NP-hard graph problems by using the structure of the input graph. Moreover, in the afternoon of each seminar's day new problems have been posed and discussed.

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena,\ud including information or behaviour spread over social networks, biological diseases spreading over\ud contact or trade networks, and the potential flow of goods over logistical infrastructure. Often,\ud the networks over which these processes spread are dynamic in nature, and can be modeled with\ud graphs whose structure is subject to discrete changes over time, i.e. with temporal graphs. Here, we\ud consider temporal graphs in which edges are available at specified timesteps, and study the problem\ud of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally)\ud reachable from a given starting point. This could be used to control the spread of a disease, rumour,\ud etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process\ud starting at any single vertex can be transferred to only a limited number of other vertices using\ud a temporally-feasible path (i.e. a path, along which the times of the edge availabilities increase).\ud We introduce a natural deletion problem for temporal graphs and we provide positive and negative\ud results on its computational complexity, both in the traditional and the parameterised sense (subject\ud to various natural parameters), as well as addressing the approximability of this problem.

The Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for an integer k, such that no two adjacent vertices are coloured alike. A graph G is H-free if G does not contain H as an induced subgraph. It is known that Colouring is NP-complete for H-free graphs if H contains a cycle or claw, even for fixed k >= 3. We examine to what extent the situation may change if in addition the input graph has bounded diameter.

Given a regular expression $R$ and a string $Q$, the regular expression parsing problem is to determine if $Q$ matches $R$ and if so, determine how it matches, e.g., by a mapping of the characters of $Q$ to the characters in $R$. Regular expression parsing makes finding matches of a regular expression even more useful by allowing us to directly extract subpatterns of the match, e.g., for extracting IP-addresses from internet traffic analysis or extracting subparts of genomes from genetic data bases. We present a new general techniques for efficiently converting a large class of algorithms that determine if a string $Q$ matches regular expression $R$ into algorithms that can construct a corresponding mapping. As a consequence, we obtain the first efficient linear space solutions for regular expression parsing.

We study descriptive complexity of counting complexity classes in the range from #P to #*NP. A corollary of Fagin's characterization of NP by existential second-order logic is that #P can be logically described as the class of functions counting satisfying assignments to free relation variables in first-order formulae. In this paper we extend this study to classes beyond #P and extensions of first-order logic with team semantics. These team-based logics are closely related to existential second-order logic and its fragments, hence our results also shed light on the complexity of counting for extensions of first-order logic in Tarski's semantics. Our results show that the class #*NP can be logically characterized by independence logic and existential second-order logic, whereas dependence logic and inclusion logic give rise to subclasses of #*NP and #P, respectively. We also study the function class generated by inclusion logic and relate it to the complexity class TotP, which is a subclass of #P. Our main technical result shows that the problem of counting satisfying assignments for monotone Boolean Sigma_1-formulae is #*NP-complete with respect to Turing reductions as well as complete for the function class generated by dependence logic with respect to first-order reductions.

We give deterministic distributed $(1+\epsilon)$-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in $O(\frac{1}{\epsilon} \log n)$ rounds, and our independent set algorithm has a runtime of $O(\frac{1}{\epsilon}\log(\frac{1}{\epsilon})\log^* n)$ rounds. For coloring, existing lower bounds imply that the dependencies on $\frac{1}{\epsilon}$ and $\log n$ are best possible. For independent set, we prove that $O(\frac{1}{\epsilon})$ rounds are necessary. Both our algorithms make use of a tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into $O(\log n)$ layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first $O( \log \frac{1}{\epsilon})$ layers are required as they already contain a large enough independent set. We develop a $(1+\epsilon)$-approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. This work raises the question as to how useful tree decompositions are for distributed computing.