Danny Hermelin

TCS Journal 2024 Journal Article

Approximating sparse quadratic programs

• Danny Hermelin
• Leon Kellerhals
• Rolf Niedermeier
• Rami Pugatch

Given a matrix A ∈ R n × n, we consider the problem of maximizing x T A x subject to the constraint x ∈ { − 1, 1 } n. This problem, called MaxQP by Charikar and Wirth [FOCS'04], generalizes MaxCut and has natural applications in data clustering and in the study of disordered magnetic phases of matter. Charikar and Wirth showed that the problem admits an Ω ( 1 / lg ⁡ n ) approximation via semidefinite programming, and Alon, Makarychev, Makarychev, and Naor [STOC'05] showed that the same approach yields an Ω ( 1 ) approximation when A corresponds to a graph of bounded chromatic number. Both these results rely on solving the semidefinite relaxation of MaxQP, whose currently best running time is O ˜ ( n 1. 5 ⋅ min ⁡ { N, n 1. 5 } ), where N is the number of nonzero entries in A and O ˜ ignores polylogarithmic factors. In this sequel, we abandon the semidefinite approach and design purely combinatorial approximation algorithms for special cases of MaxQP where A is sparse (i. e. , has O ( n ) nonzero entries). Our algorithms are superior to the semidefinite approach in terms of running time, yet are still competitive in terms of their approximation guarantees. More specifically, we show that: • MaxQP admits a ( 1 / 2 Δ ) -approximation in O ( n lg ⁡ n ) time, where Δ = O ( 1 ) is the maximum degree of the corresponding graph. • Unit MaxQP, where A ∈ { − 1, 0, 1 } n × n, admits a ( 1 / 2 d ) -approximation in O ( n ) time when the corresponding graph is d-degenerate, and a ( 1 / 3 δ ) -approximation in O ( n 1. 5 ) time when the corresponding graph has δn edges for δ = O ( 1 ). • MaxQP admits a ( 1 − ε ) -approximation in O ( n ) time when the corresponding graph and each of its minors have bounded local treewidth. • Unit MaxQP admits a ( 1 − ε ) -approximation in O ( n 2 ) time for H-minor free graphs.

TCS Journal 2023 Journal Article

Temporal interval cliques and independent sets

• Danny Hermelin
• Yuval Itzhaki
• Hendrik Molter
• Rolf Niedermeier

Temporal graphs have been recently introduced to model changes in a given network that occur throughout a fixed period of time. The Temporal Δ Clique problem, which generalizes the well known Clique problem to temporal graphs, has been studied in the context of finding nodes of interest in dynamic networks [TCS '16]. We introduce the Temporal Δ Independent Set problem, a temporal generalization of Independent Set. This problem is e. g. motivated in the context of finding conflict-free schedules for maximum subsets of tasks, that have certain (time-varying) constraints within a given time period. We are specifically interested in the case where each task needs to be performed in a certain time-interval on each day and two tasks are in conflict on a certain day if their time-intervals on that day overlap. This leads us to consider both problems on the restricted class of temporal unit interval graphs, i. e. , temporal graphs where each layer is a unit interval graph. We present several hardness results as well as positive results. On the algorithmic side, we provide constant-factor approximation algorithms for instances of both problems where τ, the total number of time steps (layers) of the temporal graph, and Δ, a parameter that allows us to model conflict tolerance, are constants. We develop an exact FPT algorithm for Temporal Δ Clique with respect to parameter τ + k. Finally, we use the notion of order preservation for temporal unit interval graphs that, informally, requires the intervals of every layer to obey a common ordering. For both problems, we provide an FPT algorithm parameterized by the size of minimum vertex deletion set to order preservation.

EAAI Journal 2021 Journal Article

Collective multi agent deployment for wireless sensor network maintenance

• Harel Yedidsion
• Danny Hermelin
• Michael Segal

In this paper, we study the problem of wireless sensor network (WSN) maintenance using a team of physical autonomous mobile agents. The agents are deployed in the area of the WSN in such a way that would minimize the time it takes them to reach a failed sensor and repair it. The team must constantly optimize its collective deployment to account for occupied agents. The objective is to define the optimal deployment and task allocation strategy, that minimize the solution cost. The solution cost is a linear combination of the weighted sensors’ downtime, the agents’ traveling distance, and penalties incurred due to unrepaired sensors within a certain time limit. Our proposed solution algorithms are inspired by research in the field of computational geometry and the design of our algorithms is based on state of the art approximation algorithms for the classical problem of facility location. We empirically compare and analyze the performance of several proposed algorithms. The sensitivity of the algorithms’ performance to the following parameters is analyzed: agents to sensors ratio, sensors’ sparsity, frequency and distribution of failures, repair duration, repair capacity, and communication limitations. Our results demonstrate that: (i) cooperation enhances the team’s performance by orders of magnitude, (ii) k -Median based deployment algorithm provides up to 30% improvement in downtime, (iii) k -Center based deployment incurs 10% fewest penalties, and (iv) k -Centroid based deployment is most efficient in terms of minimizing the overall costs, with up to 21% lower cost than the next best algorithm.

SODA Conference 2021 Conference Paper

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles

• Jiehua Chen 0001
• Wojciech Czerwinski
• Yann Disser
• Andreas Emil Feldmann
• Danny Hermelin
• Wojciech Nadara
• Marcin Pilipczuk
• Michal Pilipczuk

We present a data structure that in a dynamic graph of treedepth at most d, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case update time, which matches the best known parameter dependency in the running time of a static fpt algorithm for computing the treedepth of a graph. This improves a result of Dvořák et al. [ESA 2014], who for the same problem achieved update time f ( d ) for some non-elementary (i. e. tower-exponential) function f. As a by-product, we improve known upper bounds on the sizes of minimal obstructions for having treedepth d from doubly-exponential in d to d O ( d ). As applications, we design new fully dynamic parameterized data structures for detecting long paths and cycles in general graphs. More precisely, for a fixed parameter k and a dynamic graph G, modified over time by edge insertions and deletions, our data structures maintain answers to the following queries: Does G contain a simple path on k vertices? Does G contain a simple cycle on at least k vertices? In the first case, the data structure achieves amortized update time. In the second case, the amortized update time is. In both cases we assume access to a dictionary on the edges of G.

SODA Conference 2019 Conference Paper

SETH-Based Lower Bounds for Subset Sum and Bicriteria Path

• Amir Abboud
• Karl Bringmann
• Danny Hermelin
• Dvir Shabtay

S ubset S um and k -SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. An important open problem in this area is to base the hardness of one of these problems on the other. Our main result is a tight reduction from k -SAT to S ubset S um on dense instances, proving that Bellman's 1962 pseudo-polynomial O* ( T )-time algorithm for S ubset S um on n numbers and target T cannot be improved to time T 1– ε · 2 o ( n ) for any ε > 0, unless the Strong Exponential Time Hypothesis (SETH) fails. As a corollary, we prove a “Direct-OR” theorem for S ubset S um under SETH, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of N given instances of S ubset S um is a YES instance requires time ( NT ) 1– o (1). As an application of this corollary, we prove a tight SETH-based lower bound for the classical B icriteria s, t -PATH problem, which is extensively studied in Operations Research. We separate its complexity from that of S ubset S um: On graphs with m edges and edge lengths bounded by L, we show that the O ( Lm ) pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to Õ ( L + m ), in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017).

MFCS Conference 2017 Conference Paper

Lossy Kernels for Hitting Subgraphs

• Eduard Eiben
• Danny Hermelin
• M. S. Ramanujan 0001

In this paper, we study the Connected H-hitting Set and Dominating Set problems from the perspective of approximate kernelization, a framework recently introduced by Lokshtanov et al. [STOC 2017]. For the Connected H-hitting set problem, we obtain an \alpha-approximate kernel for every \alpha>1 and complement it with a lower bound for the natural weighted version. We then perform a refined analysis of the tradeoff between the approximation factor and kernel size for the Dominating Set problem on d-degenerate graphs and provide an interpolation of approximate kernels between the known d^2-approximate kernel of constant size and 1-approximate kernel of size k^{O(d^2)}.

TCS Journal 2016 Journal Article

Parameterized complexity of critical node cuts

• Danny Hermelin
• Moshe Kaspi
• Christian Komusiewicz
• Barak Navon

We consider the following graph cut problem called Critical Node Cut (CNC): Given a graph G on n vertices, and two positive integers k and x, determine whether G has a set of k vertices whose removal leaves G with at most x connected pairs of vertices. We analyze this problem in the framework of parameterized complexity. That is, we are interested in whether or not this problem is solvable in f ( κ ) ⋅ n O ( 1 ) time (i. e. , whether or not it is fixed-parameter tractable), for various natural parameters κ. We consider four such parameters: • The size k of the required cut. • The upper bound x on the number of remaining connected pairs. • The lower bound y on the number of connected pairs to be removed. • The treewidth w of G. We determine whether or not CNC is fixed-parameter tractable for each of these parameters. We determine this also for all possible aggregations of these four parameters, apart from w + k. Moreover, we also determine whether or not CNC admits a polynomial kernel for all these parameterizations. That is, whether or not there is an algorithm that reduces each instance of CNC in polynomial time to an equivalent instance of size κ O ( 1 ), where κ is the given parameter.

TCS Journal 2015 Journal Article

On the average-case complexity of parameterized clique

• Nikolaos Fountoulakis
• Tobias Friedrich
• Danny Hermelin

The k -Clique problem is a fundamental combinatorial problem that plays a prominent role in classical as well as in parameterized complexity theory. It is among the most well-known NP-complete and W[1]-complete problems. Moreover, its average-case complexity analysis has created a long thread of research already since the 1970s. Here, we continue this line of research by studying the dependence of the average-case complexity of the k -Clique problem on the parameter k. To this end, we define two natural parameterized analogs of efficient average-case algorithms. We then show that k -Clique admits both analogues for Erdős–Rényi random graphs of arbitrary density. We also show that k -Clique is unlikely to admit either of these analogs for some specific computable input distribution.

TCS Journal 2015 Journal Article

Parameterized complexity analysis for the Closest String with Wildcards problem

• Danny Hermelin
• Liat Rozenberg

The Closest String problem asks to find a string s which is not too far from each string in a set of m input strings, where the distance is taken as the Hamming distance. This well-studied problem has various applications in computational biology and drug design. In this paper, we introduce a new variant of Closest String where the input strings can contain wildcards that can match any letter in the alphabet, and the goal is to find a solution string without wildcards. We call this problem the Closest String with Wildcards problem, and we analyze it in the framework of parameterized complexity. Our study determines for each natural parameterization whether this parameterization yields a fixed-parameter algorithm, or whether such an algorithm is highly unlikely to exist.

TCS Journal 2014 Journal Article

Local search for string problems: Brute-force is essentially optimal

• Jiong Guo
• Danny Hermelin
• Christian Komusiewicz

We address the problem of whether the brute-force procedure for the local improvement step in a local search algorithm can substantially be improved when applied to classical NP-hard string problems. We examine four of the more prominent problems in this domain: Closest String, Longest Common Subsequence, Shortest Common Supersequence, and Shortest Common Superstring. Herein, we consider arguably the most fundamental string distance measure, namely the Hamming distance, which has been applied in practical local search implementations for string problems. Our results indicate that for all four problems, the brute-force algorithm cannot be considerably improved.

TCS Journal 2013 Journal Article

Constraint satisfaction problems: Convexity makes AllDifferent constraints tractable

• Michael Fellows
• Tobias Friedrich
• Danny Hermelin
• Nina Narodytska
• Frances Rosamond

We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations, and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable even though it is provably intractable in general. Interestingly, the convexity of constraints is the key property in achieving fixed parameter tractability, while the convexity of domains does not usually make the problem easier.

I&C Journal 2012 Journal Article

Mod/Resc Parsimony Inference: Theory and application

• Igor Nor
• Danny Hermelin
• Sylvain Charlat
• Jan Engelstadter
• Max Reuter
• Olivier Duron
• Marie-France Sagot

We address in this paper a new computational biology problem that aims at understanding a mechanism that could potentially be used to genetically manipulate natural insect populations infected by inherited, intra-cellular parasitic bacteria. In this problem, that we denote by Mod/Resc Parsimony Inference, we are given a boolean matrix and the goal is to find two other boolean matrices with a minimum number of columns such that an appropriately defined operation on these matrices gives back the input. We show that this is formally equivalent to the Biclique Edge Cover for Bipartite Graphs problem and derive some complexity results for our problem using this equivalence. We provide a new, fixed-parameter tractability approach for solving both problems that slightly improves upon a previously published algorithm for the Biclique Edge Cover for Bipartite Graphs. Finally, we present experimental results applying some of our techniques to a real-life dataset.

SODA Conference 2012 Conference Paper

Weak compositions and their applications to polynomial lower bounds for kernelization

• Danny Hermelin
• Xi Wu 0001

In this paper we use the notion of weak compositions to obtain polynomial kernelization lower-bounds for several natural parameterized problems. Let d ≥ 2 be some constant and let L 1, L 2 ⊆ {0, 1}* × ℕ be two parameterized problems where the unparameterized version of L 1 is NP-hard. Assuming coNP ⊆ NP/poly, our framework essentially states that composing t L 1 -instances each with parameter k, to an L 2 -instance with parameter k ′ ≤ t 1/ d k O (1), implies that L 2 does not have a kernel of size O( k d − ε ) for any ε > 0. We show two examples of weak composition and derive polynomial kernelization lower bounds for d -B ipartite R egular P erfect C ode and d -D imensional M atching, parameterized by the solution size k. By reduction, using linear parameter transformations, we then derive the following lower-bounds for kernel sizes when the parameter is the solution size k (assuming coNP ⊆ NP/poly): d -S et P acking, d -S et C over, d -E xact S et C over, H itting S et with d -B ounded O ccurrences, and E xact H itting S et with d -B ounded O ccurrences have no kernels of size O ( k d –3–ε ) for any ε > 0. K d P acking and I nduced K 1, d P acking have no kernels of size O ( k d –4–ε ) for any ε > 0. d -R ed -B lue D ominating S et and d -S teiner T ree have no kernels of sizes O ( k d –3–ε ) and O ( k d −4−ε ), respectively, for any ε > 0. Our results give a negative answer to an open question raised by Dom, Lokshtanov, and Saurabh [ICALP2009] regarding the existence of uniform polynomial kernels for the problems above. All our lower bounds transfer automatically to compression lower bounds, a notion defined by Harnik and Naor [SICOMP2010] to study the compressibility of NP instances with cryptographic applications. We believe weak composition can be used to obtain polynomial kernelization lower bounds for other interesting parameterized problems. In the last part of the paper we strengthen previously known super-polynomial kernelization lower bounds to super-quasi-polynomial lower bounds, by showing that quasi-polynomial kernels for compositional NP-hard parameterized problems implies the collapse of the exponential hierarchy. These bounds hold even the kernelization algorithms are allowed to run in quasi-polynomial time.

IJCAI Conference 2011 Conference Paper

Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable

• Michael Fellows
• Tobias Friedrich
• Danny Hermelin
• Nina Narodytska
• Frances Rosamond

We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable while it is provably intractable in general.

TCS Journal 2010 Journal Article

Finding common structured patterns in linear graphs

• Guillaume Fertin
• Danny Hermelin
• Romeo Rizzi
• Stéphane Vialette

A linear graph is a graph whose vertices are linearly ordered. This linear ordering allows pairs of disjoint edges to be either preceding (<), nesting ( ⊏ ) or crossing ( ≬ ). Given a family of linear graphs, and a non-empty subset R ⊆ { <, ⊏, ≬ }, we are interested in the Maximum Common Structured Pattern (MCSP) problem: find a maximum size edge-disjoint graph, with edge pairs all comparable by one of the relations in R, that occurs as a subgraph in each of the linear graphs of the family. The MCSP problem generalizes many structure-comparison and structure-prediction problems that arise in computational molecular biology. We give tight hardness results for the MCSP problem for { <, ≬ } -structured patterns and { ⊏, ≬ } -structured patterns. Furthermore, we prove that the problem is approximable within ratios: (i) 2 ℋ ( k ) for { <, ≬ } -structured patterns, (ii) k 1 / 2 for { ⊏, ≬ } -structured patterns, and (iii) O ( k log k ) for { <, ⊏, ≬ } -structured patterns, where k is the size of the optimal solution and ℋ ( k ) = ∑ i = 1 k 1 / i is the k th harmonic number. Also, we provide combinatorial results concerning different types of structured patterns that are of independent interest in their own right.

TCS Journal 2009 Journal Article

On the parameterized complexity of multiple-interval graph problems

• Michael R. Fellows
• Danny Hermelin
• Frances Rosamond
• Stéphane Vialette

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more robustness in the modeling of the specific application. With this motivation in mind, a recent systematic study of optimization problems in multiple-interval graphs was initiated. In this sequel, we study multiple-interval graph problems from the perspective of parameterized complexity. The problems under consideration are k -Independent Set, k -Dominating Set, and k -Clique, which are all known to be W[1]-hard for general graphs, and NP-complete for multiple-interval graphs. We prove that k -Clique is in FPT, while k -Independent Set and k -Dominating Set are both W[1]-hard. We also prove that k -Independent Dominating Set, a hybrid of the two above problems, is also W[1]-hard. Our hardness results hold even when each vertex is associated with at most two intervals, and all intervals have unit length. Furthermore, as an interesting byproduct of our hardness results, we develop a useful technique for showing W[1]-hardness via a reduction from the k -Multicolored Clique problem, a variant of k -Clique. We believe this technique has interest in its own right, as it should help in simplifying W[1]-hardness results which are notoriously hard to construct and technically tedious.

TCS Journal 2008 Journal Article

Approximating the 2-interval pattern problem

• Maxime Crochemore
• Danny Hermelin
• Gad M. Landau
• Dror Rawitz
• Stéphane Vialette

We address the issue of approximating the 2-Interval Pattern problem over its various models and restrictions. This problem, motivated by RNA secondary structure prediction, asks to find a maximum cardinality subset of a 2-interval set with respect to some prespecified geometric constraints. We present several constant factor approximation algorithms whose performance guarantee depends on the different possible restrictions imposed on the input 2-interval set. In addition, we show that our results extend to the weighted variant of the problem.

I&C Journal 2008 Journal Article

The Minimum Substring Cover problem

• Danny Hermelin
• Dror Rawitz
• Romeo Rizzi
• Stéphane Vialette

In this paper, we consider the problem of covering a set of strings S with a set C of substrings in S, where C is said to cover S if every string in S can be written as a concatenation of the substrings in C. We discuss applications for the problem that arise in the context of computational biology and formal language theory. We then proceed to show several hardness of approximation results for the problem, and in the main part of the paper, we focus on devising approximation algorithms using two generic paradigms—the local-ratio technique and linear programming rounding.

SODA Conference 2007 Conference Paper

Optimization problems in multiple-interval graphs

• Ayelet Butman
• Danny Hermelin
• Moshe Lewenstein
• Dror Rawitz