Parameterized Complexity of Diameter
Matthias Bentert André Nichterlein


CSRNet: Dilated Convolutional Neural Networks for Understanding the Highly Congested Scenes

    Yuhong Li^1,2, Xiaofan Zhang^1, Deming Chen^1 

        ^1University of Illinois at Urbana-Champaign

        ^2Beijing University of Posts and Telecommunications

        {leeyh,xiaofan3,dchen}@illinois.edu 


    December 30, 2023
======================================================================================================================================================================================================================




	—the task of computing the length of a longest shortest path—is a fundamental graph problem.
	Assuming the Strong Exponential Time Hypothesis, there is no O(n^1.99)-time algorithm even in sparse graphs RW13.
	To circumvent this lower bound, 	we investigate which parameters allow for running times of the form f(k) (n+m) where k is the respective parameter and f is a computable function.
	To this end, we systematically explore a hierarchy of structural graph parameters.




§ INTRODUCTION

The diameter is arguably among the most fundamental graph parameters. 
Most known algorithms for determining the diameter first compute the shortest path between each pair of vertices (APSP: ) and then return the maximum <cit.>. 
The currently fastest algorithms for APSP in weighted graphs 
have a running time of O(n^3 / 2^Ω(√(log n))) in dense graphs <cit.> and O(nm + n^2 log n) in sparse graphs <cit.>, respectively.
In this work, we focus on the unweighted case.  
Formally, we study the following problem: 

An undirected, connected, unweighted graph G=(V,E).
Compute the length of a longest shortest path in G.
The (theoretically) fastest algorithm for  runs in O(n^2.373) time and is based on fast matrix multiplication <cit.>. 
This upper bound can (presumably) not be improved by much as <cit.> showed that solving  in O((n+m)^2-ε) time for any ε > 0 breaks the SETH (Strong Exponential Time Hypothesis <cit.>).
Seeking for ways to circumvent this lower bound, we follow the line of “parameterization for polynomial-time solvable problems” <cit.> (also referred to as “FPT in P”).
This approach is recently actively studied and sparked a lot of research <cit.>.
Given some parameter k, we aim for an algorithm with a running time of f(k) (n+m) that solves . 
Starting FPT in P for , <cit.> observed that, unless the SETH fails, the function f has to be an exponential function if k is the treewidth of the graph.
We extend their research by systematically exploring the parameter space looking for parameters where f can be a polynomial. 
If such running times contradict conditional lower bounds, then we seek for matching upper bounds of the form f(k)(n+m) or f(k) n^2 where f is exponential. 

In a second step, we combine parameters that are known to be small in many real-world graphs. 
We concentrate on social networks which often have special characteristics, including the “small-world” property and a power-law degree distribution <cit.>.  
We therefore combine parameters related to the diameter with parameters related to the h-index[The h-index of a graph G is the largest number ℓ such that G contains at least ℓ vertices of degree at least ℓ.]; both parameters can be expected to be orders of magnitude smaller than the number of vertices in large social networks. 



  
Related Work.
Due to its importance,  is extensively studied.
Algorithms employed in practice have usually a worst-case running time of O(nm), but are much faster in experiments.
See e. g. <cit.> for a recent example which also yields good performance bounds using average-case analysis <cit.>.
Concerning worst-case analysis, the theoretically fastest algorithms are based on matrix multiplication and run in O(n^2.373) time <cit.> and any O((n+m)^2-ε)-time algorithm refutes the SETH <cit.>.

The following results on approximating  are known:
It is easy to see that a simple breadth-first search gives a linear-time 2-approximation.
<cit.> improved the approximation factor to 3/2 at the expense of the higher running time of O(n^2 log n + m √(n log n)).
The lower bound of <cit.> also implies that approximating  within a factor of 3/2 - δ in O(n^2 - ε) time refutes the SETH.
Moreover, for any ε,δ > 0 a (3/2-δ)-approximation in O(m^2-ε) time or a (5/3-δ)-approximation in O(m^3/2-ε) time also refute the SETH <cit.>.
On planar graphs, there is an approximation scheme with 
near linear running time <cit.>; the fastest exact algorithm for  on planar graphs runs in O(n^1.667) time <cit.>.

Concerning FPT in P,  can be solved in 2^O(k) n^1+o(1) time where k is the treewidth of the graph <cit.>.
However, the reduction for the lower bound of <cit.> implies that for any ε > 0 a 2^o(k) n^2-ε-time algorithm refutes the SETH, where k is either the vertex cover number, the treewidth, or the combined parameter h-index and domination number.
Moreover, this reduction also implies that the SETH is refuted by any f(k)(n+m)^2-ε-time algorithm for  for any computable function f and ε > 0 when k is the (vertex deletion) distance to chordal graphs.
<cit.> adapted the reduction by  and proved that any f(k)(n+m)^2-ε-time algorithm for  parameterized by the maximum degree k for any computable function f refutes the SETH.



  
Our Contribution.
We make progress towards systematically classifying the complexity of  parameterized by structural graph parameters. 
<Ref> gives an overview of previously known and new results and their implications.

We define the graph parameters for which we provide results in the sections where they are used; we refer to <cit.> for definitions of the remaining parameters in <Ref>. 

In <ref>, we follow the “distance from triviality parameterization” <cit.> aiming to extend known tractability results for special graph classes to graphs with small modulators.
For example,  is linear-time solvable on trees.
We obtain an O(k · n)-time algorithm for the parameter feedback edge number k (edge deletion number to trees). 
However, this is our only k^O(1)(n+m)-time algorithm in this section. 
For the remaining parameters, it is already known that such algorithms refute the SETH.
For the parameter distance k to cographs we therefore provide a 2^O(k)(n+m)-time algorithm.
Finally, for the parameter odd cycle transversal k, we use the recently introduced notion of General-Problem-hardness <cit.> to show that  parameterized by k is “as hard” as the unparameterized  problem.
In <ref>, we investigate parameter combinations.
We prove that a k^O(1)(n+m)^2-ε-time algorithm where k is the combined parameter diameter and maximum degree would refute the SETH.
Complementing this lower bound, we provide an f(k)(n+m)-time algorithm where k is the combined parameter diameter and h-index.

Many of our algorithmic results for  transfer easily to the edge-weighted case by simply exchanging bread-first search with Dijkstra's algorithm and thus getting a logarithmic overhead in the running time.
Whenever this is the case, we state the result for the edge-weighted case which we call .
The focus of our work (and hence the overview in <Ref>) is still on the unweighted case.
Thus, we provide hardness results only for the easier, unweighted variant .




§ PRELIMINARIES

We set := {0,1,2,…,} and ^+ := ∖{0}.
For ℓ∈^+ we set [ℓ] := {1, 2,…, ℓ}.
We use mostly standard graph notation.
For a graph G = (V,E) we set n:=|V| and m:= |E|.
All graphs in this work are undirected.
For a vertex subset V' ⊆ V, we denote with G[V'] the graph induced by V'.
We set G-V' := G[V ∖ V'].
A path P = v_0 … v_a is a graph with vertex set {v_0, …, v_a} and edge set {{v_i,v_i+1}| 0 ≤ i < a }. 
For u,v ∈ V, we denote with _G(u,v) the distance between u and v in G, that is, the number of edges (the sum of edge weights in weighted graphs) in a shortest path between u and v.
If G is clear from the context, then we omit the subscript.
We denote by (G) the diameter of G, that is, the length of the longest shortest path in G.
For  we consider edge weights to be positive integers:

A connected graph G=(V,E) and edge weights E →^+.
Compute (G).



  
Parameterized Complexity and GP-hardness.
A language L⊆Σ^* × is a parameterized problem over some finite alphabet Σ, where (x,k) ∈Σ^* × denotes an instance of L and k is the parameter.
The language L is called fixed-parameter tractable if there is an algorithm that on input (x,k) decides whether (x,k)∈ L in f(k)· |x|^O(1) time, where f is some computable function only depending on k and |x| denotes the size of x.
For a parameterized problem L, the language L̂={x∈Σ^*|∃ k (x,k)∈ L} is called the unparameterized problem associated to L.
We use the notion of General-Problem-hardness which formalizes the types of reduction that allow us to exclude parameterized algorithms as they would lead to faster algorithms for the general, unparameterized, problem.

	
	Let P ⊆Σ^* × be a parameterized problem, let P̂⊆Σ^* be the unparameterized decision problem associated to P, and let g→ be a polynomial.
	We call P ℓ-General-Problem-hard(g) (ℓ-GP-hard(g)) if there exists an algorithm A transforming any input instance I of P̂ into a new instance (I',k') of P such that
	
		
  *  A runs in O(g(|I|)) time,
		
  *  I ∈P̂ (I',k') ∈ P,
		
  *  k' ≤ℓ, and
		
  *  |I'| ∈ O(|I|).
	
	We call P General-Problem-hard(g) (GP-hard(g)) if there exists an integer ℓ such that P is ℓ-GP-hard(g). 
	We omit the running time and call P ℓ-General-Problem-hard (ℓ-GP-hard) if g is a linear function. 

Showing GP-hardness for some parameter k allows to lift algorithms for the parameterized problem to the unparameterized setting as stated next.

	
	Let g→ be a polynomial, let P ⊆Σ^* × be a parameterized problem that is GP-hard(g), and let P̂⊆Σ^* be the unparameterized decision problem associated to P.
	If there is an algorithm solving each instance (I, k) of P in O(f(k) · g(|I|)) time, then there is an algorithm solving each instance I' of P̂ in O(g(|I'|)) time. 


Applying <ref> to  yields the following.
First, having an f(k) n^2.3 time algorithm with respect to a parameter k for which  is GP-hard would yield a faster  algorithm.
Moreover, from the known SETH-based hardness results <cit.>, we get the following.


	If the SETH is true and  is GP-hard(n^2-ε) with respect to some parameter k for some ε > 0, then there is no f(k) · n^2-ε' time algorithm for any ε' > 0 and any function f.




§ BASIC OBSERVATIONS

In this section, we present several simple observations that complete the overview in <ref>.
More precisely, we show algorithms with respect to the parameters distance c to clique, distance i to interval graphs, average degree a,  maximum degree Δ, diameter , and domination number γ (in the order they are listed).



  
Distance to clique.
We start with the parameter distance c to clique and provide an algorithm with running time O(c · (n + m)) time.
Since clique is the vertex cover number in the complement graph, it can be 2-approximated in linear time (without computing the complement graph). 


	
	 parameterized by distance c to clique takes O(c · (n + m)) time.



Let G=(V,E) be the input graph and let c be its distance to clique.
Let G' be the respective induced clique graph. 
Compute in linear time the degree of each vertex and the number n = |V| of vertices.
Iteratively check for each vertex v whether its degree is n-1.
If (v) = n-1, then v can be deleted as it is in every largest clique and thus decrease n by one and the degree of each other vertex by one.
If not, then we can find a vertex w which is not adjacent to v in O((v)) time.
Put v and w in the solution set, delete both vertices and all incident edges and adjust the number of vertices and their degree accordingly.
Observe that v and w cannot be contained in the same clique and therefore v∈ K or w∈ K.
Putting both vertices in the solution set results in a 2-approximation.
This algorithm takes O((v) + (w)) time per deleted pair v,w of vertices.
Since ∑_v∈ V(v) ∈ O(n+m) this procedure takes O(n+m) time.

We use the algorithm described above to compute a set K such that G' = G-K is a clique and |K| ≤ 2k in linear time.
Since G' is a clique, its diameter is one if there are at least two vertices in the clique.
We therefore assume that there is at least one vertex in the deletion set K.
Compute for each vertex v∈ K a breadth-first search rooted in v in linear time and return the largest distance found.
The returned value is the diameter of G as each longest induced path is either of length one or has at least one endpoint in K.
The procedure takes O(|K|· (n+m) + n + m) = O(c· (n+m)) time.


Note that for  a result similar to <ref> would yield a faster algorithm for :
In a clique C with n vertices and edge weights either 1 or n, one can encode any connected unweighted graph G by giving edges in G weight one in C and any non-edge in G a weight of n in C. 
It is easy to see that G has the same diameter as C.
Thus, an algorithm for  with running time O(c · (n + m)) would imply an O(n^2) algorithm for and, hence, drastically improve on the state-of-the-art.



  
Distance to interval graphs.
We next discuss the parameter interval graphs.
We first provide a general observation stating that a size k deletion set to some graph class can be used to design a O(k· n^2)-time algorithm if  can be solved in O(n^2) time on graphs in the respective graph class.
The algorithm is fairly simple:
First compute G', that is, the graph without the deletion set K, and solve  on it in O(n^2) time.
Next, compute a breadth-first search from every vertex in K in O(k · m) time and store all distances found in a table.
The last step can  be seen as running the classical Floyd-Warshall algorithm for each vertex in K: compute for each pair a,c∈ V∖ K 

    _G(a,c) := min{_G'(a,c), min_b∈ K{_G(a,b)+_G(b,c)}},

that is, the minimum distance in the original graph.
Observe that a shortest path either travels through some vertex b∈ K or not.
In the latter case, _G(a,c) = _G'(a,c) and in the former case the distance between a and c in G is _G(a,b)+_G(b,c).
This algorithm takes O(n+m+n^2+k· m+n^2· k) = O(k· n^2) time.


	
	Let Π be a graph class such that  can be solved in O(n^2) time on Π.
	If the (vertex) deletion set K to Π is given, then  can be solved in  time.

Note the above algorithm works also for weighted graphs by replacing the breadth-first search with Dijkstra's algorithm.
The overall running time would be unchanged as running Dijkstra's algorithm k times takes O(knlog n + km) = O(kn^2) time.
Thus, <ref> is true for weighted and unweighted graphs.

It is known that (unweighted)  can be solved in O(n^2) time on interval graphs <cit.>.
Thus we obtain the following.


	
	 parameterized by the distance i to interval graphs is solvable in  time provided that the deletion set 
	is given.


We are not aware of a fast constant factor approximation algorithm to compute the deletion set in the above observation.
Finding (or excluding) such an approximation algorithm remains a task for future work.
As interval graphs contain cliques, it follows again that generalizing <ref> to the weighted case would improve upon the state-of-the-art algorithm for .



  
Average degree.
We next consider the average degree a.
Observe that 2m = n · a and therefore the standard algorithm (run Dijkstra's algorithm n times) takes O(n· (n log n + m)) = O(n^2 (log n + a)) time.


	
	 parameterized by average degree a is solvable in O((a + log n) · n^2) time.




  
Maximum degree and diameter.
We look at two parameter combinations related to both maximum degree and diameter.
Usually, this parameter is not interesting as the graph size can be upper-bounded by this parameter and thus fixed-parameter tractability with respect to this combined parameter is trivial.
The input size is, however, only exponentially bounded in the parameter, so it might be tempting to search for fully polynomial algorithms.
In <ref> we exclude such a fully polynomial algorithm.
Thus, the subsequent algorithm is basically optimal.



	
	 parameterized by diameter d and maximum degree Δ is solvable in O(Δ^2d· (d logΔ + Δ)) time.


Since we may assume that the input graph only consists of one connected component, every vertex is found by any breadth-first search.
Any breadth-first search may only reach depth d, where d is the diameter of the input graph, and as each vertex may only have Δ neighbors there are at most 1+∑_i=1^dΔ· (Δ-1)^i-1≤ 1+∑_i=1^dΔ^i-1· (Δ-1)  = Δ^d vertices (since in each “depth layer i” there are at most Δ· (Δ-1)^i-1 vertices).
Since m ≤ n·Δ the O(n · (n log n + m))-time algorithm (n rounds of Dijkstra's algorithm) runs in O(Δ^2d· (d logΔ + Δ)) time. 




  
Maximum degree and domination number.
Observe that for any graph of n vertices, domination number γ, and maximum degree Δ it holds that n≤γ· (Δ+1) as each vertex is in a dominating set or is a neighbor of at least one vertex in it.
The next observation follows from m ≤ n·Δ.

	
	 parameterized by domination number γ and maximum degree Δ is solvable in O(γ^2 Δ^2 (Δ + log(γΔ))) time. 


The reduction of <cit.> can also be used to show that the SETH is refuted by any f(γ)(n+m)^2-ε-time algorithm for  for any computable function f even if a minimum dominating set is given.
This lower bound result is in stark contrast to a simple algorithm running in O(γ(n+m)) time that returns either the diameter or the diameter minus one.


	Given a dominating set of size γ for an unweighted graph, one can approximate the diameter with an additive factor of one in O(γ(n+m)) time.


	The algorithm is as follows: Run a breadth-first search from each vertex in the dominating set D and return the largest distance found.
	This can be done O(γ(n+m)) time.
	Clearly, the value ℓ returned by the algorithm is at most the diameter d of the input graph, that is, ℓ≤ d.
	It remains to show that d ≤ℓ + 1.
	
	To this end, let u,v be the two furthest vertices, that is, (u,v) = d.
	Observe that if either u or v is in the dominating set D, then the algorithm returned ℓ = d.
	Thus, consider the case that neither u nor v are in D.
	Since D is a dominating set, there is a vertex w ∈ D that is a neighbor of u.
	Since w ∈ D, the returned value is at least ℓ≥(w,v).
	Hence, we have d = (u,v) ≤(w,v) + 1 ≤ℓ + 1.


Note that, although computing a minimum dominating set is NP-hard, a simple greedy algorithm computes a (1 + log n)-approximation.
Thus, if the dominating set is not given, the worst-case running time of the above plus-one-approximation changes to O(γ(n+m)log n), which is still far better than the lower bound for exactly computing the diameter.



§ DELETION DISTANCE TO SPECIAL GRAPH CLASSES



In this section, we investigate parameterizations that measure the distance to special graph classes.
The hope is that when  can be solved efficiently in a special graph class Π, then  can be solved if the input graph is “almost” in Π.
We study the following parameters in this order: odd cycle transversal (which is the same as bipartite graphs), cographs, and feedback edge number.
The first two parameters measure the vertex deletion distance to bipartite graphs and cographs, respectively. 
Feedback edge number measures the edge deletion distance to trees.
Note that the lower bound of  for the parameter vertex cover number (i. e. vertex deletion to edgeless graphs) already implies that there is no 2^o(k)(n+m)^2-ε-time algorithm for k being one of the first two parameters in our list unless the SETH breaks, since each of these parameters is smaller than the vertex cover number (see <ref>).



  
Odd Cycle Transversal.
We show that  parameterized by odd cycle transversal and girth is 4-GP-hard.
Consequently, solving  in f(k) · n^2.3 for any computable function f implies an O(n^2.3)-time algorithm for —which would improve the currently best (unparameterized) algorithm.
The girth of a graph is the length of a shortest cycle in it.

	
	 is 4-GP-hard with respect to the combined parameter odd cycle transversal and girth.



	Let G=(V,E) be an arbitrary undirected graph where V = {v_1,v_2,…,  v_n}.
	We construct a new graph G'=(V',E') as follows:
	V' {u_i, w_i | v_i ∈ V}, and
	E' {{u_i, w_j}, {u_j,w_i}|{v_i, v_j}∈ E}∪{{u_i, w_i}| v_i∈ V}.

	An example of this construction can be seen in <ref>.
	
	We will now prove that all properties of <ref> hold.
	It is easy to verify that the reduction can be implemented in linear time and therefore the resulting instance is of linear size as well.
	Observe that {u_i | v_i ∈ V} and {w_i | v_i ∈ V} are both independent sets and therefore G' is bipartite.
	Notice further that for any edge {v_i,v_j}∈ E there is an induced cycle in G' containing the vertices {u_i,w_i,u_j,w_j}.
	Since G' is bipartite there is no induced cycle of length three in G' and thus the girth of G' is four.

	Lastly, we show that (G') = (G)+1 by proving that if (v_i,v_j) is odd, then (u_i,w_j) = (v_i,v_j) and (u_i,u_j) = (v_i,v_j) + 1, and if (v_i,v_j) is even, then (u_i,u_j) = (v_i,v_j) and (u_i,w_j) = (v_i,v_j) + 1.
	Since (u_i,w_i) = 1 and (u_i,w_j) = (u_j,w_i), this will conclude the proof.

	Let P=v_a_0v_a_1… v_a_d be a shortest path from v_i to v_j where v_a_0=v_i and v_a_d = v_j.
	Let P'=u_a_0w_a_1u_a_2 w_a_3… be a path in G'.
	Clearly, P' is also a shortest path as there are no edges {u_i, w_j}∈ E' where {v_i,v_j}∉ E.

	If d is odd, then u_a_0w_a_1… w_a_d is a path of length d from u_i to w_j and u_a_0w_a_1… w_a_d u_a_d is a path of length d+1 from u_i to u_j.
	If d is even, then u_a_0w_a_1… w_a_d-1u_a_d is a path of length d from u_i to u_j and u_a_0 w_a_1… w_a_d-1u_a_dw_a_d is a path of length d+1 from u_i to w_j. 
	Notice that G' is bipartite and thus (u_i, u_j) must be even and (u_i,w_j) must be odd.





  
Distance to cographs.
A graph is a cograph if and only if it does not contain a P_4 as an induced subgraph, where a P_4 is a path on four vertices.
Providing an algorithm that matches the lower bound of <cit.>, we will show that  parameterized by distance k to cographs can be solved in O(k · (n + m) + 2^O(k)) time.
To this end, we will use the following lemma covering the algorithm in a more general setting than we use.


	
	Let G = (V,E) be an edge-weighted graph and let K ⊆ V a vertex subset such that each connected component in G-K has diameter at most two.
	Then, the diameter of G can be computed in O(k · (n log n + m + 2^4k)) time.



	We first compute all connected components and their diameter in G' := G-K in linear time and store for each vertex the information in which connected component it is.
	Note that we only need to check for each connected component C, whether C induces a clique in G' and all edge-weights are one in C; otherwise C's diameter is by assumption two.
	In a second step, we perform in O(k· (nlog n + m)) time Dijkstra's algorithm in G from each vertex v ∈ K and store the distance between v and every other vertex w in a table.

	Next we introduce some notation.
	The type of a vertex u∈ V∖ K is a vector of length d where the ith entry describes the distance from u to x_i with the addition that any value above three is set to 4.
	We say a type is non-empty, if there is at least one vertex with this type.
	We compute for each vertex u∈ V∖ K its type.
	Additionally we store for each non-empty type the connected component its vertex is in or that there are at least two different connected components containing a vertex of that type.
	This takes O(n · k) time and there are at most 4^k many different types.

	Lastly, we iterate over all of the O(4^2k) pairs of types (including the pairs where both types are the same) and compute the largest distance between vertices of these types.
	Let y,z be the vertices of the respective types with maximum pairwise distance.
	We will first discuss how to find y and z and then show how to correctly compute their distance in O(k) time.
	If both types only appear in the same connected component, then the distance between the two vertices of these types is at most two.
	Hence, we can discard this case (one can check in linear time whether the diameter of G is at least two).
	If two types appear in different connected components, then a longest shortest path between vertices of the respective type contain at least one vertex in K.
	Observe that since each connected component has diameter at most two, each third vertex in any longest shortest path must be in K.
	Thus a shortest y-z–path contains at least one vertex x_i∈ K with (x_i,y) < 3.
	By definition, each vertex with the same type as y has the same distance to x_i and therefore the same distance to z unless there is no shortest path from it to z that passes through x_i, that is, it is in the same connected component as z.
	Thus, we can choose two arbitrary vertices of the respective types in different connected components.
	Observe that when computing the types, one can also precompute the connected components the corresponding vertices are in.
	Thus, checking whether there are two vertices of the respective type in different connected components is just a table lookup.
	We can compute the distance between y and z in O(k) time by computing min_x∈ K(y,x) + (x,z).
	Observe that the shortest path from y to z contains x_i and therefore (y,x_i) + (x_i,z) = (y,z).
	We can compute the diameter of G this way in O(k· (n log n+m + 2^4k)) time. 


Note that the algorithm described in the above proof does not verify if K is indeed a vertex set such that each connected component in G-K has diameter at most two.
Indeed, even in the unweighted case to distinguish diameter two and three in O(n^2-ε), ε > 0, time would refute the SETH <cit.>.
Thus, the above algorithm cannot efficiently verify if the input meets the stated conditions.
Hence, when using <ref>, we need a way to ensure this condition.

Recall that a cograph does not contain a P_4 as an induced subgraph.
Thus, any unweighted cograph has diameter at most two (but not every diameter-two graph is a cograph, consider e. g. a cycle on five vertices).
Moreover, given a graph G one can determine in linear time whether G is a cograph and can return an induced P_4 if this is not the case <cit.>.
This implies that in O(k· (n+m)) time one can compute a set K⊆ V with |K|≤ 4k such that G - K is a cograph: 
Iteratively add all four vertices of a returned P_4 into the solution set and delete those vertices from G until it is P_4-free.
Thus, we can compute a set K that satisfy the conditions of <ref> and the following theorem is immediate.


	
	 can be solved in O(k · (n + m + 2^16k)) time when parameterized by distance k to cographs.



	Let G=(V,E) be the input graph with distance k to cograph.
	Let K be a set of vertices such that G' = G - K is a cograph with |K| ≤ 4k.
	Recall that K can be computed in O(k · (n+m)) time.
	
	Thus, applying <ref> yields a running time of O(k · (n + m + 2^16k)).
	Note that since we are in the unweighted setting, we can replace Dijkstra's algorithm in the proof of <ref> by a simple breadth-first search and thus get rid of the log-factor in the running time.


Note that a clique is also a cograph. 
Thus, following the same argumentation given after <ref>, it follows that a generalization of <ref> to the weighted case would significantly improve the state-of-the-art algorithm for .



  
Feedback edge number.
We will prove that  parameterized by feedback edge number k can be solved in O(k· n log n) time.
One can compute a minimum feedback edge set K (with |K| = k) in linear time by taking all edges not in a spanning tree.
Recently, this parameter was used to speed up algorithms computing maximum matchings <cit.>.
Note that k ≤ m, thus the subsequently provided O(k· n log n)-time algorithm is adaptive, that is, it is not slower than the standard O(n(n log n + m))-time algorithm but can be much faster in case k = o(m).
In the remainder of this section we will prove the following.


	
	 parameterized by feedback edge number k can be solved in O(k· n log n) time.


The algorithm behind the above theorem works roughly in two steps: 
In a first step, we apply data reduction rules.
On the one hand, these rules can shrink the graph considerably. 
On the other hand, these rules also create a special structure: 
After these rules are exhaustively applied, there are “few” vertices of degree at least three; moreover, these high-degree vertices are connected via “few” paths.
In the second step, the algorithm uses this structure in a case distinction to compute the diameter in O(k· n log n) time.

Note that the data reduction rules delete vertices from the graph.
However, since at the time of deletion, we do not know whether these vertices are contained in a shortest path defining the diameter, we need to keep additional information.
In particular, we introduce a second weight function  (for pending) and an integer s.
Intuitively, (v) stores the length of a longest shortest path P with one endpoint being v and the other endpoint in P being already deleted by the data reduction rules.
The role of s is to store the length of a longest shortest path where both endpoints are already deleted.
This leads to the following formal problem definition:



An undirected, connected graph G=(V,E), weight functions E →^+ and V →, and s ∈.
Compute max{^(G), s}, where 
    ^(G) := max_v,w∈ V{_G^(v,w)} := max_v,w∈ V{(v) + _G(v,w) + (w)}.


Notice that if all -weights and s are set to 0, then the problem is the same as .
We therefore start with initializing all -weights and s to 0 and applying our reduction rule that removes degree-one vertices from the graph.
The main idea of the reduction rule is simple: 
If a degree-one vertex u is removed, then the value (v) (v is the unique neighbor of u) is adjusted and we store in an additional variable s the length of a longest shortest path that cannot be recovered from the reduced graph.
This addresses the case that a longest shortest path has both its endpoints in pending trees (trees removed by our reduction rule) that are connected to the same vertex.
Initially, s is set to zero.
The first reduction rule is defined as follows (see <ref> for an example illustrating the subsequent two reduction rules).



	
	Let u be a vertex of degree one and let v be its neighbor.
	Delete u and the incident edge from G, set s = max{s, (u) + (v) + ({u,v})} and (v) = max{(v), (u) + ({u,v})}.



Before we analyze the running time and correctness, we first present a second reduction rule that we apply after <Ref> is not applicable anymore.
Since the resulting graph has no degree-one vertices we can partition the vertex set of the remaining graph into vertices V^=2 of degree exactly two and vertices V^≥ 3 of degree at least three.
Using standard argumentation we can show that |V^≥ 3| ∈ O(min{k,n}) and all vertices in V^=2 are either in pending cycles or in maximal paths <cit.>.
A maximal path is an induced subgraph P = x_0x_1… x_a where {x_i,x_i+1}∈ E for all 0≤ i <a, x_0, x_a ∈ V^≥ 3, x_i∈ V^=2 for all 0<i<a, and x_0 ≠ x_a.  
A pending cycle is basically the same except x_0 = x_a and (x_0) may possibly be two.
The set 𝒞 of all pending cycles and 𝒫 of maximal paths can be computed in O(n+m) time <cit.>.
The second reduction rule works similar to <Ref>, but instead of deleting degree-one vertices, it removes pending cycles.


	
	Let C = x_0x_1… x_a be a pending cycle.
	Let x_k be the vertex that maximizes (x_k) + (x_0,x_k) in C.
	Delete all vertices in C except for x_0 (and all incident edges) from G, set s = max{s, ^(C)} and (x_0) = max{(x_0), (x_k) + (x_0,x_k)}.


We now prove the correctness of these two data reduction rules.
That is, given an instance (G,,,s) of  let (G',',',s') be the instance created by applying a data reduction rule R once.
Then, R is correct if max{s,^(G)} = max{s',^(G')}.


	
	<Ref> are correct.



	Let (G = (V,E),,,s) be the input instance of  and (G' = (V',E'),',',s') the instance resulting of an application of <ref> to the degree-one vertex u with neighbor v or <ref> to a pending cycle C = x_0,x_1,…,x_a.
	We start with making some statements that are true for both reduction rules.

	We first show that ^(G) ≥^(G'), that is, the (-adjusted) diameter in G is at least as large as in G'.
	To this end, let w,w' ∈ V' such that ^(G') = '(w) + _G'(w,w') + '(w').
	Observe that if w ≠ v and w' ≠ v (for <ref>) or w ≠ x_0 and ,w' ≠ x_0 (for <ref>), then
	
    '(w) + _G'(w,w') + '(w') ≤(w) + _G(w,w') + (w') ≤^(G).

	Thus, it remains to consider the case that w' = v for <ref> and w' = x_0 for <ref> (the cases w=v respectively w = x_0 are completely analogous). 
	In the case of <ref> we have
	
    '(w) + _G'(w,w') + '(w') 
    
    		=   (w) + _G(w,v) + max{(v), ({u,v}) + (u)}≤^(G).

	In the case of <ref> we have for the “furthest” vertex x_k from x_0 in C that
		
    '(w) + _G'(w,w') + '(w') 
    
    		=   (w) + _G(w,x_0) + max{(x_0), ({x_0,x_k}) + (x_k)}≤^(G).
	
	Thus, ^(G) ≥^(G').

	Next, observe that s ≤ s'.
	Moreover, observe that if s ≥^(G), then we have max{s,^(G)} = s = s' = max{s',^(G')} since s' ≥ s ≥^(G) ≥^(G').
	Thus, it remains to consider the case s < ^(G) and, hence, to show that ^(G) = max{s',^(G')}.
	
	We split this last part of the proof into two parts, where we first consider <ref> and then consider <ref> in the second part.
	For the first part, let w,w' ∈ V such that ^(G) = (w) + _G(w,w') + (w').
	We make a case distinction on the size of {w,w'}∩{u,v} (that is, whether w or w' are equal to v or u).

	Case 1: |{w,w'}∩{u,v}| = 2.
	Since s < ^(G), we have by definition of s' that
	
    ^(G) = (u) + _G(u,v) + (v) = (u) + ({u,v}) + (v) = s'.

	Since ^(G') ≤^(G), it follows that max{s',^(G')} = s' = ^(G).

	In the following two cases we assume that ^(G) > (u) + _G(u,v) + (v); otherwise we are in Case 1.
	Hence, it follows that also s' < ^(G) since s < ^(G).


	Case 2: |{w,w'}∩{u,v}| = 1.
	Thus, we need to show ^(G') ≥^(G) (as we already proved ^(G') ≤^(G) and assume s' < ^(G)).
	To this end, let w' ∈{u,v} and w ∉{u,v}.
	Hence, we have
	
    ^(G) 	    = (w) + _G(w,w') + (w') 
        = (w) + _G(w,v) + max{(v), (u) + ({u,v})}
        = '(w) + _G'(w,v) + '(v) ≤^(G').

	Thus, ^(G') = ^(G).

	Case 3: |{w,w'}∩{u,v}| = 0.
	Again, we need to show ^(G') ≥^(G).
	To this end, neither w nor w' are changed by <ref>.
	Thus,
	
    (w) + _G(w,w') + (w') = '(w) + _G'(w,w') + '(w') ≤^(G').

	This finishes the last case and concludes the proof for <ref>.
	
	We continue with the proof for <ref>.
	To this end we consider two cases: Either s' > ^(G') or s' ≤^(G').
	
	Case 1: s' ≥^(G').
	We show that s' = ^(G).
	Since s' ≥^(G'), there is no shortest path of length s'+1 in G'.
	Since G and G' only differ in C, it suffices to show that there is a shortest path of length s' in G and that there is no longer path that starts in C.
	By construction, there is a pair of vertices x_i, x_j in C such that ^_G(x_i,x_j) = s'.
	Now assume that there is a shortest path of length at least s'+1 in G that starts in C.
	By construction the path has to end outside of C as otherwise s' would be larger.
	Let v be the other endpoint of the path.
	Then, ^(G') ≥_G'^(x_0,v) > s'—a contradiction.
	
	Case 2: s' < ^(G').
	We will show that ^(G) ≤^(G').
	We first define V_C = {x_0,x_1,…,x_a-1} to be the set of vertices in C.
	Again, let w,w' ∈ V such that ^(G) = (w) + _G(w,w') + (w') and we make a case distinction on the size of {w,w'}∩ V_C.
	
	Subcase 1: |{w,w'}∩ V_C| = 0.
	Since G and G' only differ in C, we have
	
    ^(G) 	    = (w) + _G(w,w') + (w') 
        = '(w) + _G'(w,w') + '(w') ≤^(G').


	Subcase 2: |{w,w'}∩ V_C| = 2.
	In this case by definition of s', we have that s' = _G^≥_G'^—a contradiction.

	Subcase 3: |{w,w'}∩ V_C| = 1.
	We assume without loss of generality that w ∉ V_C and w' ∈ V_C.
	Then we have
	
    ^(G) 	    = (w) + _G(w,w') + (w') 
       ≤(w) + _G(w,x_0) + max{(x_0), (w') + _G({x_0,w'})}
        = '(w) + _G'(w,x_0) + '(x_0) ≤^(G').

	This finishes the last case and concludes the proof.



We now analyze the running time of <Ref>.


	
	Given a pending cycle C = x_0x_1… x_a, <Ref> can be applied in O(a) time.



First, in O(a) time we compute k such that (x_k,x_0) + (x_k) is maximized and if k≠ 0, then we set s = max{s,(x_0) + (x_k,x_0) + (x_k)}.
(For k=0 we do not update s.)
It remains to show how to compute ^(C), the longest shortest path that starts and ends in C.
To this end, we first compute the sum W of all edge-weights in C, that is, W = ∑_i=0^a-1({x_i,x_i+1}).

Next we define two distance measures d_,d_ (for clockwise and counter-clockwise) such that 

    d_(x_i,x_j) =   ({x_i,x_i+1  a}) 
        + ({x_i+1  a,x_i+2 a}) + … +({x_j-1  a,x_j})        and
    
    		d_(x_i,x_j) =   ({x_i,x_i-1  a}) 
        + ({x_i-1  a,x_i-2 a}) + … +({x_j+1  a,x_j}).

Note that d_(x_i,x_j) + d_(x_i,x_j) = W and d_cl(x_i,x_j) = d_ (x_j,x_i).

We provide a dynamic program that only considers “clockwise” shortest paths between x_ℓ and x_j, that is, paths of length (x_ℓ) + d_(x_ℓ,x_j) + (x_j) that satisfy d_(x_ℓ,x_j) ≤ d_(x_ℓ,x_j) (otherwise it is not a shortest path).
Observe that all “counter-clockwise” paths will be considered in the iteration where the role of x_j and x_ℓ is swapped as d_cc(x_ℓ,x_j) = d_ (x_ℓ,x_j).

The dynamic program uses a table T with a entries, where the ℓ^th entry corresponds to x_ℓ and the value stored in the entry is the vertex x_j furthest from x_ℓ, formally, 

    x_j := _x ∈{x_i  |  d_(x_ℓ,x_i)  ≤  d_(x_ℓ,x_i)}{(x,x_ℓ) }.

For initialization, we start with computing T[x_0] by checking in O(a) time all vertices in C.
Besides the table T, the dynamic program has one more variable r storing the length of a longest shortest path found so far.
Initially, r = (x_0) + (x_k,x_0) + (x_k).

Given x_j = T[x_ℓ] for some vertex x_ℓ the dynamic program computes the furthest vertex x_j' from x_ℓ+1 and updates r if any longest shortest path from x_ℓ+1 is longer than r.
Note that the furthest vertex x_j' from x_ℓ+1 is either the furthest vertex T[x_ℓ] = x_j from x_ℓ or some vertex x that is ignored by x_ℓ. 
The only possible vertices that are ignored by x_ℓ but not by x_ℓ+1 are the vertices x with d_(x_ℓ,x) > d_(x_ℓ,x) and d_(x_ℓ+1,x) ≤ d_(x_ℓ+1,x).
Thus, we can compute the furthest vertex from x_ℓ+1 in constant amortized time as follows:
We can compute the furthest vertex x_j' from x_ℓ+1 by iterating over the vertices x_j+1  a, x_j+2  a, … and check whether

    d_(x_ℓ+1,x_j+1 a) 
    
    	=    d_(x_ℓ,x_j) - (x_ℓ,x_ℓ+1) + (x_j  a,x_j+1  a) ≤ W/2.

If this first check is met, then we compute the “pen”-distance d_(x_ℓ+1,x_k+1  a) + (x_ℓ+1) + (x_k+1  a).
If this is larger than r, then we update r with this value (a longer shortest path was found).
We then continue with x_k+2  a and so on until the first check is not met anymore.

The whole pending cycle can be checked in O(a) time in this way and we can set s = max{s,r}.


We now analyze the running time of both reduction rules.


	
	<Ref> can be exhaustively applied in O(n+m) time.



Notice that we can sort all vertices by their degree in linear time using bucket sort.
Applying <Ref> or <ref> takes constant time per deleted vertex.
After applying a reduction rule, we adjust the degree of the remaining vertex (either the unique neighbor of a degree-one vertex or the high-degree vertex in a pending cycle) in constant time by moving it to the appropriate bucket.
Note that applying <ref> can lead to a new vertex of degree one and an application of <ref> can lead to two maximal paths merging to either a longer maximal path or a pending cycle.
Since these cases can be detected in constant time and each vertex is only removed once, the overall running time to apply <ref> exhaustively is in O(n + m).


We now present the algorithm that computes the maximum ^(u,v) over all pairs of remaining vertices u,v after applying <ref> exhaustively.
This algorithm distinguishes between three different cases:
The longest shortest path has at least one endpoint in V^≥ 3 (Case 1), its two endpoints are in the same maximal path (Case 2), or its endpoints are in two different maximal paths (Case 3).
 
 

Let G=(V,E) be the input graph with feedback edge number k and let K be a feedback edge set with |K|=k.

Case 1:
First we perform Dijkstra's algorithm from each vertex v∈ V^≥ 3 and store for each vertex u ∈ V ∖{v} the distance (v,u) and update s = max{s, (v) + (u) + (v,u)}.
This way we find all shortest paths that start or end in a vertex in V^≥ 3 (or a pendant tree connected to such a vertex).

Case 2:
This case is similar to the case of pending cycles (see <ref>).
The only adjustment is the computation of the index that is considered by x_ℓ+1 but not by x_ℓ.
For a maximal path P=x_0x_1… x_a, we compute W= ∑_i=0^a-1(x_i,x_i+1) and check whether the distance “within” a path between two vertices x_i,x_j (i < j) is at most as large as (x_i,x_0) + (x_0,x_a) + (x_a,x_j).

Case 3:
We set V_P := {x_1,x_2,…,x_a-1} and V_P := V ∖ (V_P ∪{x_0,x_a}) = {v_1, v_2, …, v_n-a-1}.
In the last case we have that u is in a maximal path P = x_0x_1 … x_a and v is outside P, that is, u ∈ V_P and v ∈V_P.
We present an algorithm that takes O(n log n) time for each maximal path to compute the length of a longest shortest path of the specified type.
As there are O(k) such maximal paths , the overall running time is O(k · nlog n).

The algorithm uses a length-|V_P| array D where the i^th entry is the distance difference of v_i ∈V_P to x_0 and x_a respectively, formally, D[i] := _G(x_0,v_i) - _G(x_a,v_i).
Note that for some vertex x_j in P, there is a shortest x_j-v_i-path leaving P via x_a if and only if _P(x_j,x_a) - _P(x_j,x_0) ≤ D[i].
Furthermore, D can be computed in O(n) time from the distances computed in Case 1.
The values _P(x_j,x_a) and _P(x_j,x_0) can also be computed easily in O(n) time.

We use D in the following way: 
The algorithm sorts D in O(n log n) time in non-increasing order (for ease of notation, we still assume that the i^th entry of D correspond to v_i).
As a result, we have that if a shortest x_j-v_i-path leaves P via x_a, then so does every shortest x_j-v_i'-path for every i' < i.
Furthermore, since for any j' > j we have _P(x_j',x_a) - _P(x_j',x_0) < _P(x_j,x_a) - _P(x_j,x_0) ≤ D[i], we have that every shortest x_j'-v_i-path goes via x_0.
See <ref> for an illustration of this monotonicity which is exploited in our subsequent algorithm.





The algorithm handles two cases separately: One for computing the longest shortest x_j-v_i-path, x_j∈ V_P and v_i ∈V_P, that contains x_0 and one for computing longest shortest x_j-v_i-path containing x_a.
As these two cases are completely symmetric, we will discuss only the latter case.
For brevity, let _max(x_j) be the length of a longest shortest path starting in x_j, leaving P via x_a, and ending in some v ∈V_P.
Formally, _max(x_j) = max{^(x_j,v_i) | v_i ∈V_P _G(x_j,v_i) = _P(x_j,x_a) + _G(x_a,v_i)}.
Thus, the task is to compute max_j ∈ [a-1]{_max(x_j)}.
To this end, the algorithm computes _max(x_j) for all j.

For the initialization, the algorithm computes the sorted array D.
Moreover, it computes the largest number i_1 ∈ [n-a-1] such that _G(x_1,v_i_1) = _P(x_1,x_a) + _G(x_a,v_i_1).
If no such number exists, then set i_1 := 0.
Furthermore, for each i ∈ [i_1] compute ^(x_1,v_i) = (v_i) + _G(v_i,x_a) + _P(x_a,x_1) + (x_1) and store the maximum in a variable r (r will be returned at the end of the algorithm).
Due to D being sorted, this initialization phase can be done in O(i_1) time.
Moreover, due to D being sorted, we have r = _max(x_1) as for all i' > i_1 every shortest x_1-v_i'-path leaves P via x_0.
This completes the initialization.

Next, the algorithm computes for each j ∈{2,3,…,a-1} the value _max(x_j).
Notice that _max(x_1) was computed in the initialization.
For j>1 the algorithm is as follows:
Compute the largest number i_j ∈ [n-a-1] such that _G(x_j,v_i_j) = _P(x_j,x_a) + _G(x_a,v_i_j).
Note that due to the sorting of D we have that i_j ≥ i_j-1.
Hence, we find i_j in O(i_j - i_j-1) time by simply start checking D at positions i_j-1+1, i_j-1+2, …, i_j, i_j+1 (note that, by definition of i_j, the last check at position i_j+1 fails).
For each i ∈{i_j-1+1,i_j-1+2,…,i_j} we do the following:
We first compute ^(x_j,v_i) = (v_i) + _G(v_i,x_a) + _P(x_a,x_j) + (x_j) and store the maximum in a variable r'.
We then update r with max{ r', r - (x_j-1) + (x_j) - ({x_j-1,x_j}) }.
Observe that r = _max(x_j) as for v_i with i ∈{i_j-1+1,i_j-1+2,…,i_j} the algorithm computed ^(x_j,v_i).
For all i ∈ [i_j-1] we know that all x_j-1-v_i-paths leave P via x_a.
Thus, we can simply update their length by (x_j) - (x_j-1) - ({x_j-1,x_j}).

Altogether, the algorithm runs in O(k (n log n + ∑_i=1^a-1 (i_j - i_j-1))) = O(kn log n) time.
Combining this with <ref> concludes the proof of <ref>.






§ PARAMETERS FOR SOCIAL NETWORKS



Here, we study parameters that we expect to be small in social networks.
Recall that social networks have the “small-world” property and a power-law degree distribution <cit.>.  
The “small-world” property directly transfers to the diameter.
We capture the power-law degree distribution by the h-index as only few high-degree vertices exist in the network.
Thus, we investigate parameters related to the diameter and to the h-index starting with degree-related parameters. 



 §.§ Degree Related Parameters


We next investigate the parameter minimum degree.
Unsurprisingly, the minimum degree is not helpful for parameterized algorithms.
In fact, we show that  is 2-GP-hard with respect to the combined parameter bisection width and minimum degree.
The bisection width of a graph G is the minimum number of edges to delete from G in order to partition G into two connected component whose number of vertices differ by at most one.


	
	 is 2-GP-hard with respect to bisection width and minimum degree.


Let G=(V,E) be an arbitrary input graph for  where V = {v_1,v_2,… v_n} and let d be the diameter of G.
We construct a new graph G'=(V',E') with diameter d+4 as follows:
Let V'= {s_i, t_i, u_i | i ∈ [n]}∪{w_i | i ∈ [3n]} and E'= T ∪ W ∪ E”, where T = {{s_i, t_i}, {t_i,u_i}| i ∈ [n]}, W = {u_1, w_1}∪{{w_1, w_i}| i ∈ ([3n]∖{1})}, and E” = {{u_i, u_j}|{v_i, v_j}∈ E}.

An example of this construction can be seen in <ref>.

We will now prove that all properties of <ref> hold.
It is easy to verify that the reduction runs in linear time and that there are 6n vertices and 5n + m edges in G'.
Notice that {s_i, t_i, u_i | i ∈ [n]} and {w_i | i ∈ [3n]} are both of size 3n and that there is only one edge ({u_1,w_1}) between these two sets of vertices.
The bisection width of G' is therefore one and the minimum degree is also one as s_1 is only adjacent to t_1.

It remains to show that G' has diameter d+4.
First, notice that the subgraph of G' induced by {u_i | i ∈ [n]} is isomorphic to G.
Note that (s_i,u_i) = 2 and thus (s_i, s_j)= (u_i, u_j) + 4 = (v_i,v_j) + 4 and therefore the diameter of G' is at least d+4.
Third, notice that for all vertices x ∈ V' ∖{s_i} it holds that (s_i,x) > (t_i,x).
Lastly, observe that for all i ∈ [3n] and all vertices x ∈ V' it holds that (w_i, x) ≤max{(s_1, x), 4}.
Thus the longest shortest path in G' is between two vertices s_i,s_j and is of distance (u_i,u_j) + 4 = (v_i,v_j) + 4 ≤ d + 4.



We mention in passing that the constructed graph in the proof of <ref> contains the original graph as an induced subgraph and if the original graph is bipartite, then so is the constructed graph.
Thus, first applying the construction in the proof of <ref> (see also <ref>) and then the construction in the proof of <ref> proves that  is GP-hard even parameterized by the sum of girth, bisection width, minimum degree, and bipartite graphs.



 §.§ Parameters related to both diameter and h-index


Here, we will study combinations of two parameters where the first one is related to diameter and the second to h-index (see <Ref> for an overview of closely related parameters).
We start with the combination maximum degree and diameter.
Interestingly, although the parameter is quite large, the naive algorithm behind <ref> cannot be improved to a fully polynomial running time.


	
	There is no (d+ Δ)^O(1)(n+m)^2-ϵ-time algorithm that solves  parameterized by maximum degree Δ and diameter d unless the SETH is false.



We prove a slightly stronger statement excluding 2^o(√(d + Δ))· (n+m)^2-ϵ-time algorithms for some constant c.
Assume towards a contradiction that for each constant r there is a 2^o(√(d + Δ))· (n+m)^2-ϵ-time algorithm that solves  parameterized by maximum degree Δ and diameter d.
<cit.> have shown a reduction from CNF-SAT to  where the resulting graph has maximum degree three such that for any constant ϵ>0 an O((n+m)^2-ϵ)-time algorithm (for ) would refute the SETH.
A closer look reveals that there is some constant c such that the diameter d in their constructed graph is in O(log^c (n+m)).
By assumption we can solve  parameterized by maximum degree and diameter in 2^o(√(d + Δ))· (n+m)^2-ϵ time.
Observe that

    2^o(√(d + Δ))· (n+m)^2-ϵ = 2^o(√(log^c (n+m)))· (n+m)^2-ϵ
    
    =    (n+m)^o(1)· (n+m)^2-ϵ⊆ O((n+m)^2-ϵ') for some  ε'>0.

Since we constructed for some ϵ'>0 an O((n+m)^2-ϵ')-time algorithm for  the SETH fails and thus we reached a contradiction. Finally, notice that (d + Δ)^O(1)⊂ 2^o(√(d + Δ)) for any constant c. 





  
h-index and diameter.
We next investigate the combined parameter h-index and diameter.
The reduction by <cit.> produces instances with constant domination number and logarithmic vertex cover number (in the input size).
Since the diameter d is linearly upper-bounded by the domination number and the h-index is linearly upper-bounded by the vertex cover number, any algorithm that solves  parameterized by the combined parameter (d+h) in 2^o(d+h)· (n+m)^2-ϵ time disproves the SETH.
We will now present an algorithm for  parameterized by h-index and diameter that almost matches the lower bound.


	
	 parameterized by diameter d and h-Index h is solvable in O(h · (n log n + m) + n · d · h ·  (d^h + h^d log h)) time.



Let H = {x_1,…,x_h} be a set of vertices such that all vertices in V ∖ H have degree at most h in G.
Clearly, H can be computed in linear time.
We will describe a two-phase algorithm with the following basic idea:
In the first phase it performs Dijkstra's algorithm from each vertex v ∈ H, stores the distance to each other vertex and uses this to compute the “type” of each vertex, that is, a characterization by the distance to each vertex in H.
In the second phase it iteratively increases a value e and verifies whether there is a vertex pair of distance at least e+1.
If at any point no vertex pair is found, then the diameter of G is e.

The first phase is straight forward:
Execute Dijkstra's algorithm from each vertex v in H and store the distance from v to every other vertex w in a table.
Then iterate over each vertex w ∈ V ∖ H and compute a vector of length h where the ith entry represents the distance from w to x_i.
Also store the number of vertices of each type containing at least one vertex.
Since the distance to any vertex is at most d, there are at most d^h different types.
This first phase takes O(h · (m + n log n)) time.

For the second phase, we initialize e with the largest distance found so far, that is, the maximum value stored in the table and compute G' = G - H.
Iteratively check whether there is a pair of vertices in V ∖ H of distance at least e+1 as follows.
We check for each vertex v ∈ V ∖ H whether there are types such that no vertex of one of these types can be reached by a path of length at most e passing through a vertex in H.
This can be done by computing the sum of the two type-vectors in O(h) time and comparing the minimum entry in this sum with e.
If all entries are larger than e, then no shortest path from v to some vertex w of the respective type of length at most e can contain any vertex in H.
Thus we compute Dijkstra's algorithm from v in G' up to depth e[By “up to depth e” we mean that we run Dijkstra's algorithm with the addition that whenever the distance to a vertex is at least e, then we do not add it to the stack (or priority queue) and if the distance is larger then e, then we do not update its distance to the source. Similar as in the proof of <ref>, we can show that the number of vertices and edges considered by the algorithm are at most h^e+1 and h^e, respectively.] and count the number of vertices of the respective types we found.
If these numbers are equal to the total number of vertices of the respective types, then for all vertices w of these type it holds that (v,w) ≤ e.
If the respective numbers do not match, then there is a vertex pair of distance at least e+1, and we can therefore increase e by one and start the process again.

There are at most d iterations in which e is increased and the check is done.
In each iteration, we have to compute the sum of type vectors for each vertex and perform Dijkstra's algorithm up to depth at most d in G'.
Recall that the maximum degree in G' is h and therefore computing Dijkstra's algorithm up to depth d takes O(h^d · d ·log h) time.
Since ∑_e=1^d h^e < h^d+1 for h ≥ 2, the overall running time is in O(h · (n log n + m) + n · d · h ·  (d^h + h^d log h)).





  
Acyclic chromatic number and domination number.
We next analyze the parameterized complexity of  parameterized by acyclic chromatic number a and domination number d.
The acyclic chromatic number of a graph is the minimum number of colors needed to color each vertex with one of the given colors such that each subgraph induced by all vertices of one color is an independent set and each subgraph induced by all vertices of two colors is acyclic.
The acyclic chromatic number upper-bounds the average degree, and therefore the standard O(n · m)-time algorithm runs in O(n^2 · a) time.
We will show that this is essentially the best one can hope for as we can exclude f(a,d) · (n+m)^2-ε-time algorithms 
assuming SETH.
Our result is based on the reduction by <cit.> and is modified such that the acyclic chromatic number and domination number are both four in the resulting graph.


	
	There is no f(a,d)· (n+m)^2-ϵ-time algorithm for any computable function f that solves  parameterized by acyclic chromatic number a and domination number d unless the SETH is false.



We provide a reduction from CNF-SAT to  where the input instance has constant acyclic chromatic number and domination number and such that an O((n+m)^2-ε)-time algorithm refutes the SETH.
Since the idea is the same as in <cit.> we refer the reader to their work for more details.
Let ϕ be a CNF-SAT instance with variable set W and clause set C.
Assume without loss of generality that |W| is even.
We construct an instance (G=(V,E), k) for  as follows:

Randomly partition W into two set W_1,W_2 of equal size.
Add three sets V_1,V_2 and B of vertices to G where each vertex in V_1 (in V_2) represents one of 2^|W_1| = 2^|W_2| possible assignments of the variables in W_1 (in W_2) and each vertex in B represents a clause in C.
Clearly |V_1| + |V_2| = 2 · 2^|W|/2 and |B| = |C|.
For each v_i∈ V_1 and each u_j∈ B we add a new vertex s_ij and the two edges {v_i,s_ij} and {u_j,s_ij} to G if the respective variable assignment does not satisfy the respective clause.
We call the set of all these newly introduced vertices S_1.
Now repeat the process for all vertices w_i∈ V_2 and all u_j in B and call the newly introduced vertices q_ij and the set S_2.
Finally we add four new vertices t_1,t_2,t_3,t_4 and the following sets of edges to G:
{{t_1,v}| v∈ V_1}, {{t_2,s}| s∈ S_1}, {{t_3,q}| q∈ S_2}, {{t_4,w}| w∈ V_2}, {{t_2,b},{t_3,b}| b ∈ B}, and {{t_1,t_2},{t_2,t_3},{t_3,t_4}}.
See <Ref> for a schematic illustration of the construction. 



We will first show that ϕ is satisfiable if and only if G has diameter five and then show that the domination number and acyclic chromatic number of G are five and four, respectively.
First assume that ϕ is satisfiable.
Then, there exists some assignment β of the variables such that all clauses are satisfied, that is, the two assignments of β with respect to the variables in W_1 and W_2 satisfy all clauses.
Let v_1∈ V_1 and v_2∈ V_2 be the vertices corresponding to β. 
Thus for each b∈ B we have (v_1,b) + (v_2,b) ≥ 5.
Observe that all paths from a vertex in V_1 to a vertex in V_2 that do not pass a vertex in B pass through t_2 and t_3.
Since all of these paths are of length 5, it follows that (v_1,v_2) = 5.
Observe that the diameter of G is at most five since each vertex is connected to some vertex in {t_1,t_2,t_3,t_4} and these four are of pairwise distance at most three.

Assume next that the diameter of G is five.
Clearly there is a shortest path between a vertex v_i∈ V_1 and v_j∈ V_2 of length five.
Thus there is no path of the form v_is_ihu_hq_jhw_j for any u_h ∈ B.
This corresponds to the statement that the variable assignment of v_i and w_j satisfy all clauses and therefore ϕ is satisfiable.

The domination number of G is four since {t_1,t_2,t_3,t_4} is a dominating set.
The acyclic chromatic number of G is at most five as V_1 ∪ V_2, B, S_1 ∪ S_2 ∪{t_1,t_4}, {t_2} and {t_3} each induce an independent set and each combination of them not including S_1 ∪ S_2 ∪{t_1,t_4} only induce independent sets or stars.
Lastly, note that S_1 ∪ S_2 ∪{t_1,t_4} and {t_2} or {t_3} only induces a star and an independent set, S_1 ∪ S_2 ∪{t_1,t_4} and V_1 ∪ V_2 induces two trees of depth 2 (where t_1 and t_4 are the roots and S_1 and S_2 are the leaves), and S_1 ∪ S_2 ∪{t_1,t_4} and B induce a disjoint union of stars and isolated vertices as each vertex in S_1 ∪ S_2 ∪{t_1,t_4} has maximum degree one in G[B ∪ S_1 ∪ S_2 ∪{t_1,t_4}].


Now assume that we have an O(f(k)· (n+m)^2-ϵ)-time algorithm for  parameterized by domination number and acyclic chromatic number.
Since the constructed graph has O(2^|W|/2· |C|) vertices and edges, this would imply an algorithm with running time

    O(f(9)· (2^|W|/2· |C|)^2-ϵ)
    
    =    O(2^(|W|/2) (2-ϵ)· |C|^(2-ϵ))
    
    =    O(2^|W| (1 - ϵ / 2)· |C|^(2-ϵ)) 
    
    =    2^|W| (1 - ϵ')· (|C| + |W|)^O(1) for some  ε'>0.

Hence, such an algorithm for  would refute the SETH.





§ CONCLUSION

We have resolved the complexity status of  for most of the parameters in the complexity landscape shown in <Ref>.
However, several open questions remain.
For example, is there an f(k)n^2-time algorithm with respect to the parameter diameter?
Moreover, our algorithms working with parameter combinations have mostly impractical running times which, assuming SETH, cannot be improved by much.
So the question arises, whether there are parameters k_1, …, k_ℓ that allow for practically relevant running times like ∏_i=1^ℓ k_i · (n+m) or even (n+m) ·∑_i=1^ℓ k_i?
The list of parameters displayed in <Ref> is by no means exhaustive.
Hence, the question arises which other parameters are small in typical scenarios? 
For example, what is a good parameter capturing the special community structures of social networks <cit.>?


plainnat




