\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{4}{Sunday, December 18, 2017} % Number, Deadline
\textit{Total points : 40}
\vspace{1ex}
\textit{Prove all your claims!}
%\vspace{2ex}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{1}{10}
Let $ A $ and $ B $ be two $ n \times n $ matrices with integer entries in $ \{ -M, -M +\nobreak 1, \ldots,\allowbreak M -\nobreak 1,\allowbreak M \} $.
Show that the min-plus matrix product of $ A $ and $ B $ can be computed in time $ O(M^{2} \cdot n^{\omega}) $.
Here $ \omega $ is the exponent of matrix multiplication.
\textit{Remark:} This problem can actually be solved in time $(M\cdot n^{\omega}\cdot\poly(\log M,\log n))$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{2}{10}
In the \textbf{$k$-Clique} problem, we are given an unweighted undirected graph~$ G $ and are asked to decide if $ G $ contains a $k$-clique (i.e., a set of $ k $ vertices which are pairwise adjacent).
Show that if $k$ is divisible by $ 3 $, then $k$-\textbf{Clique} can be solved in time $O(n^{\frac{\omega k}{3}})$.
%Bonus: Which running time can you obtain when $3\nmid k$?
\textit{Hint:} Reduce the problem to detecting a triangle in a graph with $ O( n^{\frac{k}{3}})$ vertices.
\textit{Remark:} This is the best running time known for this problem.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{3}{10}
In the \textbf{Zero-Weight 3-Star} problem, we are given a weighted 4-partite graph $ G = (V_1 \cup V_2 \cup V_3 \cup V_4, E) $, where $ |V_1| = |V_2| = |V_3| = |V_4| = n $, and are asked to decide whether there are $ v_1 \in V_1, v_2 \in V_2, v_3 \in V_3 $, and $ v_4 \in V_4 $ such that $ w (v_1, v_2) + w (v_1, v_3) + w (v_1, v_4) = 0 $.
Show that \textbf{Zero-Weight 3-Star} has an algorithm with running time $ O (n^{3 - \epsilon}) $ (for some $ \epsilon > 0 $) if and only if there is an algorithm with running time $ O (n^{3 - \delta}) $ (for some $ \delta > 0 $) that decides if at least one of $ n $ given \textbf{3SUM} instances has a solution.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise{4}{10}
In the \textbf{Segment Visibility} problem, we are given a set $ S $ of $ n $ line segments in the plane and two distinguished line segments $ a $ and~$ b $, and are asked to decide whether there are points $ p $ on $ a $ and $ q $ on $ b $ such that the line through the points $ p $ and~$ q $ does not intersect any line segment in~$ S $ (i.e., we want to check whether $ a $ is ``visible'' from $ b $).
Show that if \textbf{Segment Visibility} can be solved in them $ O (n^{2 - \epsilon}) $ for some $ \epsilon > 0 $, then \textbf{3SUM} can be solved in time $ O (n^{2 - \delta}) $ for some $ \delta > 0 $.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}