---
_id: '11826'
abstract:
- lang: eng
  text: "The diameter, radius and eccentricities are natural graph parameters. While
    these problems have been studied extensively, there are no known dynamic algorithms
    for them beyond the ones that follow from trivial recomputation after each update
    or from solving dynamic All-Pairs Shortest Paths (APSP), which is very computationally
    intensive. This is the situation for dynamic approximation algorithms as well,
    and even if only edge insertions or edge deletions need to be supported.\r\nThis
    paper provides a comprehensive study of the dynamic approximation of Diameter,
    Radius and Eccentricities, providing both conditional lower bounds, and new algorithms
    whose bounds are optimal under popular hypotheses in fine-grained complexity.
    Some of the highlights include:\r\n- Under popular hardness hypotheses, there
    can be no significantly better fully dynamic approximation algorithms than recomputing
    the answer after each update, or maintaining full APSP.\r\n- Nearly optimal partially
    dynamic (incremental/decremental) algorithms can be achieved via efficient reductions
    to (incremental/decremental) maintenance of Single-Source Shortest Paths. For
    instance, a nearly (3/2+epsilon)-approximation to Diameter in directed or undirected
    n-vertex, m-edge graphs can be maintained decrementally in total time m^{1+o(1)}sqrt{n}/epsilon^2.
    This nearly matches the static 3/2-approximation algorithm for the problem that
    is known to be conditionally optimal."
alternative_title:
- LIPIcs
article_number: '13'
article_processing_charge: No
arxiv: 1
author:
- first_name: Bertie
  full_name: Ancona, Bertie
  last_name: Ancona
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Liam
  full_name: Roditty, Liam
  last_name: Roditty
- first_name: Virginia Vassilevska
  full_name: Williams, Virginia Vassilevska
  last_name: Williams
- first_name: Nicole
  full_name: Wein, Nicole
  last_name: Wein
citation:
  ama: 'Ancona B, Henzinger M, Roditty L, Williams VV, Wein N. Algorithms and hardness
    for diameter in dynamic graphs. In: <i>46th International Colloquium on Automata,
    Languages, and Programming</i>. Vol 132. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik; 2019. doi:<a href="https://doi.org/10.4230/LIPICS.ICALP.2019.13">10.4230/LIPICS.ICALP.2019.13</a>'
  apa: 'Ancona, B., Henzinger, M., Roditty, L., Williams, V. V., &#38; Wein, N. (2019).
    Algorithms and hardness for diameter in dynamic graphs. In <i>46th International
    Colloquium on Automata, Languages, and Programming</i> (Vol. 132). Patras, Greece:
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPICS.ICALP.2019.13">https://doi.org/10.4230/LIPICS.ICALP.2019.13</a>'
  chicago: Ancona, Bertie, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams,
    and Nicole Wein. “Algorithms and Hardness for Diameter in Dynamic Graphs.” In
    <i>46th International Colloquium on Automata, Languages, and Programming</i>,
    Vol. 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href="https://doi.org/10.4230/LIPICS.ICALP.2019.13">https://doi.org/10.4230/LIPICS.ICALP.2019.13</a>.
  ieee: B. Ancona, M. Henzinger, L. Roditty, V. V. Williams, and N. Wein, “Algorithms
    and hardness for diameter in dynamic graphs,” in <i>46th International Colloquium
    on Automata, Languages, and Programming</i>, Patras, Greece, 2019, vol. 132.
  ista: 'Ancona B, Henzinger M, Roditty L, Williams VV, Wein N. 2019. Algorithms and
    hardness for diameter in dynamic graphs. 46th International Colloquium on Automata,
    Languages, and Programming. ICALP: International Colloquium on Automata, Languages,
    and Programming, LIPIcs, vol. 132, 13.'
  mla: Ancona, Bertie, et al. “Algorithms and Hardness for Diameter in Dynamic Graphs.”
    <i>46th International Colloquium on Automata, Languages, and Programming</i>,
    vol. 132, 13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:<a
    href="https://doi.org/10.4230/LIPICS.ICALP.2019.13">10.4230/LIPICS.ICALP.2019.13</a>.
  short: B. Ancona, M. Henzinger, L. Roditty, V.V. Williams, N. Wein, in:, 46th International
    Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2019.
conference:
  end_date: 2019-07-12
  location: Patras, Greece
  name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
  start_date: 2019-07-09
date_created: 2022-08-12T08:14:51Z
date_published: 2019-07-04T00:00:00Z
date_updated: 2024-11-06T11:56:23Z
day: '04'
doi: 10.4230/LIPICS.ICALP.2019.13
extern: '1'
external_id:
  arxiv:
  - '811.12527'
intvolume: '       132'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.ICALP.2019.13
month: '07'
oa: 1
oa_version: Published Version
publication: 46th International Colloquium on Automata, Languages, and Programming
publication_identifier:
  isbn:
  - 978-3-95977-109-2
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algorithms and hardness for diameter in dynamic graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 132
year: '2019'
...
---
_id: '6725'
abstract:
- lang: eng
  text: "A Valued Constraint Satisfaction Problem (VCSP) provides a common framework
    that can express a wide range of discrete optimization problems. A VCSP instance
    is given by a finite set of variables, a finite domain of labels, and an objective
    function to be minimized. This function is represented as a sum of terms where
    each term depends on a subset of the variables. To obtain different classes of
    optimization problems, one can restrict all terms to come from a fixed set Γ of
    cost functions, called a language. \r\nRecent breakthrough results have established
    a complete complexity classification of such classes with respect to language
    Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances
    can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately,
    testing this condition for a given language Γ is known to be NP-hard. We thus
    study exponential algorithms for this meta-problem. We show that the tractability
    condition of a finite-valued language Γ can be tested in O(3‾√3|D|⋅poly(size(Γ)))
    time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also
    obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH).
    More precisely, we prove that for any constant δ<1 there is no O(3‾√3δ|D|) algorithm,
    assuming that SETH holds."
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
citation:
  ama: 'Kolmogorov V. Testing the complexity of a valued CSP language. In: <i>46th
    International Colloquium on Automata, Languages and Programming</i>. Vol 132.
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:77:1-77:12. doi:<a href="https://doi.org/10.4230/LIPICS.ICALP.2019.77">10.4230/LIPICS.ICALP.2019.77</a>'
  apa: 'Kolmogorov, V. (2019). Testing the complexity of a valued CSP language. In
    <i>46th International Colloquium on Automata, Languages and Programming</i> (Vol.
    132, p. 77:1-77:12). Patras, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPICS.ICALP.2019.77">https://doi.org/10.4230/LIPICS.ICALP.2019.77</a>'
  chicago: Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.”
    In <i>46th International Colloquium on Automata, Languages and Programming</i>,
    132:77:1-77:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href="https://doi.org/10.4230/LIPICS.ICALP.2019.77">https://doi.org/10.4230/LIPICS.ICALP.2019.77</a>.
  ieee: V. Kolmogorov, “Testing the complexity of a valued CSP language,” in <i>46th
    International Colloquium on Automata, Languages and Programming</i>, Patras, Greece,
    2019, vol. 132, p. 77:1-77:12.
  ista: 'Kolmogorov V. 2019. Testing the complexity of a valued CSP language. 46th
    International Colloquium on Automata, Languages and Programming. ICALP: Automata,
    Languages and Programming, LIPIcs, vol. 132, 77:1-77:12.'
  mla: Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” <i>46th
    International Colloquium on Automata, Languages and Programming</i>, vol. 132,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12, doi:<a
    href="https://doi.org/10.4230/LIPICS.ICALP.2019.77">10.4230/LIPICS.ICALP.2019.77</a>.
  short: V. Kolmogorov, in:, 46th International Colloquium on Automata, Languages
    and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12.
conference:
  end_date: 2019-07-12
  location: Patras, Greece
  name: 'ICALP: Automata, Languages and Programming'
  start_date: 2019-07-08
date_created: 2019-07-29T12:23:29Z
date_published: 2019-07-01T00:00:00Z
date_updated: 2025-07-10T11:53:47Z
day: '01'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.4230/LIPICS.ICALP.2019.77
ec_funded: 1
external_id:
  arxiv:
  - '1803.02289'
file:
- access_level: open_access
  checksum: f5ebee8eec6ae09e30365578ee63a492
  content_type: application/pdf
  creator: dernst
  date_created: 2019-07-31T07:01:45Z
  date_updated: 2020-07-14T12:47:38Z
  file_id: '6738'
  file_name: 2019_LIPICS_Kolmogorov.pdf
  file_size: 575475
  relation: main_file
file_date_updated: 2020-07-14T12:47:38Z
has_accepted_license: '1'
intvolume: '       132'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 77:1-77:12
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '616160'
  name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: 46th International Colloquium on Automata, Languages and Programming
publication_identifier:
  isbn:
  - 978-3-95977-109-2
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Testing the complexity of a valued CSP language
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 132
year: '2019'
...