**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 *2 ^{n}* subsets of this set, while a more sophisticated algorithm may solve this problem in time

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(**2 ^{n})*.

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.9977^{n})”,

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(**2 ^{n}).* 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(**d ^{n}*

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.