Arrow Research search

Author name cluster

Ivan Bliznets

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
2 author rows

Possible papers

12

JAIR Journal 2026 Journal Article

Partial Minimum Satisfiability: Fine-Grained Analysis

  • Ivan Bliznets
  • Danil Sagunov
  • Kirill Simonov

There is a well-known approach to cope with NP-hard problems in practice: reduce the given problem to SAT or Max-SAT and run a SAT or a Max-SAT solver. This method is very efficient since SAT/Max-SAT solvers are extremely well-studied, as well as the complexity of these problems. At IJCAI-2011, Li et al. proposed an alternative to this approach and suggested the Partial Minimum Satisfiability problem as a reduction target for NP-hard problems. They developed the MinSatz solver and showed that reducing to Partial Min-SAT and using MinSatz is in some cases more efficient than reductions to SAT or Max-SAT. Since then many results connected to the Partial Min-SAT problem were published. However, to the best of our knowledge, the worst-case complexity of Partial Min-SAT has not been studied up until now. Our goal is to fix the issue and show a O*((2 - ε)m) lower bound under the SETH assumption (here m is the total number of clauses), as well as several other lower bounds and parameterized exact algorithms with better-than-trivial running time.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Parameterization of (Partial) Maximum Satisfiability above Matching in a Variable-Clause Graph

  • Vasily Alferov
  • Ivan Bliznets
  • Kirill Brilliantov

In the paper, we study the Maximum Satisfiability and the Partial Maximum Satisfiability problems. Using Gallai–Edmonds decomposition, we significantly improve the upper bound for the Maximum Satisfiability problem parameterized above maximum matching in the variable-clause graph. Our algorithm operates with a runtime of O*(2.83^k'), a substantial improvement compared to the previous approach requiring O*(4^k' ), where k' denotes the relevant parameter. Moreover, this result immediately implies O*(1.14977^m) and O*(1.27895^m) time algorithms for the (n, 3)-MaxSAT and (n, 4)-MaxSAT where m is the overall number of clauses. These upper bounds improve prior-known upper bounds equal to O*(1.1554^m) and O*(1.2872^m). We also adapt the algorithm so that it can handle instances of Partial Maximum Satisfiability without losing performance in some cases. Note that this is somewhat surprising, as the existence of even one hard clause can significantly increase the hardness of a problem.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Improved Algorithms for Maximum Satisfiability and Its Special Cases

  • Kirill Brilliantov
  • Vasily Alferov
  • Ivan Bliznets

The Maximum Satisfiability (MAXSAT) problem is an optimization version of the Satisfiability problem (SAT) in which one is given a CNF formula with n variables and needs to find the maximum number of simultaneously satisfiable clauses. Recent works achieved significant progress in proving new upper bounds on the worst-case computational complexity of MAXSAT. All these works reduce general MAXSAT to a special case of MAXSAT where each variable appears a small number of times. So, it is important to design fast algorithms for (n,k)-MAXSAT to construct an efficient exact algorithm for MAXSAT. (n,k)-MAXSAT is a special case of MAXSAT where each variable appears at most k times in the input formula. For the (n,3)-MAXSAT problem, we design a O*(1.1749^n) algorithm improving on the previous record running time of O*(1.191^n). For the (n,4)-MAXSAT problem, we construct a O*(1.3803^n) algorithm improving on the previous best running time of O*(1.4254^n). Using the results, we develop a O*(1.0911^L) algorithm for the MAXSAT where L is a length of the input formula which improves previous algorithm with O*(1.0927^L) running time.

PDF Details DOI

MFCS Conference 2023 Conference Paper

MaxCut Above Guarantee

  • Ivan Bliznets
  • Vladislav Epifanov

In this paper, we study the computational complexity of the Maximum Cut problem parameterized above guarantee. Our main result provides a linear kernel for the Maximum Cut problem in connected graphs parameterized above the spanning tree. This kernel significantly improves the previous O(k⁵) kernel given by Madathil, Saurabh, and Zehavi [ToCS 2020]. We also provide subexponential running time algorithms for this problem in special classes of graphs: chordal, split, and co-bipartite. We complete the picture by lower bounds under the assumption of the ETH. Moreover, we initiate a study of the Maximum Cut problem above 2/3|E| lower bound in tripartite graphs.

Details

IJCAI Conference 2022 Conference Paper

Fine-grained Complexity of Partial Minimum Satisfiability

  • Ivan Bliznets
  • Danil Sagunov
  • Kirill Simonov

There is a well-known approach to cope with NP-hard problems in practice: reduce the given problem to SAT or MAXSAT and run a SAT or a MaxSAT solver. This method is very efficient since SAT/MaxSAT solvers are extremely well-studied, as well as the complexity of these problems. At AAAI 2011, Li et al. proposed an alternative to this approach and suggested the Partial Minimum Satisfiability problem as a reduction target for NP-hard problems. They developed the MinSatz solver and showed that reducing to Partial Minimum Satisfiability and using MinSatz is in some cases more efficient than reductions to SAT or MaxSAT. Since then many results connected to the Partial Minimum Satisfiability problem were published. However, to the best of our knowledge, the worst-case complexity of Partial Minimum Satisfiability has not been studied up until now. Our goal is to fix the issue and show a O*((2-ɛ)^m) lower bound under the SETH assumption (here m is the total number of clauses), as well as several other lower bounds and parameterized exact algorithms with better-than-trivial running time.

PDF Details DOI

AAAI Conference 2021 Conference Paper

New Length Dependent Algorithm for Maximum Satisfiability Problem

  • Vasily Alferov
  • Ivan Bliznets

In this paper, we study the computational complexity of the MAXIMUM SATISFIABILITY problem in terms of the length L of a given formula. We present an algorithm with running time O(1. 0927L ), hence, improving the previously known best upper bound O(1. 1058L ) developed more than 20 years ago by Bansal and Raman. Theoretically speaking, our algorithm increases the length of solvable formulas by 13. 3% (compare this to the recent breakthrough result for MAXI- MUM SATISFIABILITY problem with respect to the number of clauses by Xu et al. in 2019 giving a 7. 5% improvement). Besides, we propose a significantly simpler algorithm with running time O(1. 1049L ). The algorithm outperforms Bansal’s and Raman’s algorithm in simplicity and running time.

PDF Details

MFCS Conference 2017 Conference Paper

Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters

  • Ivan Bliznets
  • Nikolay Karpov

Clustering is a well-known and important problem with numerous applications. The graph-based model is one of the typical cluster models. In the graph model generally clusters are defined as cliques. However, such approach might be too restrictive as in some applications, not all objects from the same cluster must be connected. That is why different types of cliques relaxations often considered as clusters. In our work, we consider a problem of partitioning graph into clusters and a problem of isolating cluster of a special type where by cluster we mean highly connected subgraph. Initially, such clusterization was proposed by Hartuv and Shamir. And their HCS clustering algorithm was extensively applied in practice. It was used to cluster cDNA fingerprints, to find complexes in protein-protein interaction data, to group protein sequences hierarchically into superfamily and family clusters, to find families of regulatory RNA structures. The HCS algorithm partitions graph in highly connected subgraphs. However, it is achieved by deletion of not necessarily the minimum number of edges. In our work, we try to minimize the number of edge deletions. We consider problems from the parameterized point of view where the main parameter is a number of allowed edge deletions. The presented algorithms significantly improve previous known running times for the Highly Connected Deletion (improved from \cOs\left(81^k\right) to \cOs\left(3^k\right)), Isolated Highly Connected Subgraph (from \cOs(4^k) to \cOs\left(k^{\cO\left(k^{\sfrac{2}{3}}\right)}\right) ), Seeded Highly Connected Edge Deletion (from \cOs\left(16^{k^{\sfrac{3}{4}}}\right) to \cOs\left(k^{\sqrt{k}}\right)) problems. Furthermore, we present a subexponential algorithm for Highly Connected Deletion problem if the number of clusters is bounded. Overall our work contains three subexponential algorithms which is unusual as very recently there were known very few problems admitting subexponential algorithms.

Details

SODA Conference 2016 Conference Paper

Subexponential parameterized algorithm for Interval Completion

  • Ivan Bliznets
  • Fedor V. Fomin
  • Marcin Pilipczuk
  • Michal Pilipczuk

In the I nterval C ompletion problem we are given an n -vertex graph G and an integer k, and the task is to transform G by making use of at most k edge additions into an interval graph. This is a fundamental graph modification problem with applications in sparse matrix multiplication and molecular biology. The question about fixed-parameter tractability of I nterval C ompletion was asked by Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999] and was answered 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 2 k n 3 m ). We give the first subexponential parameterized algorithm solving I nterval C ompletion in time. This adds I nterval C ompletion to a very small list of parameterized graph modification problems solvable in subexponential time.

Details