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.