Search

Among the most fundamental graph parameters is the Diameter, the largest distance between any pair of vertices. Computing the Diameter of a graph with $m$ edges requires $m^{2-o(1)}$ time under the Strong Exponential Time Hypothesis (SETH), which can be prohibitive for very large graphs, so efficient approximation algorithms for Diameter are desired. There is a folklore algorithm that gives a $2$-approximation for Diameter in $\tilde{O}(m)$ time. Additionally, a line of work concludes with a $3/2$-approximation algorithm for Diameter in weighted directed graphs that runs in $\tilde{O}(m^{3/2})$ time. The $3/2$-approximation algorithm is known to be tight under SETH: Roditty and Vassilevska W. proved that under SETH any $3/2-\epsilon$ approximation algorithm for Diameter in undirected unweighted graphs requires $m^{2-o(1)}$ time, and then Backurs, Roditty, Segal, Vassilevska W., and Wein and the follow-up work of Li proved that under SETH any $5/3-\epsilon$ approximation algorithm for Diameter in undirected unweighted graphs requires $m^{3/2-o(1)}$ time. Whether or not the folklore 2-approximation algorithm is tight, however, is unknown, and has been explicitly posed as an open problem in numerous papers. Towards this question, Bonnet recently proved that under SETH, any $7/4-\epsilon$ approximation requires $m^{4/3-o(1)}$, only for directed weighted graphs. We completely resolve this question for directed graphs by proving that the folklore 2-approximation algorithm is conditionally optimal. In doing so, we obtain a series of conditional lower bounds that together with prior work, give a complete time-accuracy trade-off that is tight with all known algorithms for directed graphs. Specifically, we prove that under SETH for any $\delta>0$, a $(\frac{2k-1}{k}-\delta)$-approximation algorithm for Diameter on directed unweighted graphs requires $m^{\frac{k}{k-1}-o(1)}$ time., Comment: Updated to cite concurrent work

Attempts to prove the intractability of the Minimum Circuit Size Problem (MCSP) date as far back as the 1950s and are well-motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing MCSP is intractable under worst-case assumptions. While Masek showed in the late 1970s that the version of MCSP for DNF formulas is NP-hard, extending this result to the case of depth-3 AND/OR formulas was open. We show that determining the minimum size of a depth- $d$ formula computing a given Boolean function is N P-hard under quasipolynomial-time randomized reductions for all constant $d\geq 2$ . Our approach is based on a method to “lift” depth- $d$ formula lower bounds to depth-( $d+1$ ). This method also implies the existence of a function with a $2^{\Omega_{d}(n^{1/5}}$ ) additive gap between its depth-d and depth-( $d+1$ ) formula complexity. We also make progress in the case of general, unrestricted circuits. We show that the version of MCSP where the input is a partial function (represented by a string in $\{0,1, ?\}^{\ast}$ ) is not in P under the Exponential Time Hypothesis (ETH). Intriguingly, we formulate a notion of lower bound statements being (P/poly)-recognizable that is closely related to Razborov and Rudich's definition of being (P/poly)-constructive. We show that unless there are subexponential-sized circuits computing SAT, the lower bound statements used to prove the correctness of our reductions cannot be (P/poly)-recognizable.

We study the problem of finding a maximum cardinality minimal separator of a graph. This problem is known to be NP-hard even for bipartite graphs. In this paper, we strengthen this hardness by showing that for planar bipartite graphs, the problem remains NP-hard. Moreover, for co-bipartite graphs and for line graphs, the problem also remains NP-hard. On the positive side, we give an algorithm deciding whether an input graph has a minimal separator of size at least $k$ that runs in time $2^{O(k)}n^{O(1)}$. We further show that a subexponential parameterized algorithm does not exist unless the Exponential Time Hypothesis (ETH) fails. Finally, we discuss a lower bound for polynomial kernelizations of this problem., 15 pages

We prove several tight results on the fine-grained complexity of approximating the diameter of a graph. First, we prove that, for any $\varepsilon>0$, assuming the Strong Exponential Time Hypothesis (SETH), there are no near-linear time $2-\varepsilon$-approximation algorithms for the Diameter of a sparse directed graph, even in unweighted graphs. This result shows that a simple near-linear time 2-approximation algorithm for Diameter is optimal under SETH, answering a question from a survey of Rubinstein and Vassilevska-Williams (SIGACT '19) for the case of directed graphs. In the same survey, Rubinstein and Vassilevska-Williams also asked if it is possible to show that there are no $2-\varepsilon$ approximation algorithms for Diameter in a directed graph in $O(n^{1.499})$ time. We show that, assuming a hypothesis called NSETH, one cannot use a deterministic SETH-based reduction to rule out the existence of such algorithms. Extending the techniques in these two results, we characterize whether a $2-\varepsilon$ approximation algorithm running in time $O(n^{1+\delta})$ for the Diameter of a sparse directed unweighted graph can be ruled out by a deterministic SETH-based reduction for every $\delta\in(0,1)$ and essentially every $\varepsilon\in(0,1)$, assuming NSETH. This settles the SETH-hardness of approximating the diameter of sparse directed unweighted graphs for deterministic reductions, up to NSETH. We make the same characterization for randomized SETH-based reductions, assuming another hypothesis called NUNSETH. We prove additional hardness and non-reducibility results for undirected graphs.

In the \textsc{Waypoint Routing Problem} one is given an undirected capacitated and weighted graph $G$, a source-destination pair $s,t\in V(G)$ and a set $W\subseteq V(G)$, of \emph{waypoints}. The task is to find a walk which starts at the source vertex $s$, visits, in any order, all waypoints, ends at the destination vertex $t$, respects edge capacities, that is, traverses each edge at most as many times as is its capacity, and minimizes the cost computed as the sum of costs of traversed edges with multiplicities. We study the problem for graphs of bounded treewidth and present a new algorithm for the problem working in $2^{O(\mathrm{tw})}\cdot n$ time, significantly improving upon the previously known algorithms. We also show that this running time is optimal for the problem under Exponential Time Hypothesis., Comment: 11 pages

Given a simple polygon P on n vertices, two points x , y in P are said to be visible to each other if the line segment between x and y is contained in P . The P oint G uard A rt G allery problem asks for a minimum set S such that every point in P is visible from a point in S . The V ertex G uard A rt G allery problem asks for such a set S subset of the vertices of P . A point in the set S is referred to as a guard. For both variants, we rule out any f ( k ) n o ( k / log k ) algorithm, where k := | S | is the number of guards, for any computable function f , unless the exponential time hypothesis fails. These lower bounds almost match the n O ( k ) algorithms that exist for both problems.

We give algorithms with running time $$2^{\mathcal {O}({\sqrt{k}\log {k}})} \cdot n^{\mathcal {O}(1)}$$ for the following problems. Given an n-vertex unit disk graph G and an integer k, decide whether G contains For the first three problems, no subexponential time parameterized algorithms were previously known. For the remaining two problems, our algorithms significantly outperform the previously best known parameterized algorithms that run in time $$2^{\mathcal {O}(k^{0.75}\log {k})} \cdot n^{\mathcal {O}(1)}$$ . Our algorithms are based on a new kind of tree decompositions of unit disk graphs where the separators can have size up to $$k^{\mathcal {O}(1)}$$ and there exists a solution that crosses every separator at most $$\mathcal {O}(\sqrt{k})$$ times. The running times of our algorithms are optimal up to the $$\log {k}$$ factor in the exponent, assuming the exponential time hypothesis.

We prove that there is no fpt-algorithm that can approximate the dominating set problem with any constant ratio, unless FPT = W[1]. Our hardness reduction is built on the second author's recent W[1]-hardness proof of the biclique problem [25]. This yields, among other things, a proof without the PCP machinery that the classical dominating set problem has no polynomial time constant approximation under the exponential time hypothesis.

The weak 2-linkage problem for digraphs asks for a given digraph and vertices s 1 , s 2 , t 1 , t 2 whether D contains a pair of arc-disjoint paths P 1 , P 2 such that P i is an ( s i , t i ) -path. This problem is NP-complete for general digraphs but polynomially solvable for acyclic digraphs [8] . Recently it was shown [3] that if D is equipped with a weight function w on the arcs which satisfies that all edges have positive weight, then there is a polynomial algorithm for the variant of the weak-2-linkage problem when both paths have to be shortest paths in D. In this paper we consider the unit weight case and prove that for every pair of constants k 1 , k 2 , there is a polynomial algorithm which decides whether the input digraph D has a pair of arc-disjoint paths P 1 , P 2 such that P i is an ( s i , t i ) -path of length no more than d ( s i , t i ) + k i , for i = 1 , 2 , where d ( s i , t i ) denotes the length of the shortest ( s i , t i ) -path. We prove that, unless the exponential time hypothesis (ETH) fails, there is no polynomial algorithm for deciding the existence of a solution P 1 , P 2 to the weak 2-linkage problem where each path P i has length at most d ( s i , t i ) + c log 1 + ϵ ⁡ n for some constant c.

For a finite collection of graphs ${\cal F}$, the ${\cal F}$-M-DELETION (resp. ${\cal F}$-TM-DELETION) problem consists in, given a graph $G$ and an integer $k$, decide whether there exists $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as a minor (resp. topological minor). We are interested in the parameterized complexity of both problems when the parameter is the treewidth of $G$, denoted by $tw$, and specifically in the cases where ${\cal F}$ contains a single connected planar graph $H$. We present algorithms running in time $2^{O(tw)} \cdot n^{O(1)}$, called single-exponential, when $H$ is either $P_3$, $P_4$, $C_4$, the paw, the chair, and the banner for both $\{H\}$-M-DELETION and $\{H\}$-TM-DELETION, and when $H=K_{1,i}$, with $i \geq 1$, for $\{H\}$-TM-DELETION. Some of these algorithms use the rank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. This is the second of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of $\{H\}$-M-DELETION in terms of $H$., 36 pages, 2 figures

The maximum/minimum bisection problems are, given an edge-weighted graph, to find a bipartition of the vertex set into two sets whose sizes differ by at most one, such that the total weight of edges between the two sets is maximized/minimized. Although these two problems are known to be NP-hard, there is an efficient algorithm for bounded-treewidth graphs. In particular, Jansen et al. (SIAM J. Comput. 2005) gave an $O(2^tn^3)$-time algorithm when given a tree decomposition of width $t$ of the input graph, where $n$ is the number of vertices of the input graph. Eiben et al. (ESA 2019) improved the dependency of $n$ in the running time by giving an $O(8^tt^5n^2\log n)$-time algorithm. Moreover, they showed that there is no $O(n^{2-\varepsilon})$-time algorithm for trees under some reasonable complexity assumption. In this paper, we show an $O(2^t(tn)^2)$-time algorithm for both problems, which is asymptotically tight to their conditional lower bound. We also show that the exponential dependency of the treewidth is asymptotically optimal under the Strong Exponential Time Hypothesis. Finally, we discuss the (in)tractability of both problems with respect to special graph classes., 13 pages, 2 figures

In arXiv:1710.08163 a generalization of Boolean circuits to arbitrary finite algebras had been introduced and applied to sketch P versus NP-complete borderline for circuits satisfiability over algebras from congruence modular varieties. However the problem for nilpotent (which had not been shown to be NP-hard) but not supernilpotent algebras (which had been shown to be polynomial time) remained open. In this paper we provide a broad class of examples, lying in this grey area, and show that, under the Exponential Time Hypothesis and Strong Exponential Size Hypothesis (saying that Boolean circuits need exponentially many modular counting gates to produce boolean conjunctions of any arity), satisfiability over these algebras have intermediate complexity between $\Omega(2^{c\log^{h-1} n})$ and $O(2^{c\log^h n})$, where $h$ measures how much a nilpotent algebra fails to be supernilpotent. We also sketch how these examples could be used as paradigms to fill the nilpotent versus supernilpotent gap in general. Our examples are striking in view of the natural strong connections between circuits satisfiability and Constraint Satisfaction Problem for which the dichotomy had been shown by Bulatov and Zhuk.

Gerrymandering is a practice of manipulating district boundaries and locations in order to achieve a political advantage for a particular party. Lewenberg, Lev, and Rosenschein [AAMAS 2017] initiated the algorithmic study of a geographically-based manipulation problem, where voters must vote at the ballot box closest to them. In this variant of gerrymandering, for a given set of possible locations of ballot boxes and known political preferences of $n$ voters, the task is to identify locations for $k$ boxes out of $m$ possible locations to guarantee victory of a certain party in at least $l$ districts. Here integers $k$ and $l$ are some selected parameter. It is known that the problem is NP-complete already for 4 political parties and prior to our work only heuristic algorithms for this problem were developed. We initiate the rigorous study of the gerrymandering problem from the perspectives of parameterized and fine-grained complexity and provide asymptotically matching lower and upper bounds on its computational complexity. We prove that the problem is W[1]-hard parameterized by $k+n$ and that it does not admit an $f(n,k)\cdot m^{o(\sqrt{k})}$ algorithm for any function $f$ of $k$ and $n$ only, unless Exponential Time Hypothesis (ETH) fails. Our lower bounds hold already for $2$ parties. On the other hand, we give an algorithm that solves the problem for a constant number of parties in time $(m+n)^{O(\sqrt{k})}$., Presented at AAAI-20

We study the complexity of the problems of finding, given a graph $G$, a largest induced subgraph of $G$ with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition $V(G)$. We call these parameters ${\sf mos}(G)$ and $\chi_{{\sf odd}}(G)$, respectively. We prove that deciding whether $\chi_{{\sf odd}}(G) \leq q$ is polynomial-time solvable if $q \leq 2$, and NP-complete otherwise. We provide algorithms in time $2^{O({\sf rw})} \cdot n^{O(1)}$ and $2^{O(q \cdot {\sf rw})} \cdot n^{O(1)}$ to compute ${\sf mos}(G)$ and to decide whether $\chi_{{\sf odd}}(G) \leq q$ on $n$-vertex graphs of rank-width at most ${\sf rw}$, respectively, and we prove that the dependency on rank-width is asymptotically optimal under the ETH. Finally, we give some tight bounds for these parameters on restricted graph classes or in relation to other parameters., Comment: 24 pages, 8 figures

In the Min $k$-Cut problem, input is an edge weighted graph $G$ and an integer $k$, and the task is to partition the vertex set into $k$ non-empty sets, such that the total weight of the edges with endpoints in different parts is minimized. When $k$ is part of the input, the problem is NP-complete and hard to approximate within any factor less than $2$. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta et al.~[SODA 2018] initiated the study of FPT-approximation for the Min $k$-Cut problem and gave an $1.9997$-approximation algorithm running in time $2^{\mathcal{O}(k^6)}n^{\mathcal{O}(1)}$. Later, the same set of authors~[FOCS 2018] designed an $(1 +\epsilon)$-approximation algorithm that runs in time $(k/\epsilon)^{\mathcal{O}(k)}n^{k+\mathcal{O}(1)}$, and a $1.81$-approximation algorithm running in time $2^{\mathcal{O}(k^2)}n^{\mathcal{O}(1)}$. More, recently, Kawarabayashi and Lin~[SODA 2020] gave a $(5/3 + \epsilon)$-approximation for Min $k$-Cut running in time $2^{\mathcal{O}(k^2 \log k)}n^{\mathcal{O}(1)}$. In this paper we give a parameterized approximation algorithm with best possible approximation guarantee, and best possible running time dependence on said guarantee (up to Exponential Time Hypothesis (ETH) and constants in the exponent). In particular, for every $\epsilon > 0$, the algorithm obtains a $(1 +\epsilon)$-approximate solution in time $(k/\epsilon)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. The main ingredients of our algorithm are: a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time $s^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ on unweighted (multi-) graphs. Here, $s$ denotes the number of edges in a minimum $k$-cut. The latter two are of independent interest., Comment: 32 pages, 5 figures, to appear in FOCS '20. Typos from previous version fixed

A graph $G$ with $n$ vertices is called an outerstring graph if it has an intersection representation of a set of $n$ curves inside a disk such that one endpoint of every curve is attached to the boundary of the disk. Given an outerstring graph representation, the Maximum Independent Set (MIS) problem of the underlying graph can be computed in $O(s^3)$ time, where $s$ is the number of segments in the representation (Keil et al., Comput. Geom., 60:19--25, 2017). If the strings are of constant size (e.g., line segments, L-shapes, etc.), then the algorithm takes $O(n^3)$ time. In this paper, we examine the fine-grained complexity of the MIS problem on some well-known outerstring representations. We show that solving the MIS problem on grounded segment and grounded square-L representations is at least as hard as solving MIS on circle graph representations. Note that no $O(n^{2-\delta})$-time algorithm, $\delta>0$, is known for the MIS problem on circle graphs. For the grounded string representations where the strings are $y$-monotone simple polygonal paths of constant length with segments at integral coordinates, we solve MIS in $O(n^2)$ time and show this to be the best possible under the strong exponential time hypothesis (SETH). For the intersection graph of $n$ L-shapes in the plane, we give a $(4\cdot \log OPT)$-approximation algorithm for MIS (where $OPT$ denotes the size of an optimal solution), improving the previously best-known $(4\cdot \log n)$-approximation algorithm of Biedl and Derka (WADS 2017)., Comment: A preliminary version of this paper appeared in the 16th International Symposium on Algorithms and Data Structures (WADS 2019)

In this paper, we study Reiter's propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree decompositions that decides whether a theory has a consistent stable extension ( Cons ). Our algorithm can even be used to enumerate all generating defaults ( EnumSD ) that lead to stable extensions. We show that our algorithm decides Cons in linear time in the input theory and triple exponential time in the treewidth Further, our algorithm solves EnumSD with a pre-computation step that is linear in the input theory and triple exponential in the treewidth followed by a linear delay to output solutions. Finally, we take the exponential time hypothesis (ETH) into consideration and establish lower bounds of bounded treewidth algorithms for Cons .

M AX -C UT , E DGE D OMINATING S ET , G RAPH C OLORING , and H AMILTONIAN C YCLE on graphs of bounded clique-width have received significant attention as they can be formulated in MSO 2 (and, therefore, have linear-time algorithms on bounded treewidth graphs by the celebrated Courcelle’s theorem), but cannot be formulated in MSO 1 (which would have yielded linear-time algorithms on bounded clique-width graphs by a well-known theorem of Courcelle, Makowsky, and Rotics). Each of these problems can be solved in time g ( k ) n f ( k ) on graphs of clique-width k . Fomin et al. (2010) showed that the running times cannot be improved to g ( k ) n O (1) assuming W[1]≠FPT. However, this does not rule out non-trivial improvements to the exponent f ( k ) in the running times. In a follow-up paper, Fomin et al. (2014) improved the running times for E DGE D OMINATING S ET and M AX -C UT to n O ( k ) , and proved that these problems cannot be solved in time g ( k ) n o ( k ) unless ETH fails. Thus, prior to this work, E DGE D OMINATING S ET and M AX -C UT were known to have tight n Θ ( k ) algorithmic upper and lower bounds. In this article, we provide lower bounds for H AMILTONIAN C YCLE and G RAPH C OLORING . For H AMILTONIAN C YCLE , our lower bound g ( k ) n o ( k ) matches asymptotically the recent upper bound n O ( k ) due to Bergougnoux, Kanté, and Kwon (2017). As opposed to the asymptotically tight n Θ( k ) bounds for E DGE D OMINATING S ET , M AX -C UT , and H AMILTONIAN C YCLE , the G RAPH C OLORING problem has an upper bound of n O (2 k ) and a lower bound of merely n o (√ [4] k ) (implicit from the W[1]-hardness proof). In this article, we close the gap for G RAPH C OLORING by proving a lower bound of n 2 o ( k ) . This shows that G RAPH C OLORING behaves qualitatively different from the other three problems. To the best of our knowledge, G RAPH C OLORING is the first natural problem known to require exponential dependence on the parameter in the exponent of n .

Vertex deletion problems ask whether it is possible to delete at most $k$ vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years, the parameterized complexity of vertex deletion to a plethora of graph classes has been systematically researched. Here we present the first single-exponential fixed-parameter tractable algorithm for vertex deletion to distance-hereditary graphs, a well-studied graph class which is particularly important in the context of vertex deletion due to its connection to the graph parameter rank-width. We complement our result with matching asymptotic lower bounds based on the exponential time hypothesis. As an application of our algorithm, we show that a vertex deletion set to distance-hereditary graphs can be used as a parameter which allows single-exponential fixed-parameter tractable algorithms for classical NP-hard problems., 43 pages, 9 figures (revised journal version; an extended abstract appeared in the proceedings of MFCS 2016)

The problem of Distance Edge Labeling is a variant of Distance Vertex Labeling (also known as $L_{2,1}$ labeling) that has been studied for more than twenty years and has many applications, such as frequency assignment. The Distance Edge Labeling problem asks whether the edges of a given graph can be labeled such that the labels of adjacent edges differ by at least two and the labels of edges of distance two differ by at least one. Labels are chosen from the set $\{0,1,\dots,\lambda\}$ for $\lambda$ fixed. We present a full classification of its computational complexity - a dichotomy between the polynomially solvable cases and the remaining cases which are NP-complete. We characterise graphs with $\lambda \le 4$ which leads to a polynomial-time algorithm recognizing the class and we show NP-completeness for $\lambda \ge 5$ by several reductions from Monotone Not All Equal 3-SAT., Comment: 21 pages, IWOCA 2015

In the $$r$$ -Fix problem, we are given a graph G, a (non-proper) vertex-coloring $$c : V(G) \rightarrow [r]$$ , and a positive integer k. The goal is to decide whether a proper r-coloring $$c'$$ is obtainable from c by recoloring at most k vertices of G. Recently, Junosza-Szaniawski et al. (in: SOFSEM 2015: theory and practice of computer science, Springer, Berlin, 2015) asked whether the problem has a polynomial kernel parameterized by the number of recolorings k. In a full version of the manuscript, the authors together with Garnero and Montealegre, answered the question in the negative: for every $$r \ge 3$$ , the problem $$r$$ -Fix does not admit a polynomial kernel unless . Independently of their work, we give an alternative proof of the theorem. Furthermore, we study the complexity of $$r$$ -Swap, where the only difference from $$r$$ -Fix is that instead of k recolorings we have a budget of k color swaps. We show that for every $$r \ge 3$$ , the problem $$r$$ -Swap is -hard whereas $$r$$ -Fix is known to be FPT. Moreover, when r is part of the input, we observe both Fix and Swap are -hard parameterized by the treewidth of the input graph. We also study promise variants of the problems, where we are guaranteed that a proper r-coloring $$c'$$ is indeed obtainable from c by some finite number of swaps. For instance, we prove that for $$r=3$$ , the problems $$r$$ -Fix-Promise and $$r$$ -Swap-Promise are -hard for planar graphs. As a consequence of our reduction, the problems cannot be solved in $$2^{o(\sqrt{n})}$$ time unless the Exponential Time Hypothesis fails.

Given a graph G and an integer k , the k -B iclique problem asks whether G contains a complete bipartite subgraph with k vertices on each side. Whether there is an f ( k ) ċ | G | O (1) -time algorithm, solving k -B iclique for some computable function f has been a longstanding open problem. We show that k -B iclique is W[1] -hard, which implies that such an f ( k ) ċ | G | O (1) -time algorithm does not exist under the hypothesis W[1] ≠ FPT from parameterized complexity theory. To prove this result, we give a reduction which, for every n -vertex graph G and small integer k , constructs a bipartite graph H = ( L ⊍ R , E ) in time polynomial in n such that if G contains a clique with k vertices, then there are k ( k − 1)/2 vertices in L with n θ(1/ k ) common neighbors; otherwise, any k ( k − 1)/2 vertices in L have at most ( k +1)! common neighbors. An additional feature of this reduction is that it creates a gap on the right side of the biclique. Such a gap might have further applications in proving hardness of approximation results. Assuming a randomized version of Exponential Time Hypothesis, we establish an f ( k ) ċ | G | o (√ k ) -time lower bound for k - Biclique for any computable function f . Combining our result with the work of Bulatov and Marx [2014], we obtain a dichotomy classification of the parameterized complexity of cardinality constraint satisfaction problems.

For a graph class Π, the Π-V ertex D eletion problem has as input an undirected graph G = ( V , E ) and an integer k and asks whether there is a set of at most k vertices that can be deleted from G such that the resulting graph is a member of Π. By a classic result of Lewis and Yannakakis [17], Π-V ertex D eletion is NP-hard for all hereditary properties Π. We adapt the original NP-hardness construction to show that under the exponential time hypothesis (ETH), tight complexity results can be obtained. We show that Π-V ertex D eletion does not admit a 2 o ( n ) -time algorithm where n is the number of vertices in G . We also obtain a dichotomy for running time bounds that include the number m of edges in the input graph. On the one hand, if Π contains all edgeless graphs, then there is no 2 o ( n+m ) -time algorithm for Π-V ertex D eletion . On the other hand, if there is a fixed edgeless graph that is not contained in Π and containment in Π can be determined in 2 O ( n ) time or 2 o ( m ) time, then Π-V ertex D eletion can be solved in 2 O (√ m ) + O ( n ) or 2 o ( m ) + O ( n ) time, respectively. We also consider restrictions on the domain of the input graph G . For example, we obtain that Π-V ertex D eletion cannot be solved in 2 o (√ n ) time if G is planar and Π is hereditary and contains and excludes infinitely many planar graphs. Finally, we provide similar results for the problem variant where the deleted vertex set has to induce a connected graph.

In the S ubset F eedback V ertex S et (S ubset FVS) problem, the input is a graph G on n vertices and m edges, a subset of vertices T , referred to as terminals, and an integer k . The objective is to determine whether there exists a set of at most k vertices intersecting every cycle that contains a terminal. The study of parameterized algorithms for this generalization of the F eedback V ertex S et problem has received significant attention over the past few years. In fact, the parameterized complexity of this problem was open until 2011, when two groups independently showed that the problem is fixed parameter tractable. Using tools from graph minors,, Kawarabayashi and Kobayashi obtained an algorithm for S ubset FVS running in time O ( f ( k )ċ n 2 m ) [SODA 2012, JCTB 2012]. Independently, Cygan et al. [ICALP 2011, SIDMA 2013] designed an algorithm for S ubset FVS running in time 2 O ( k log k ) ċ n O (1) . More recently, Wahlström obtained the first single exponential time algorithm for S ubset FVS, running in time 4 k ċ n O (1) [SODA 2014]. While the 2 O ( k ) dependence on the parameter k is optimal under the Exponential Time Hypothesis, the dependence of this algorithm as well as those preceding it, on the input size is at least quadratic. In this article, we design the first linear time parameterized algorithms for S ubset FVS. More precisely, we obtain the following new algorithms for S ubset FVS. — A randomized algorithm for S ubset FVS running in time O (25.6 k ċ ( n + m )). — A deterministic algorithm for S ubset FVS running in time 2 O ( k log k ) ċ ( n + m ). Since it is known that assuming the Exponential Time Hypothesis, S ubset FVS cannot have an algorithm running in time 2 o ( k ) n O (1) , our first algorithm obtains the best possible asymptotic dependence on both the parameter as well as the input size. Both of our algorithms are based on “cut centrality,” in the sense that solution vertices are likely to show up in minimum size cuts between vertices sampled from carefully chosen distributions.

Due to the lack of unconditional polynomial lower bounds, it is now in fashion to prove conditional lower bounds in order to advance our understanding of the class P. The vast majority of these lower bounds are based on one of three famous hypotheses: the 3-SUM conjecture, the APSP conjecture, and the Strong Exponential Time Hypothesis. Only circumstantial evidence is known in support of these hypotheses, and no formal relationship between them is known. In hopes of obtaining "less conditional" and therefore more reliable lower bounds, we consider the conjecture that at least one of the above three hypotheses is true. We design novel reductions from 3-SUM, APSP, and CNF-SAT, and derive interesting consequences of this very plausible conjecture, including: Tight n3-o(1) lower bounds for purely-combinatorial problems about the triangles in unweighted graphs. New n1-o(1) lower bounds for the amortized update and query times of dynamic algorithms for single-source reachability, strongly connected components, and Max-Flow. New n1.5-o(1) lower bound for computing a set of n st-maximum-flow values in a directed graph with n nodes and ~O(n) edges. There is a hierarchy of natural graph problems on n nodes with complexity nc for c ∈ (2,3).Only slightly non-trivial consequences of this conjecture were known prior to our work. Along the way we also obtain new conditional lower bounds for the Single-Source-Max-Flow problem.

There is an extensive literature on the complexity of planning, but explicit bounds on time and space complexity are very rare. On the other hand, problems like the constraint satisfaction problem (CSP) have been thoroughly analysed in this respect. We provide a number of upper- and lower-bound results (the latter based on various complexity-theoretic assumptions such as the Exponential Time Hypothesis) for both satisficing and optimal planning. We show that many classes of planning instances exhibit a dichotomy: either they can be solved in polynomial time or they cannot be solved in subexponential time. In many cases, we can even prove closely matching upper and lower bounds. Our results also indicate, analogously to CSPs, the existence of sharp phase transitions. We finally study and discuss the trade-off between time and space. In particular, we show that depth-first search may sometimes be a viable option for planning under severe space constraints.

We study the complexity of graph problems succinctly encoded by bounded depth circuits and the existence of upward translation theorems for these models. While almost all succinct encodings have an upward translation theorem for some type of reduction, we prove that such theorems for CNF- and DNF-encoded graphs and for the most studied reductions do not exist. In contrast, we show that there are upward translation theorems for AC0 circuits of depth at least 3. This implies that the complexity of the succinct versions of problems complete for NP (under quantifier-free reductions), encoded by such circuits, have an exponential blow-up. We adapt these results to problems on explicitly given graphs with the same structural properties as graphs encoded by bounded depth circuits. We define a graph class hierarchy $\mathcal {I}^{k}$ which consists of at most k alternating unions and intersections of edge-sets in $\mathcal {I}^{0}$ , a class which only consists of single bicliques. We show that the complexity of every NP-complete problem (under quantifier-free reductions) collapses to the second level: on graphs in $\mathcal {I}^{2}$ the problem is already NP-complete. Finally, we show that by restricting $\mathcal {I}^{2}$ to use only sub-logarithmic many intersections we get graphs for which Dominating Set is not NP-complete unless the Exponential Time Hypothesis is false. In contrast, a degree of O(log n) is enough for NP-completeness. Therefore, Dominating Set on $\mathcal {I}^{2}$ graphs with intersection-degree O(log δ (n)) has either a spontaneous transition from P (for all δ < 1) to NP-complete (for δ = 1), or is NP-intermediate on the restricted graph class (for some δ < 1).

The propositional model counting problem (#SAT) is known to be fixed-parameter-tractable (FPT) when parameterized by the width k of a given tree decomposition of the incidence graph. The running time of the fastest known FPT algorithm contains the exponential factor of \(4^k\). We improve this factor to \(2^k\) by utilizing fast algorithms for computing the zeta transform and covering product of functions representing partial model counts, thereby achieving the same running time as FPT algorithms that are parameterized by the less general treewidth of the primal graph. Our new algorithm is asymptotically optimal unless the Strong Exponential Time Hypothesis (SETH) fails.

In this chapter we continue a story told from in Daniel Marx’s Chapter and present three examples of surprising use of treewidth. In all cases, we present a state-of-the-art and provably optimal (assuming the Exponential Time Hypothesis) algorithm exploiting a sublinear bound on the treewidth of an auxiliary graph taken out of the blue.

Given a graph property $\Phi$, the problem $\#\mathsf{IndSub}(\Phi)$ asks, on input a graph $G$ and a positive integer $k$, to compute the number of induced subgraphs of size $k$ in $G$ that satisfy $\Phi$. The search for explicit criteria on $\Phi$ ensuring that $\#\mathsf{IndSub}(\Phi)$ is hard was initiated by Jerrum and Meeks [J. Comput. Syst. Sci. 15] and is part of the major line of research on counting small patterns in graphs. However, apart from an implicit result due to Curticapean, Dell and Marx [STOC 17] proving that a full classification into "easy" and "hard" properties is possible and some partial results on edge-monotone properties due to Meeks [Discret. Appl. Math. 16] and D\"orfler et al. [MFCS 19], not much is known. In this work, we fully answer and explicitly classify the case of monotone, that is subgraph-closed, properties: We show that for any non-trivial monotone property $\Phi$, the problem $\#\mathsf{IndSub}(\Phi)$ cannot be solved in time $f(k)\cdot |V(G)|^{o(k/ {\log^{1/2}(k)})}$ for any function $f$, unless the Exponential Time Hypothesis fails. By this, we establish that any significant improvement over the brute-force approach is unlikely; in the language of parameterized complexity, we also obtain a $\#\mathsf{W}[1]$-completeness result., Comment: 33 pages, 2 figures

Given a graph class \(\mathcal {H}\), the task of the \(\mathcal {H}\)-Square Root problem is to decide, whether an input graph G has a square root H that belongs to \(\mathcal {H}\). We are interested in the parameterized complexity of the problem for classes \(\mathcal {H}\) that are composed by the graphs at vertex deletion distance at most k from graphs of maximum degree at most one, that is, we are looking for a square root H such that there is a modulator S of size k such that \(H-S\) is the disjoint union of isolated vertices and disjoint edges. We show that different variants of the problems with constraints on the number of isolated vertices and edges in \(H-S\) are FPT when parameterized by k by providing algorithms with running time \(2^{2^{\mathcal {O}(k)}}\cdot n^{\mathcal {O}(1)}\). We further show that the running time of our algorithms is asymptotically optimal and it is unlikely that the double-exponential dependence on k could be avoided. In particular, we prove that the VC- \(k\) Root problem, that asks whether an input graph has a square root with vertex cover of size at most k, cannot be solved in time \(2^{2^{o(k)}}\cdot n^{\mathcal {O}(1)}\) unless the Exponential Time Hypothesis fails. Moreover, we point out that VC- \(k\) Root parameterized by k does not admit a subexponential kernel unless P=N P.

For a finite collection of graphs ${\cal F}$, the ${\cal F}$-M-DELETION problem consists in, given a graph $G$ and an integer $k$, deciding whether there exists $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as a minor. We are interested in the parameterized complexity of ${\cal F}$-M-DELETION when the parameter is the treewidth of $G$, denoted by $tw$. Our objective is to determine, for a fixed ${\cal F}$, the smallest function $f_{{\cal F}}$ such that {${\cal F}$-M-DELETION can be solved in time $f_{{\cal F}}(tw) \cdot n^{O(1)}$ on $n$-vertex graphs. We prove that $f_{{\cal F}}(tw) = 2^{2^{O(tw \cdot\log tw)}}$ for every collection ${\cal F}$, that $f_{{\cal F}}(tw) = 2^{O(tw \cdot\log tw)}$ if ${\cal F}$ contains a planar graph, and that $f_{{\cal F}}(tw) = 2^{O(tw)}$ if in addition the input graph $G$ is planar or embedded in a surface. We also consider the version of the problem where the graphs in ${\cal F}$ are forbidden as topological minors, called ${\cal F}$-TM-DELETION. We prove similar results for this problem, except that in the last two algorithms, instead of requiring ${\cal F}$ to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic., Comment: 36 pages

We prove that the Hadwiger number of an $n$-vertex graph $G$ (the maximum size of a clique minor in $G$) cannot be computed in time $n^{o(n)}$, unless the Exponential Time Hypothesis (ETH) fails. This resolves a well-known open question in the area of exact exponential algorithms. The technique developed for resolving the Hadwiger number problem has a wider applicability. We use it to rule out the existence of $n^{o(n)}$-time algorithms (up to ETH) for a large class of computational problems concerning edge contractions in graphs., Comment: Accepted to ICALP 2020

We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable (FPT) algorithms....

Research on the constraint satisfaction problem (CSP) is an active field both in theory and practice. An extension of CSP even considers universal and existential quantification of domain variables, known as QCSP, for which also solvers exist. The number of alternations between existential and universal quantifications is usually called quantifier rank. While QCSP is PSPACE-complete for bounded domain size, one can consider additional structural restrictions that make the problem tractable, for example, bounded treewidth. Chen [14] showed that one can solve QCSP instances of size n, quantifier rank \(\ell \), bounded treewidth k, and bounded domain size d in \(\text {poly}(n)\cdot \text {tower}(\ell -1,d^k)\), where tower are exponentials of height \(\ell -1\) with \(d^k\) on top. We follow up on Chen’s result and develop a treewidth-aware quantifier elimination technique that reduces the rank without an exponential blow-up in the instance size at the cost of exponentially increasing the treewidth. With this reduction at hand we show that one cannot significantly improve the blow-up of the treewidth assuming the exponential time hypothesis (ETH). Further, we lift a recently introduced technique for treewidth-decreasing quantifier expansion from the Boolean domain to QCSP.

For a function $\mathsf{K} : \mathbb{R}^{d} \times \mathbb{R}^{d} \to \mathbb{R}_{\geq 0}$, and a set $P = \{ x_1, \ldots, x_n\} \subset \mathbb{R}^d$ of $n$ points, the $\mathsf{K}$ graph $G_P$ of $P$ is the complete graph on $n$ nodes where the weight between nodes $i$ and $j$ is given by $\mathsf{K}(x_i, x_j)$. In this paper, we initiate the study of when efficient spectral graph theory is possible on these graphs. We investigate whether or not it is possible to solve the following problems in $n^{1+o(1)}$ time for a $\mathsf{K}$-graph $G_P$ when $d < n^{o(1)}$: $\bullet$ Multiply a given vector by the adjacency matrix or Laplacian matrix of $G_P$ $\bullet$ Find a spectral sparsifier of $G_P$ $\bullet$ Solve a Laplacian system in $G_P$'s Laplacian matrix For each of these problems, we consider all functions of the form $\mathsf{K}(u,v) = f(\|u-v\|_2^2)$ for a function $f:\mathbb{R} \rightarrow \mathbb{R}$. We provide algorithms and comparable hardness results for many such $\mathsf{K}$, including the Gaussian kernel, Neural tangent kernels, and more. For example, in dimension $d = \Omega(\log n)$, we show that there is a parameter associated with the function $f$ for which low parameter values imply $n^{1+o(1)}$ time algorithms for all three of these problems and high parameter values imply the nonexistence of subquadratic time algorithms assuming Strong Exponential Time Hypothesis ($\mathsf{SETH}$), given natural assumptions on $f$. As part of our results, we also show that the exponential dependence on the dimension $d$ in the celebrated fast multipole method of Greengard and Rokhlin cannot be improved, assuming $\mathsf{SETH}$, for a broad class of functions $f$. To the best of our knowledge, this is the first formal limitation proven about fast multipole methods., Comment: FOCS 2020

For a fixed graph $H$, the $H$-IS-Deletion problem asks, given a graph $G$, for the minimum size of a set $S \subseteq V(G)$ such that $G\setminus S$ does not contain $H$ as an induced subgraph. Motivated by previous work about hitting (topological) minors and subgraphs on bounded treewidth graphs, we are interested in determining, for a fixed graph $H$, the smallest function $f_H(t)$ such that $H$-IS-Deletion can be solved in time $f_H(t) \cdot n^{O(1)}$ assuming the Exponential Time Hypothesis (ETH), where $t$ and $n$ denote the treewidth and the number of vertices of the input graph, respectively. We show that $f_H(t) = 2^{O(t^{h-2})}$ for every graph $H$ on $h \geq 3$ vertices, and that $f_H(t) = 2^{O(t)}$ if $H$ is a clique or an independent set. We present a number of lower bounds by generalizing a reduction of Cygan et al. [MFCS 2014] for the subgraph version. In particular, we show that when $H$ deviates slightly from a clique, the function $f_H(t)$ suffers a sharp jump: if $H$ is obtained from a clique of size $h$ by removing one edge, then $f_H(t) = 2^{\Theta(t^{h-2})}$. We also show that $f_H(t) = 2^{\Omega(t^{h})}$ when $H=K_{h,h}$, and this reduction answers an open question of Mi. Pilipczuk [MFCS 2011] about the function $f_{C_4}(t)$ for the subgraph version. Motivated by Cygan et al. [MFCS 2014], we also consider the colorful variant of the problem, where each vertex of $G$ is colored with some color from $V(H)$ and we require to hit only induced copies of $H$ with matching colors. In this case, we determine, under the ETH, the function $f_H(t)$ for every connected graph $H$ on $h$ vertices: if $h\leq 2$ the problem can be solved in polynomial time; if $h\geq 3$, $f_H(t) = 2^{\Theta(t)}$ if $H$ is a clique, and $f_H(t) = 2^{\Theta(t^{h-2})}$ otherwise., Comment: 26 pages, 3 figures

In the Subset Sum problem we are given a set of $n$ positive integers $X$ and a target $t$ and are asked whether some subset of $X$ sums to $t$. Natural parameters for this problem that have been studied in the literature are $n$ and $t$ as well as the maximum input number $\rm{mx}_X$ and the sum of all input numbers $\Sigma_X$. In this paper we study the dense case of Subset Sum, where all these parameters are polynomial in $n$. In this regime, standard pseudo-polynomial algorithms solve Subset Sum in polynomial time $n^{O(1)}$. Our main question is: When can dense Subset Sum be solved in near-linear time $\tilde{O}(n)$? We provide an essentially complete dichotomy by designing improved algorithms and proving conditional lower bounds, thereby determining essentially all settings of the parameters $n,t,\rm{mx}_X,\Sigma_X$ for which dense Subset Sum is in time $\tilde{O}(n)$. For notational convenience we assume without loss of generality that $t \ge \rm{mx}_X$ (as larger numbers can be ignored) and $t \le \Sigma_X/2$ (using symmetry). Then our dichotomy reads as follows: - By reviving and improving an additive-combinatorics-based approach by Galil and Margalit [SICOMP'91], we show that Subset Sum is in near-linear time $\tilde{O}(n)$ if $t \gg \rm{mx}_X \Sigma_X/n^2$. - We prove a matching conditional lower bound: If Subset Sum is in near-linear time for any setting with $t \ll \rm{mx}_X \Sigma_X/n^2$, then the Strong Exponential Time Hypothesis and the Strong k-Sum Hypothesis fail. We also generalize our algorithm from sets to multi-sets, albeit with non-matching upper and lower bounds., Comment: full version of SODA'21 paper, 36 pages

Elastic-degenerate text provides a novel and effective method for modeling collections of text that have local variations. Due to its applicability in pan-genomics, an index for an elastic-degenerate text which can efficiently report the occurrences of a given query pattern is desirable. This paper attempts to dash our hopes for such an index, one that is deterministic and has good worst-case query time. We do so by providing conditional lower bounds based on the Orthogonal Vectors Hypothesis (OVH) (and hence the Strong Exponential Time Hypothesis). We show that, even with arbitrary polynomial preprocessing time, an index for an elastic-degenerate text with n degenerate letters that can perform queries on a pattern of length m in time Open image in new window for constants \(\alpha \) and \(\beta \) where Open image in new window or Open image in new window would violate OVH. Additionally, we provide an elastic-degenerate text index with query time Open image in new window, which is independent of the size N (distinct from its length) of the elastic-degenerate text. Finally, we investigate the hardness of matching elastic-degenerate text to elastic-degenerate text.

An integer program (IP) is a problem of the form $\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}$, where $A \in \Z^{m \times n}$, $b \in \Z^m$, $l,u \in \Z^n$, and $f: \Z^n \rightarrow \Z$ is a separable convex objective function. The problem of finding an optimal solution for an integer program is known as integer programming. Integer programming is NP-hard in general, though several algorithms exist: Lenstra provided an algorithm that is polynomial if the dimension $n$ is fixed. For variable dimension, the best known algorithm depends linearly on $n$, and exponentially on the number of equalities as well as the largest absolute value of an entry in the matrix $A$. The first part of this thesis considers integer programming for variable dimensions and sparse matrices. We measure the sparsity of a matrix by the tree-depth of the dual graph of $A$. A typical example for these integer programs are $N$-fold IPs, used for scheduling and social choice problems. We obtain the currently fastest fixed-parameter tractable algorithm with parameters tree-depth and the largest absolute value of the entries in $A$. The running time we achieve is near-linear in the dimension. With a slightly worse running time, we are able to show that $N$-fold integer programs of constant block size can be solved in strongly polynomial time. Assuming the exponential time hypothesis, we complement these results with a lower bound on the parameter dependency that almost matches the parameter dependency of the running time. As a consequence, we provide the currently strongest lower bound for $N$-fold integer programs. Another problem closely related to integer programming is the closest vector problem. A lattice is a discrete additive subgroup of $\R^n$. The closest vector problem (CVP) asks for a lattice point closest to a given target vector. An important tool for solving the closest vector problem is the Voronoi cell $\vc$ of a lattice $\Lambda \subseteq \R^n$, which is the set of all points for which $0$ is a closest lattice point. It is a polytope whose facets are induced by a set of lattice vectors, the Voronoi relevant vectors. A generic lattice has exponentially many Voronoi relevant vectors, leading to exponential space for certain CVP algorithms. In the second part of this thesis, we introduce the notion of a $c$-compact lattice basis $B \in \R^{n \times n}$ that facilitates to represent the Voronoi relevant vectors with coefficients bounded by $c$. Such a basis allows to reduce the space requirement of Micciancio's \& Voulgaris' algorithm for the closest vector problem from exponential to polynomial, while the running time becomes exponential in $c$. We show that for every lattice an $n^2$-compact basis exists, but there are lattices for which we cannot choose $c \in o (n)$. If the Voronoi cell is a zonotope, we can choose $c=1$, providing a single-exponential time and polynomial space algorithm for CVP, assuming a $1$-compact basis is known. Deciding whether a given lattice has a certain structure that helps to solve the closest vector problem more efficiently is a reappearing and non-trivial problem. The third part of this thesis is concerned with the specific structure of having an orthonormal basis. We show that this problem belongs to NP $\cap$ co-NP. Moreover, it can be reduced to solving a single closest vector problem. We also show that if a separation oracle for the Voronoi cell is provided, CVP is solvable in polynomial time.

The problem of deciding the validity (QSat) of quantified Boolean formulas (QBF) is a vivid research area in both theory and practice. In the field of parameterized algorithmics, the well-studied graph measure treewidth turned out to be a successful parameter. A well-known result by Chen [9] is that QSat when parameterized by the treewidth of the primal graph and the quantifier rank of the input formula is fixed-parameter tractable. More precisely, the runtime of such an algorithm is polynomial in the formula size and exponential in the treewidth, where the exponential function in the treewidth is a tower, whose height is the quantifier rank. A natural question is whether one can significantly improve these results and decrease the tower while assuming the Exponential Time Hypothesis (ETH). In the last years, there has been a growing interest in the quest of establishing lower bounds under ETH, showing mostly problem-specific lower bounds up to the third level of the polynomial hierarchy. Still, an important question is to settle this as general as possible and to cover the whole polynomial hierarchy. In this work, we show lower bounds based on the ETH for arbitrary QBFs parameterized by treewidth and quantifier rank. More formally, we establish lower bounds for QSat and treewidth, namely, that under ETH there cannot be an algorithm that solves QSat of quantifier rank i in runtime significantly better than i-fold exponential in the treewidth and polynomial in the input size. In doing so, we provide a reduction technique to compress treewidth that encodes dynamic programming on arbitrary tree decompositions. Further, we describe a general methodology for a more finegrained analysis of problems parameterized by treewidth that are at higher levels of the polynomial hierarchy. Finally, we illustrate the usefulness of our results by discussing various applications of our results to problems that are located higher on the polynomial hierarchy, in particular, various problems from the literature such as projected model counting problems.

In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and a parameter $\alpha>1$, and the goal is to design an $\alpha$-approximation algorithm with the fastest possible running time. We show the following results: - An $r$-approximation for maximum independent set in $O^*(\exp(\tilde O(n/r \log^2 r+r\log^2r)))$ time, - An $r$-approximation for chromatic number in $O^*(\exp(\tilde{O}(n/r \log r+r\log^2r)))$ time, - A $(2-1/r)$-approximation for minimum vertex cover in $O^*(\exp(n/r^{\Omega(r)}))$ time, and - A $(k-1/r)$-approximation for minimum $k$-hypergraph vertex cover in $O^*(\exp(n/(kr)^{\Omega(kr)}))$ time. (Throughout, $\tilde O$ and $O^*$ omit $\mathrm{polyloglog}(r)$ and factors polynomial in the input size, respectively.) The best known time bounds for all problems were $O^*(2^{n/r})$ [Bourgeois et al. 2009, 2011 & Cygan et al. 2008]. For maximum independent set and chromatic number, these bounds were complemented by $\exp(n^{1-o(1)}/r^{1+o(1)})$ lower bounds (under the Exponential Time Hypothesis (ETH)) [Chalermsook et al., 2013 & Laekhanukit, 2014 (Ph.D. Thesis)]. Our results show that the naturally-looking $O^*(2^{n/r})$ bounds are not tight for all these problems. The key to these algorithmic results is a sparsification procedure, allowing the use of better approximation algorithms for bounded degree graphs. For obtaining the first two results, we introduce a new randomized branching rule. Finally, we show a connection between PCP parameters and exponential-time approximation algorithms. This connection together with our independent set algorithm refute the possibility to overly reduce the size of Chan's PCP [Chan, 2016]. It also implies that a (significant) improvement over our result will refute the gap-ETH conjecture [Dinur 2016 & Manurangsi and Raghavendra, 2016]., Comment: 13 pages

We introduce and investigate the approximability of the maximum binary tree problem (MBT) in directed and undirected graphs. The goal in MBT is to find a maximum-sized binary tree in a given graph. MBT is a natural variant of the well-studied longest path problem, since both can be viewed as finding a maximum-sized tree of bounded degree in a given graph. The connection to longest path motivates the study of MBT in directed acyclic graphs (DAGs), since the longest path problem is solvable efficiently in DAGs. In contrast, we show that MBT in DAGs is in fact hard: it has no efficient $\exp(-O(\log n/ \log \log n))$-approximation algorithm under the exponential time hypothesis, where $n$ is the number of vertices in the input graph. In undirected graphs, we show that MBT has no efficient $\exp(-O(\log^{0.63}{n}))$-approximation under the exponential time hypothesis. Our inapproximability results rely on self-improving reductions and structural properties of binary trees. We also show constant-factor inapproximability assuming $\text{P}\neq \text{NP}$. In addition to inapproximability results, we present algorithmic results along two different flavors: (1) We design a randomized algorithm to verify if a given directed graph on $n$ vertices contains a binary tree of size $k$ in $2^k \text{poly}(n)$ time. (2) Motivated by the longest heapable subsequence problem, introduced by Byers, Heeringa, Mitzenmacher, and Zervas (ANALCO 2011), which is equivalent to MBT in permutation DAGs, we design efficient algorithms for MBT in bipartite permutation graphs., to be published in European Symposium on Algorithms 2020

In the Steiner Orientation problem, the input is a mixed graph G (it has both directed and undirected edges) and a set of k terminal pairs $$\mathscr {T}$$ . The question is whether we can orient the undirected edges in a way such that there is a directed $$s\leadsto t$$ path for each terminal pair $$(s,t)\in \mathscr {T}$$ . Arkin and Hassin [DAM’02] showed that the Steiner Orientation problem is NP-complete. They also gave a polynomial time algorithm for the special case when $$k=2$$ . From the viewpoint of exact algorithms, Cygan et al. [ESA’12, SIDMA’13] designed an XP algorithm running in $$n^{O(k)}$$ time for all $$k\ge 1$$ . Pilipczuk and Wahlstrom [SODA’16, TOCT’18] showed that the Steiner Orientation problem is W[1]-hard parameterized by k. As a byproduct of their reduction, they were able to show that under the Exponential Time Hypothesis (ETH) of Impagliazzo, Paturi and Zane [JCSS’01] the Steiner Orientation problem does not admit an $$f(k)\cdot n^{o(k/\log k)}$$ algorithm for any computable function f. In this paper, we give a short and easy proof that the $$n^{O(k)}$$ algorithm of Cygan et al. is asymptotically optimal, even if the input graph is planar. Formally, we show that the Planar Steiner Orientation problem is W[1]-hard parameterized by the number k of terminal pairs, and, under ETH, cannot be solved in $$f(k)\cdot n^{o(k)}$$ time for any computable function f. Moreover, under a stronger hypothesis called Gap-ETH of Dinur [ECCC’16] and Manurangsi and Raghavendra [ICALP’17], we are able to show that there is no constant $$\vartheta >0$$ such that Planar Steiner Orientation admits an $$(\frac{19}{20}+\vartheta )$$ -approximation in FPT time, i.e., no $$f(k)\cdot n^{o(k)}$$ time algorithm can distinguish between the case when all k pairs are satisfiable versus the case when less than $$k \cdot (\frac{19}{20}+\vartheta )$$ pairs are satisfiable. To the best of our knowledge, this is the first FPT inapproximability result on planar graphs.