Source author record

Ivan Bliznets

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity

Catalog footprint

Research overview

7works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Maximizing Happiness in Graphs of Bounded Clique-Width

Clique-width is one of the most important parameters that describes structural complexity of a graph. Probably, only treewidth is more studied graph width parameter. In this paper we study how clique-width influences the complexity of the Maximum Happy Vertices (MHV) and Maximum Happy Edges (MHE) problems. We answer a question of Choudhari and Reddy '18 about parameterization by the distance to threshold graphs by showing that MHE is NP-complete on threshold graphs. Hence, it is not even in XP when parameterized by clique-width, since threshold graphs have clique-width at most two. As a complement for this result we provide a $n^{\mathcal{O}(\ell \cdot \operatorname{cw})}$ algorithm for MHE, where $\ell$ is the number of colors and $\operatorname{cw}$ is the clique-width of the input graph. We also construct an FPT algorithm for MHV with running time $\mathcal{O}^*((\ell+1)^{\mathcal{O}(\operatorname{cw})})$ , where $\ell$ is the number of colors in the input. Additionally, we show $\mathcal{O}(\ell n^2)$ algorithm for MHV on interval graphs.

preprint2015arXiv

Kernelization lower bound for Permutation Pattern Matching

A permutation $π$ contains a permutation $σ$ as a pattern if it contains a subsequence of length $|σ|$ whose elements are in the same relative order as in the permutation $σ$ . This notion plays a major role in enumerative combinatorics. We prove that the problem does not have a polynomial kernel (under the widely believed complexity assumption $\mbox{NP} \not\subseteq \mbox{co-NP}/\mbox{poly}$) by introducing a new polynomial reduction from the clique problem to permutation pattern matching.

preprint2015arXiv

Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems

In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper Interval Completion, Threshold Completion, and Trivially Perfect Completion. In these problems, the task is to add at most k edges to a given graph in order to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds for all these problems, as well as for the related Chain Completion problem: Assuming the Exponential Time Hypothesis, none of these problems can be solved in time 2^O(n^(1/2) / log^c n) or 2^O(k^(1/4) / log^c k) n^O(1), for some integer c. Assuming the non-existence of a subexponential-time approximation scheme for Min Bisection on d-regular graphs, for some constant d, none of these problems can be solved in time 2^o(n) or 2^o(sqrt(k)) n^O(1). For all the aforementioned completion problems, apart from Proper Interval Completion, FPT algorithms with running time of the form 2^O(sqrt(k) log k) n^O(1) are known. Thus, the second result proves that a significant improvement of any of these algorithms would lead to a surprising breakthrough in the design of approximation algorithms for Min Bisection. To prove our results, we use a reduction methodology based on combining the classic approach of starting with a sparse instance of 3-Sat, prepared using the Sparsification Lemma, with the existence of almost linear-size Probabilistically Checkable Proofs (PCPs). Apart from our main results, we also obtain lower bounds excluding the existence of subexponential algorithms for the Optimum Linear Arrangement problem, as well as improved, yet still not tight, lower bounds for Feedback Arc Set in Tournaments.

preprint2015arXiv

Parameterized Complexity of Superstring Problems

In the Shortest Superstring problem we are given a set of strings $S=\{s_1, \ldots, s_n\}$ and integer $\ell$ and the question is to decide whether there is a superstring $s$ of length at most $\ell$ containing all strings of $S$ as substrings. We obtain several parameterized algorithms and complexity results for this problem. In particular, we give an algorithm which in time $2^{O(k)} \operatorname{poly}(n)$ finds a superstring of length at most $\ell$ containing at least $k$ strings of $S$ . We complement this by the lower bound showing that such a parameterization does not admit a polynomial kernel up to some complexity assumption. We also obtain several results about "below guaranteed values" parameterization of the problem. We show that parameterization by compression admits a polynomial kernel while parameterization "below matching" is hard.

preprint2014arXiv

A subexponential parameterized algorithm for Interval Completion

In the Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into an interval graph, i.e., a graph admitting an intersection model of intervals on a line. Motivated by applications in sparse matrix multiplication and molecular biology, Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999] asked for a fixed-parameter algorithm solving this problem. This question was answer affirmatively more than a decade later by Villanger at el. [STOC 2007; SIAM J. Comput. 2009], who presented an algorithm with running time $O(k^{2k}n^3m)$ . We give the first subexponential parameterized algorithm solving Interval Completion in time $k^{O(\sqrt{k})} n^{O(1)}$ . This adds Interval Completion to a very small list of parameterized graph modification problems solvable in subexponential time.

preprint2014arXiv

A subexponential parameterized algorithm for Proper Interval Completion

In the Proper Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of Proper Interval Completion from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999], who showed an algorithm for the problem working in $O(16^k (n + m))$ time. In this paper we present an algorithm with running time $k^{O(k^{2/3})} + O(nm(kn + m))$ , which is the first subexponential parameterized algorithm for Proper Interval Completion.

preprint2013arXiv

Largest chordal and interval subgraphs faster than 2^n

We prove that in an n-vertex graph, induced chordal and interval subgraphs with the maximum number of vertices can be found in time $O(2^{λn})$ for some $λ<1$ . These are the first algorithms breaking the trivial $2^n n^{O(1)}$ bound of the brute-force search for these problems.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ivan Bliznets

Research overview

Is this your work?

7 publications

Maximizing Happiness in Graphs of Bounded Clique-Width

Kernelization lower bound for Permutation Pattern Matching

Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems

Parameterized Complexity of Superstring Problems

A subexponential parameterized algorithm for Interval Completion

A subexponential parameterized algorithm for Proper Interval Completion

Largest chordal and interval subgraphs faster than 2^n

See the researcher in context

Building this map preview