DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2021.16

Optimal Centrality Computations Within Bounded Clique-Width Graphs

Authors: Guillaume Ducoffe

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract

Given an n-vertex m-edge graph G of clique-width at most k, and a corresponding k-expression, we present algorithms for computing some well-known centrality indices (eccentricity and closeness) that run in O(2^{O(k)}(n+m)^{1+ε}) time for any ε > 0. Doing so, we can solve various distance problems within the same amount of time, including: the diameter, the center, the Wiener index and the median set. Our run-times match conditional lower bounds of Coudert et al. (SODA'18) under the Strong Exponential-Time Hypothesis. On our way, we get a distance-labeling scheme for n-vertex m-edge graphs of clique-width at most k, using O(klog²{n}) bits per vertex and constructible in Õ(k(n+m)) time from a given k-expression. Doing so, we match the label size obtained by Courcelle and Vanicat (DAM 2016), while we considerably improve the dependency on k in their scheme. As a corollary, we get an Õ(kn²)-time algorithm for computing All-Pairs Shortest-Paths on n-vertex graphs of clique-width at most k, being given a k-expression. This partially answers an open question of Kratsch and Nelles (STACS'20). Our algorithms work for graphs with non-negative vertex-weights, under two different types of distances studied in the literature. For that, we introduce a new type of orthogonal range query as a side contribution of this work, that might be of independent interest.

Cite as

Guillaume Ducoffe. Optimal Centrality Computations Within Bounded Clique-Width Graphs. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ducoffe:LIPIcs.IPEC.2021.16,
  author =	{Ducoffe, Guillaume},
  title =	{{Optimal Centrality Computations Within Bounded Clique-Width Graphs}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.16},
  URN =		{urn:nbn:de:0030-drops-153995},
  doi =		{10.4230/LIPIcs.IPEC.2021.16},
  annote =	{Keywords: Clique-width, Centralities computation, Facility Location problems, Distance-labeling scheme, Fine-grained complexity in P, Graph theory}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2021.44

On Computing the Average Distance for Some Chordal-Like Graphs

Authors: Guillaume Ducoffe

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract

The Wiener index of a graph G is the sum of all its distances. Up to renormalization, it is also the average distance in G. The problem of computing this parameter has different applications in chemistry and networks. We here study when it can be done in truly subquadratic time (in the size n+m of the input) on n-vertex m-edge graphs. Our main result is a complete answer to this question, assuming the Strong Exponential-Time Hypothesis (SETH), for all the hereditary subclasses of chordal graphs. Interestingly, the exact same result also holds for the diameter problem. The case of non-hereditary chordal subclasses happens to be more challenging. For the chordal Helly graphs we propose an intricate Õ(m^{3/2})-time algorithm for computing the Wiener index, where m denotes the number of edges. We complete our results with the first known linear-time algorithm for this problem on the dually chordal graphs. The former algorithm also computes the median set.

Cite as

Guillaume Ducoffe. On Computing the Average Distance for Some Chordal-Like Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 44:1-44:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ducoffe:LIPIcs.MFCS.2021.44,
  author =	{Ducoffe, Guillaume},
  title =	{{On Computing the Average Distance for Some Chordal-Like Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{44:1--44:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.44},
  URN =		{urn:nbn:de:0030-drops-144841},
  doi =		{10.4230/LIPIcs.MFCS.2021.44},
  annote =	{Keywords: Wiener index, Graph diameter, Hardness in P, Chordal graphs, Helly graphs}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2019.59

Minimizing and Computing the Inverse Geodesic Length on Trees

Authors: Serge Gaspers and Joshua Lau

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract

For any fixed measure H that maps graphs to real numbers, the MinH problem is defined as follows: given a graph G, an integer k, and a target tau, is there a set S of k vertices that can be deleted, so that H(G - S) is at most tau? In this paper, we consider the MinH problem on trees. We call H balanced on trees if, whenever G is a tree, there is an optimal choice of S such that the components of G - S have sizes bounded by a polynomial in n / k. We show that MinH on trees is Fixed-Parameter Tractable (FPT) for parameter n / k, and furthermore, can be solved in subexponential time, and polynomial space, whenever H is additive, balanced on trees, and computable in polynomial time. A particular measure of interest is the Inverse Geodesic Length (IGL), which is used to gauge the efficiency and connectedness of a graph. It is defined as the sum of inverse distances between every two vertices: IGL(G) = sum_{{u,v} subseteq V} 1/d_G(u,v). While MinIGL is W[1]-hard for parameter treewidth, and cannot be solved in 2^{o(k + n + m)} time, even on bipartite graphs with n vertices and m edges, the complexity status of the problem remains open in the case where G is a tree. We show that IGL is balanced on trees, to give a 2^O((n log n)^(5/6)) time, polynomial space algorithm. The distance distribution of G is the sequence {a_i} describing the number of vertex pairs distance i apart in G: a_i = |{{u, v}: d_G(u, v) = i}|. Given only the distance distribution, one can easily determine graph parameters such as diameter, Wiener index, and particularly, the IGL. We show that the distance distribution of a tree can be computed in O(n log^2 n) time by reduction to polynomial multiplication. We also extend the result to graphs with small treewidth by showing that the first p values of the distance distribution can be computed in 2^(O(tw(G))) n^(1 + epsilon) sqrt(p) time, and the entire distance distribution can be computed in 2^(O(tw(G))) n^{1 + epsilon} time, when the diameter of G is O(n^epsilon') for every epsilon' > 0.

Cite as

Serge Gaspers and Joshua Lau. Minimizing and Computing the Inverse Geodesic Length on Trees. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.ISAAC.2019.59,
  author =	{Gaspers, Serge and Lau, Joshua},
  title =	{{Minimizing and Computing the Inverse Geodesic Length on Trees}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{59:1--59:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.59},
  URN =		{urn:nbn:de:0030-drops-115555},
  doi =		{10.4230/LIPIcs.ISAAC.2019.59},
  annote =	{Keywords: Trees, Treewidth, Fixed-Parameter Tractability, Inverse Geodesic Length, Vertex deletion, Polynomial multiplication, Distance distribution}
}

Document

DOI: 10.4230/DagSemProc.09281.6

Rounds in Combinatorial Search

Authors: Gábor Wiener

Published in: Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009)

Abstract

The search complexity of a separating system ${cal H} subseteq 2^{[m]}$ is the minimum number of questions of type ``$xin H$? hinspace '' (where $H in {cal H}$) needed in the worst case to determine a hidden element $xin [m]$. If we are allowed to ask the questions in at most $k$ batches then we speak of the emph{$k$-round} (or emph{$k$-stage}) complexity of ${cal H}$, denoted by $hbox{c}_k ({cal H})$. While $1$-round and $m$-round complexities (called non-adaptive and adaptive complexities, respectively) are widely studied (see for example Aigner cite{A}), much less is known about other possible values of $k$, though the cases with small values of $k$ (tipically $k=2$) attracted significant attention recently, due to their applications in DNA library screening. It is clear that $ |{cal H}| geq hbox{c}_{1} ({cal H}) geq hbox{c}_{2} ({cal H}) geq ldots geq hbox{c}_{m} ({cal H})$. A group of problems raised by {G. O. H. Katona} cite{Ka} is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems ${cal H}$ with the property $|{cal H}| = hbox{c}_{k} ({cal H}) $ for any $kgeq 3$. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest.

Cite as

Gábor Wiener. Rounds in Combinatorial Search. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{wiener:DagSemProc.09281.6,
  author =	{Wiener, G\'{a}bor},
  title =	{{Rounds in Combinatorial Search}},
  booktitle =	{Search Methodologies},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.6},
  URN =		{urn:nbn:de:0030-drops-22399},
  doi =		{10.4230/DagSemProc.09281.6},
  annote =	{Keywords: Search, group testing, adaptiveness, hypergraph, trace}
}

Document

DOI: 10.4230/DagSemProc.05491.7

Path planning and optimization in the traveling salesman problem: Nearest neighbor vs. region-based strategies

Authors: Jan Malte Wiener, Nicole N. Ehbauer, and H. A. Mallot

Published in: Dagstuhl Seminar Proceedings, Volume 5491, Spatial Cognition: Specialization and Integration (2007)

Abstract

According to the number of targets, route planning can be a very complex task. Human navigators, however, usually solve route planning tasks fastly and efficiently. Here two experiments are presented that studied human route planning performance, route planning strategies employed, and cognitive processes involved. For this, 25 places were arranged on a regular grid in a large room. Each place was marked by a unique symbol. Subjects were repeatedly asked to solve traveling salesman problems (TSP), i.e. to find the shortest closed loop connecting a given start place with a number of target places. For this, subjects were given a so-called 'shopping list' depicting the symbols of the start place and the target places. While the TSP is computationally hard, sufficient solutions can be found by simple strategies such as the nearest neighbor strategy. In Experiment 1, it was tested whether humans deployed the nearest neighbor strategy (NNS) when solving the TSP. Results showed that subjects outperformed the NNS in cases in which the NNS did not predict the optimal solution, suggesting that the NNS is not sufficient to explain human route planning behavior. As a second possible strategy a region-based approach was tested in Experiment 2. When optimal routes required more region transitions than other, sub-optimal routes, subjects preferred these sub-optimal routes. This result suggests that subjects first planned a coarse route on the region level and then refined the route during navigation. Such a hierarchical planning stragey would allow to reduce computational effort during route planning. In a control condition, the target places were directly marked in the environment rather than being depicted on the shopping list. As subjects did not have to identify and remember the positions of the target places based on the shopping list during route planning, this control condition tested for the influence of spatial working memory for route planning performance. Results showed a strong performance increase in the control condition, emphasizing the prominent role of spatial working memory for route planning.

Cite as

Jan Malte Wiener, Nicole N. Ehbauer, and H. A. Mallot. Path planning and optimization in the traveling salesman problem: Nearest neighbor vs. region-based strategies. In Spatial Cognition: Specialization and Integration. Dagstuhl Seminar Proceedings, Volume 5491, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{wiener_et_al:DagSemProc.05491.7,
  author =	{Wiener, Jan Malte and Ehbauer, Nicole N. and Mallot, H. A.},
  title =	{{Path planning and optimization in the traveling salesman problem: Nearest neighbor vs. region-based strategies}},
  booktitle =	{Spatial Cognition: Specialization and Integration},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{5491},
  editor =	{Anthony G. Cohn and Christian Freksa and Bernhard Nebel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05491.7},
  URN =		{urn:nbn:de:0030-drops-9848},
  doi =		{10.4230/DagSemProc.05491.7},
  annote =	{Keywords: Spatial cognition, navigation, route planning, path complexity, traveling salesman problem, regions, hierarchical planning, nearest neighbor strategy}
}

5 Search Results for "Wiener, G�bor"

Optimal Centrality Computations Within Bounded Clique-Width Graphs

Abstract

Cite as

On Computing the Average Distance for Some Chordal-Like Graphs

Abstract

Cite as

Minimizing and Computing the Inverse Geodesic Length on Trees

Abstract

Cite as

Rounds in Combinatorial Search

Abstract

Cite as

Path planning and optimization in the traveling salesman problem: Nearest neighbor vs. region-based strategies

Abstract

Cite as

Thanks for your feedback!

Could not send message