Search

The Induced Disjoint Paths problem is to test whether an graph G on n vertices with k distinct pairs of vertices ( s i , t i ) contains paths P 1 , ź , P k such that P i connects s i and t i for i = 1 , ź , k , and P i and P j have neither common vertices nor adjacent vertices (except perhaps their ends) for 1 ź i < j ź k . We present a linear-time algorithm that solves Induced Disjoint Paths and finds the corresponding paths (if they exist) on circular-arc graphs. For interval graphs, we exhibit a linear-time algorithm for the generalization of Induced Disjoint Paths where the pairs ( s i , t i ) are not necessarily distinct. In both cases, if a representation of the graph is given, then the algorithms run in O ( n + k ) time.

The Firefighter problem aims to save as many vertices of a graph as possible from a fire that starts in a vertex and spreads through the graph. At every time step a new firefighter may be placed on some vertex, and then the fire advances to every vertex that is not protected by a firefighter and has a neighbor on fire. The problem is notoriously hard: it is NP-hard even when the input graph is a bipartite graph or a tree of maximum degree 3, it is NP-hard to approximate within n 1 - ? for any ? 0 , and it is W 1 -hard when parameterized by the number of saved vertices. We show that Firefighter can be solved in polynomial time on interval graphs, split graphs, permutation graphs, and P k -free graphs for fixed k. To complement these results, we show that the problem remains NP-hard on unit disk graphs.

In this paper, we investigate a graph-theoretical model of social networks. The dot product model assumes that two individuals are connected in the social network if their attributes or opinions are similar. In the model, a d -dimensional vector a v represents the extent to which individual v has each of a set of d attributes or opinions. Then two individuals u and v are assumed to be friends, that is, they are connected in the graph model, if and only if a u · a v ≥ t , for some fixed, positive threshold t . The resulting graph is called a d-dot product graph . We consider diversity and clustering in social networks by using a d -dot product graph model for the network. Diversity is considered through the size of the largest independent set of the graph, and clustering through the size of the largest clique. We present both positive and negative results on the potential of this model. We obtain a tight result for the diversity problem, namely that it is polynomial-time solvable for d = 2, but NP -hard for d ≥ 3. We show that the clustering problem is polynomial-time solvable for d = 2. To our knowledge, these results are also the first on the computational complexity of combinatorial optimization problems on dot product graphs. We also give new insights into the structure of dot product graphs. We also consider the situation when two individuals u and v are connected if and only if their preferences are not antithetical, that is, if and only if a u · a v ≥ 0 , and the situation when two individuals u and v are connected if and only if their preferences are neither antithetical nor “orthogonal”, that is, if and only if a u · a v > 0 . For these two cases we prove that the diversity problem is polynomial-time solvable for any fixed d and that the clustering problem is polynomial-time solvable for d ≤ 3.

A k-spanner of a graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most k times the distance in G. We prove that for fixed k,w, the problem of deciding if a given graph has a k-spanner of treewidth w is fixed-parameter tractable on graphs of bounded degree. In particular, this implies that finding a k-spanner that is a tree (a tree k-spanner) is fixed-parameter tractable on graphs of bounded degree. In contrast, we observe that if the graph has only one vertex of unbounded degree, then Treek-Spanner is NP-complete for k?4. Research highlights? We study how to find a k-spanner of treewidth w in bounded degree graphs. ? We show that this problem is fixed-parameter tractable for fixed k,w. ? Hence Treek-Spanner is fpt on bounded degree graphs for fixed k. ? On graphs with a vertex of unbounded degree, the problem is NP-hard for k?4.