Search

Social networks are often analyzed through a graph model of the network. 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 two measures for diversity and clustering in social networks by using a d-dot product graph model for the network. Diversity is measured through the size of the largest independent set of the graph, and clustering is measured through the size of the largest clique. We obtain a tight result for the diversity problem, namely that it is polynomial-time solvable for d = 2, but NP-complete 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 consider the situation when two individuals are connected if their preferences are not opposite. This leads to a variant of the standard dot product graph model by taking the threshold t to be zero. We prove in this case that the diversity problem is polynomial-time solvable for any fixed d.

Paths P1,…,Pk in a graph G=(V,E) are said to be mutually induced if for any 1≤i

Being a firefighter is a tough job, especially when tight city budgets do not allow enough firefighters to be on duty when a fire starts. This is formalized in the Firefighter problem, which aims to save as many vertices of a graph as possible from a fire that starts in a vertex and spreads through the graph. In every time step, a single additional firefighter may be placed on a vertex, and the fire advances to each vertex in its neighborhood that is not protected by a firefighter. 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 W[1]-hard when parameterized by the number of saved vertices, and it is NP-hard to approximate within n1−e for any e>0. We aim to simplify the task of a firefighter by providing algorithms that show him/her how to efficiently fight fires in certain types of networks. We show that Firefighter can be solved in polynomial time on various well-known graph classes, including interval graphs, split graphs, permutation graphs, and Pk-free graphs for fixed k. On the negative side, we show that the problem remains NP-hard on unit disk graphs.

The metric dimension of a graph G is the size of a smallest subset L⊆V(G) such that for any x,y∈V(G) there is a z∈L such that the graph distance between x and z differs from the graph distance between y and z. Even though this notion has been part of the literature for almost 40 years, the computational complexity of determining the metric dimension of a graph is still very unclear. Essentially, we only know the problem to be NP-hard for general graphs, to be polynomial-time solvable on trees, and to have a logn-approximation algorithm for general graphs. In this paper, we show tight complexity boundaries for the Metric Dimension problem. We achieve this by giving two complementary results. First, we show that the Metric Dimension problem on bounded-degree planar graphs is NP-complete. Then, we give a polynomial-time algorithm for determining the metric dimension of outerplanar graphs.

Paths P1,…,Pk in a graph G=(V,E) are said to be mutually induced if for any 1≤i

Geometric intersection graphs are graphs determined by intersections of geometric objects. We study the complexity of visualizing the arrangements of objects that induce such graphs. We give a general framework for describing geometric intersection graphs, using arbitrary finite base sets of rationally given convex polygons and affine transformations. We prove that for every class of intersection graphs that fits the framework, the graphs in the class have a representation using polynomially many bits. Consequently, the recognition problem of these classes is in NP (and thus NP-complete). We also give an algorithm to find a drawing of the objects in the plane, if a graph class fits the framework.

We study the planar version of Minimum-Weight Set Cover, where one has to cover a given set of points with a minimum-weight subset of a given set of planar objects. For the unit-weight case, one PTAS (on disks) is known. For arbitrary weights however, the problem appears much harder, and in particular no PTASs are known. We present the first PTAS for Weighted Geometric Set Cover on planar objects, namely on axis-parallel unit squares. By extending the algorithm, we also obtain a PTAS for Minimum-Weight Dominating Set on intersection graphs of unit squares and Geometric Budgeted Maximum Coverage on unit squares. The running time of the developed algorithms is optimal under the exponential time hypothesis. We also show inapproximability results for Geometric Set Cover on various object shapes that are more general than unit squares.

We combine two techniques recently introduced to obtain faster dynamic programming algorithms for optimization problems on graph decompositions. The unification of generalized fast subset convolution and fast matrix multiplication yields significant improvements to the running time of previous algorithms for several optimization problems. As an example, we give an O*(3ω/2k) time algorithm for Minimum Dominating Set on graphs of branchwidth k, improving on the previous O*(4k) algorithm. Here ω is the exponent in the running time of the best matrix multiplication algorithm (currently ω < 2.376). For graphs of cliquewidth k, we improve from O*(8k) to O*(4k). We also obtain an algorithm for counting the number of perfect matchings of a graph, given a branch decomposition of width k, that runs in time O*(2ω/2k). Generalizing these approaches, we obtain faster algorithms for all so-called [ρ, σ]-domination problems on branch decompositions if ρ and ρ are finite or cofinite. The algorithms presented in this paper either attain or are very close to natural lower bounds for these problems.