1. Fixed-parameter algorithms
Fixed-parameter algorithms solve hard optimization problems in a time polynomial in the input size but exponential in terms of
an additional parameter associated with the problem (the input size does not participate in the exponential part of the runtime expression). If the parameter is small then an intractable problem can be solved in a low-polynomial time. Problems that can be solved in this way are called Fixed-Parameter Tractable (FPT). For more information about the area please see here.
Many hard optimization problems are FPT. On the other hand, there are many problems that are not FPT unless some widely believed conjecture in the complexity theory fails. Also, there are problems whose status of fixed-parameter tractability is a very challenging question that stays open for many years despite a lot of research efforts. The following works contribute to understanding the answers to such open questions.
1.1. Fixed-parameter tractability of directed feedback vertex set problem
Relevant publication: [J6] J. Chen, Y. Liu, S. Lu, B. O’Sullivan and I. Razgon
“A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem",
Journal of the ACM, Volume 55, Issue 5, 2008. PDF
Description: The (parameterized) directed feedback vertex set (DFVS) problem asks, given parameter k,
whether the given graph can be made acyclic by removal of at most k vertices.
The status of fixed-parameter tractability of this problem was a notorious open question that resisted
attempts of many research groups since the late 80-th.
In [J6] we provide the first fixed-parameter algorithm for this problem.
1.2. Fixed-parameter tractability of the minimum 2CNF deletion problem
Relevant publication: [J2] I. Razgon and B. O’Sullivan “Almost-2-SAT is Fixed-Parameter Tractable”,
Journal of Computer and System Sciences, Volume 75, Issue 8, pp. 435–450, 2009. PDF
Description: The minimum 2-CNF deletion problem asks, given a parameter k, whether the given 2-CNF formula
can be made satisfiable by removal of at most k clauses.
The question regarding the status of fixed-parameter tractability of this problem was first posed by
Mahajan and Raman in 1997. The problem attracted attention of researchers because it is a very natural
parameterization of the MAX-2-SAT problem and it is equivalent to a number of other problems with
real-world applications. Despite significant efforts, the question remained open for more than 10 years
and was considered as 'one of the central challenges for parameterized algorithm design' (Niedermeier,
"Invitation to fixed-parameter algorithms", 2006) until we have resolved this question in [J2].
1.3. Fixed-parameter tractability of constrained separation and bipartization problems
Relevant publication: [P2] D. Marx, B. O’Sullivan and I. Razgon “Treewidth reduction for constrained
separation and bipartization problems”, The 27th International Symposium on
Theoretical Aspects of Computer Science (STACS 2010), to appear. PDF
Description: It is well known that a smallest set of vertices whose removal separates the given two terminals s
and t can be computed in a polynomial time. However, if we impose additional constraints
on the separator (e.g., require the separator to be an independent set), the problem usually
becomes NP-hard. We propose a methodology that allows to easily show fixed-parameter
tractability for a broad class of constrained separation problems parameterized by the size of
the separator. Using the main lemma from (Reed et al., Operations Research Letters, 2004),
we extend this methodology to constrained bipartization problems (i.e., whether the graph can be
made bipartite by removal of a set of at most k vertices that induce a subgraph having
the given property). The most interesting outcome of this methodology is showing that
it is FPT to check whether the given graph is 3-colorable so that one of the colours is assigned to
exactly k vertices (or, equivalently, whether the given graph can be made bipartite by removal
of an independent set of size exactly k). This problem was open since 2001 and attracted
a considerable attention from the parameterized complexity researchers.
1.4. Fixed-parameter tractability of the multicut problem
Relevant publication: [P1] D. Marx, and I. Razgon “Fixed-parameter tractability of multicut parameterized by the size of the cutset”, STOC2011,
pp. 469-478. PDF
Description: Given a graph and a set of pairs of terminal vertices, the (vertex) multicut problem asks if it is possible to
remove at most k vertices (k is, as usual, the parameter) so that all the pairs of terminal vertices in the above
set are separated. The question regarding the status of fixed-parameter tractability of this problem was first
posed by Marx in 2004 and in the last couple of years was considered as one of the most challenging open
problems in the area of fixed-parameter tractability. Moreover, this problem is of a fundamental nature:
it has a number of interesting and actively investigated special cases.
We establish fixed-parameter tractability of this problem.
2. Moderately exponential time algorithms.
These algorithms solve intractable problems with the runtime better than the runtime of a brute-force algorithm.
For example, if the problem is to select a subset with the given property out of a set of n elements then the brute-force algorithm
just explores all 2n subsets of this set, while a more sophisticated algorithm may solve this problem in time O(cn) for c<2.
For some problems such algorithms are easy to design and the challenging question is to make the base c of exponent as small as possible, not just smaller than 2. However, there are problems for which even 'taking off the ground', i.e. designing an algorithm for which the corresponding base of the exponent is at least slightly smaller 2 is a very challenging task. My most significant
research results in the area are related to the latter type of problems.
2.1. Undirected feedback vertex set
Relevant publications: [P17] I. Razgon “Exact Computation of Maximum Induced Forest”, Scandinavian
Workshop on Algorithm Theory (SWAT 2006), LNCS 4059, pp. 160-171. PDF
[J7] F. Fomin, S. Gaspers, A. Pyatkin, and I. Razgon
“On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms”,
Algorithmica, Volume 52, Issue 2, pp. 293-307, 2008. PDF
Description: The undirected feedback vertex set (UFVS) problem asks for a smallest subset of vertices participating
in all the cycles of the given graph. This is one of the most well-known NP-hard problems, so,
the question whether the problem can be solved faster then by a brute-force algorithm, attracted
a considerable attention of researchers in the area.
Despite the efforts, the question remained open for a few years with faster algorithms known only for
a number of special cases. I proposed in [P15] the first algorithm solving the problem faster than O(2n).
Fomin et al. used my approach to obtain a better algorithm, and [J6] is our joint journal paper.
2.2. Directed feedback vertex set
Relevant publication: [P13] I. Razgon “Computing Minimum Directed Feedback Vertex Set in O*(1.9977n)”,
The Tenth Italian Conference on Theoretical Computer Science (ICTCS 2007),
World Scientific, volume 6581, pp. 70-81. PDF
Description: This is the first algorithm that solves the DFVS problem faster than O(2n). Being strategically similar to
the case of UFVS, the question was very demanding technically and required a lot of time to realize how
to overcome a number of subtle and involved cases.
3. Experimental algorithms for the constraint satisfaction problem (CSP).
The papers below are related to design and analysis of CSP solvers, i.e. algorithms whose performance is checked empirically on
a collection of widely accepted benchmark sets of instances.
3.1. Do theoretically better algorithms have a better performance?
Relevant publication: [P18] I. Razgon and A. Meisels “A CSP Search Algorithm with Reduced Branching
Factor”, Volume "Recent Advances in Constraints", LNAI 3978, pp. 59-72, 2006. PDF
Description: All the well-known CSP solvers are based on algorithms whose runtime is O(dn), where d is the largest
domain size and n is the number of variables. This is despite a well-known fact that a (binary) CSP can
be easily solved in time O((d/2)n). So, it is quite an intriguing question whether an algorithm which is
much better theoretically would result in a constraint solver with a better practical performance.
In [P16] we address the question taking a theoretically efficient algorithm equipping it with pruning
procedures and comparing it with standard solvers. The results show that the theoretically efficient
solver indeed sometimes outperforms the standard one, but the ratio of improvement is much smaller that
one would expect taking into account the exponential gap between the worst-case runtimes.
3.2. A theoretical explanation of a better empirical performance
Relevant publication: [P19] I. Razgon “Complexity Analysis of Heuristic CSP Search Algorithms”,
Volume "Recent Advances in Constraints", LNAI 3978, pp. 88-99, 2006. PDF
Description: Empirical comparison of constraint solvers is an elusive matter. It often happens that two solvers are
incomparable in the sense that each of them performs better than the other on some set of benchmarks.
Sometimes even on the same set of benchmarks different research groups obtain different results on
the same pair of solvers (e.g., due to different tuning of parameters). However, there are empirical results
on which the community is kind of unanimous.
One example of such result is that if we equip the Forward Checking (FC) algorithm with
Conflict-Directed Backjumping and with the 'Smallest Domain First' variable ordering heuristic,
the resulting solver would be better than FC and even better than FC being equipped with only one of
the above components. In [P17] we provide a possible explanation to this phenomenon by showing that
the resulting solver has a better worst-case runtime that FC-CBJ and than FC together with the 'Smallest
Domain First' heuristic only.