\documentclass[12pt,a4paper]{article}
\usepackage{iftex}
\ifPDFTeX
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\fi
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\ifPDFTeX
\usepackage{libertine}
\usepackage[libertine]{newtxmath} % must load after ams packages
\usepackage{MnSymbol}
\else
\usepackage{unicode-math}
\setmainfont{Libertinus Serif}
\setmathfont{Libertinus Math}
\fi
\usepackage[DIV=12]{typearea} % large value = less margin, recommended values: 10pt: 8, 11pt: 10, 12pt: 12
\usepackage{microtype}
\usepackage{url}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1ex}
\pagestyle{empty}
\newcommand{\exercise}[2]{
\vspace{3ex}
\textbf{Exercise #1 }(\emph{#2 points)}
\vspace{-0.5ex}
}
\newcommand{\solution}{
\vspace{2ex}
\textbf{Solution:}
\vspace{0.5ex}
}
\newcommand{\course}{PS Complexity of Polynomial-Time Problems}
\newcommand{\website}{\url{https://www.cosy.sbg.ac.at/~sk/courses/polycomp/}}
\newcommand{\sheet}[2]{%
\begin{center}
{\Large \textbf{\course}}
\vspace{0.5ex}
{\footnotesize \website}
\vspace{2ex}
{\large
Exercise sheet #1
\hfill
Due: #2
}
\end{center}
\vspace*{2ex}
}
\newcommand{\lecturer}{Sebastian Krinninger}
\newcommand{\term}{Winter 2017/18}
\DeclareMathOperator{\poly}{poly}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{conjecture}[theorem]{Conjecture}
\newcommand{\dist}{\operatorname{dist}}
\newcommand{\diam}{\operatorname{diam}}
\newcommand{\bc}{\operatorname{BC}}
\begin{document}
\sheet{3}{Sunday, December 3, 2017} % Number, Deadline
\textit{Total points : 40}
\vspace{1ex}
\textit{Prove all your claims!}
%\vspace{2ex}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{1}{10}
The \textbf{Metricity} problem is defined as follows:
Given an $ n \times n $ matrix~$ A $ with entries in $ \{0, \ldots, \lfloor n^{c} \rfloor \} $ for some constant $ c > 0 $, decide whether $ A [i, j] \leq A [i, k] + A [k, j] $ for all $ i, j, k \in \{ 1, \dots, n \} $.
Prove that \textbf{Metricity} is equivalent to \textbf{APSP} under subcubic reductions.
\emph{\textbf{Hint}: Reduce \textbf{Metricity} to \textbf{Min-Plus Product} and reduce \textbf{Negative Triangle} to \textbf{Metricity}.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{2}{10}
Consider a directed graph $ G = (V, E, w) $ with positive integer weights in the range $ w (e) \in \{ 1, 2, \ldots, W \} $ for each edge $ e \in E $.
The \textbf{Betweenness Centrality} of a node $ v \in V $ is the number of pairs $ s, t $ such that $ v $ lies on a shortest path from $ s $ to $ t $, i.e.,
\begin{equation*}
\bc_G (v) = \big| \{ (s, t) : s, t \in V \setminus \{ v \} , s \neq t, \dist (s,t) = \dist_G (s,v) + \dist_G (v,t) \} \big| \, .
\end{equation*}
and the \textbf{Diameter} of $ G $ is the maximum distance between any pair of nodes, i.e.,
\begin{equation*}
\diam (G) = \max_{s, t \in V} \dist_G (s, t) \, .
\end{equation*}
Show that if there is an algorithm for computing the \textbf{Betweenness Centrality} of a node in a graph with positive edge weights running in time $ T (n, m) $, then there is an algorithm for computing the diameter of a graph with positive edge weights running in time
\begin{equation*}
O \Big( T \big( O(n), O(m + n) \big) \log{(n W)} + m \Big) \, .
\end{equation*}
\emph{\textbf{Hint}: Introduce a \emph{dummy node} and perform binary search to find the value of the diameter.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{3}{10}
Give an algorithm for \textbf{Orthogonal Vectors} with running time $ O (n^\omega) $, i.e., an algorithm that (theoretically) outperforms the naive $ O (n^2 d) $-time algorithm in the high-dimensional regime.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{4}{10}
Work out the subcubic reduction from \textbf{All-Pairs Triangle Detection} to \textbf{Triangle Detection} mentioned in class.
Note: As a consequence, this will prove that if there is a subquadratic \emph{combinatorial} algorithm for \textbf{Triangle Detection}, then there also is a subquadratic \emph{combinatorial} algorithm for \textbf{All-Pairs Triangle Detection}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}