Gregory Gutin

Exact capacitated domination: on the computational complexity of uniqueness

In this paper we consider a local service-requirement assignment problem named exact capacitated domination from an algorithmic point of view. This problem aims to find a solution (a Nash equilibrium) to a game-theoretic model of public good provision. In the problem we are given a capacitated graph, a graph with a parameter defined on each vertex that is interpreted as the capacity of that vertex. The objective is to find a DP-Nash subgraph: a spanning bipartite subgraph with partite sets D and P, called the D-set and P-set respectively, such that no vertex in P is isolated and that each vertex in D is adjacent to a number of vertices equal to its capacity. We show that whether a capacitated graph has a unique DP-Nash subgraph can be decided in polynomial time. However, we also show that the nearby problem of deciding whether a capacitated graph has a unique D-set is co-NP-complete.

p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms

We introduce and study two natural generalizations of the Connected VertexCover (VC) problem: the $p$ -Edge-Connected and $p$ -Vertex-Connected VC problem (where $p \geq 2$ is a fixed integer). Like Connected VC, both new VC problems are FPT, but do not admit a polynomial kernel unless $NP \subseteq coNP/poly$ , which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. We obtain an $O(2^{O(pk)}n^{O(1)})$ -time algorithm for the $p$ -Edge-Connected VC and an $O(2^{O(k^2)}n^{O(1)})$ -time algorithm for the $p$ -Vertex-Connected VC. Finally, we describe a $2(p+1)$ -approximation algorithm for the $p$ -Edge-Connected VC. The proofs for the new VC problems require more sophisticated arguments than for Connected VC. In particular, for the approximation algorithm we use Gomory-Hu trees and for the approximate kernels a result on small-size spanning $p$ -vertex/edge-connected subgraph of a $p$ -vertex/edge-connected graph obtained independently by Nishizeki and Poljak (1994) and Nagamochi and Ibaraki (1992).

Results on the Small Quasi-Kernel Conjecture

A {\em quasi-kernel} of a digraph $D$ is an independent set $Q\subseteq V(D)$ such that for every vertex $v\in V(D)\backslash Q$ , there exists a directed path with one or two arcs from $v$ to a vertex $u\in Q$ . In 1974, Chvátal and Lovász proved that every digraph has a quasi-kernel. In 1976, Erdős and Sźekely conjectured that every sink-free digraph $D=(V(D),A(D))$ has a quasi-kernel of size at most $|V(D)|/2$ . In this paper, we give a new method to show that the conjecture holds for a generalization of anti-claw-free digraphs. For any sink-free one-way split digraph $D$ of order $n$ , when $n\geq 3$ , we show a stronger result that $D$ has a quasi-kernel of size at most $\frac{n+3}{2} - \sqrt{n}$ , and the bound is sharp.

Solving Routing Problems via Important Cuts

We introduce a novel approach of using important cuts which allowed us to design significantly faster fixed-parameter tractable (FPT) algorithms for the following routing problems: the Mixed Chinese Postman Problem parameterized by the number of directed edges (Gutin et al., JCSS 2017), the Minimum Shared Edges problem (MSE) parameterized by the number p of paths between two specified vertices (Fluschnik et al., JCSS 2019), and the Weighted Min Cut Prevention problem (Gruttemeier et al., WG 2021). The Minimum Vulnerability problem (MV) is a generalization of MSE (Assadi et al., Algorithmica 2014). The only known FPT algorithm for MV parameterized by p (the same parameter as for MSE) was for chordal graphs (Aoki et al., JCO 2018). We design an FPT algorithm for MV on all undirected graphs.

Strong subgraph 2-arc-connectivity and arc-strong connectivity of Cartesian product of digraphs

Let $D=(V,A)$ be a digraph of order $n$ , $S$ a subset of $V$ of size $k$ and $2\le k\leq n$ . A strong subgraph $H$ of $D$ is called an $S$ -strong subgraph if $S\subseteq V(H)$ . A pair of $S$ -strong subgraphs $D_1$ and $D_2$ are said to be arc-disjoint if $A(D_1)\cap A(D_2)=\emptyset$ . Let $λ_S(D)$ be the maximum number of arc-disjoint $S$ -strong subgraphs in $D$ . The strong subgraph $k$ -arc-connectivity is defined as $λ_k(D)=\min\{λ_S(D)\mid S\subseteq V(D), |S|=k\}.$ The parameter $λ_k(D)$ can be seen as a generalization of classical edge-connectivity of undirected graphs. In this paper, we first obtain a formula for the arc-connectivity of Cartesian product $λ(G\Box H)$ of two digraphs $G$ and $H$ generalizing a formula for edge-connectivity of Cartesian product of two undirected graphs obtained by Xu and Yang (2006). Then we study the strong subgraph 2-arc-connectivity of Cartesian product $λ_2(G\Box H)$ and prove that $\min\left \{ λ\left ( G \right ) \left | H \right | , λ\left ( H \right ) \left |G \right |,δ^{+ } \left ( G \right )+ δ^{+ } \left ( H \right ),δ^{- } \left ( G \right )+ δ^{- } \left ( H \right ) \right \}\geλ_2(G\Box H)\ge λ_2(G)+λ_2(H)-1.$ The upper bound for $λ_2(G\Box H)$ is sharp and is a simple corollary of the formula for $λ(G\Box H)$ . The lower bound for $λ_2(G\Box H)$ is either sharp or almost sharp i.e. differs by 1 from the sharp bound. We also obtain exact values for $λ_2(G\Box H)$ , where $G$ and $H$ are digraphs from some digraph families.

preprint2021arXiv

The Effect of Social Distancing on the Reach of an Epidemic in Social Networks

How does social distancing affect the reach of an epidemic in social networks? We present Monte Carlo simulation results of a capacity constrained Susceptible-Infected-Removed (SIR) model. The key modelling feature is that individuals are limited in the number of acquaintances that they can interact with, thereby constraining disease transmission to an infectious subnetwork of the original social network. While increased social distancing always reduces the spread of an infectious disease, the magnitude varies greatly depending on the topology of the network. Our results also reveal the importance of coordinating social distancing policies at the global level. In particular, the public health benefits from social distancing to a group (e.g., a country) may be completely undone if that group maintains connections with outside groups that are not following suit.

preprint2020arXiv

Approximation algorithms for general cluster routing problem

Graph routing problems have been investigated extensively in operations research, computer science and engineering due to their ubiquity and vast applications. In this paper, we study constant approximation algorithms for some variations of the general cluster routing problem. In this problem, we are given an edge-weighted complete undirected graph $G=(V,E,c),$ whose vertex set is partitioned into clusters $C_{1},\dots ,C_{k}.$ We are also given a subset $V'$ of $V$ and a subset $E'$ of $E.$ The weight function $c$ satisfies the triangle inequality. The goal is to find a minimum cost walk $T$ that visits each vertex in $V'$ only once, traverses every edge in $E'$ at least once and for every $i\in [k]$ all vertices of $C_i$ are traversed consecutively.

preprint2020arXiv

Note on semi-proper orientations of outerplanar graphs

A semi-proper orientation of a given graph $G$ , denoted by $(D,w)$ , is an orientation $D$ with a weight function $w: A(D)\rightarrow \mathbb{Z}_+$ , such that the in-weight of any adjacent vertices are distinct, where the in-weight of $v$ in $D$ , denoted by $w^-_D(v)$ , is the sum of the weights of arcs towards $v$ . The semi-proper orientation number of a graph $G$ , denoted by $\overrightarrowχ_s(G)$ , is the minimum of maximum in-weight of $v$ in $D$ over all semi-proper orientation $(D,w)$ of $G$ . This parameter was first introduced by Dehghan (2019). When the weights of all edges eqaul to one, this parameter is equal to the proper orientation number of $G$ . The optimal semi-proper orientation is a semi-proper orientation $(D,w)$ such that $\max_{v\in V(G)}w_D^-(v)=\overrightarrowχ_s(G)$ . Araújo et al. (2016) showed that $\overrightarrowχ(G)\le 7$ for every cactus $G$ and the bound is tight. We prove that for every cactus $G$ , $\overrightarrowχ_s(G) \le 3$ and the bound is tight. Araújo et al. (2015) asked whether there is a constant $c$ such that $\overrightarrowχ(G)\le c$ for all outerplanar graphs $G.$ While this problem remains open, we consider it in the weighted case. We prove that for every outerplanar graph $G,$ $\overrightarrowχ_s(G)\le 4$ and the bound is tight.

preprint2020arXiv

Proximity and Remoteness in Directed and Undirected Graphs

Let $D$ be a strongly connected digraph. The average distance $\barσ(v)$ of a vertex $v$ of $D$ is the arithmetic mean of the distances from $v$ to all other vertices of $D$ . The remoteness $ρ(D)$ and proximity $π(D)$ of $D$ are the maximum and the minimum of the average distances of the vertices of $D$ , respectively. We obtain sharp upper and lower bounds on $π(D)$ and $ρ(D)$ as a function of the order $n$ of $D$ and describe the extreme digraphs for all the bounds. We also obtain such bounds for strong tournaments. We show that for a strong tournament $T$ , we have $π(T)=ρ(T)$ if and only if $T$ is regular. Due to this result, one may conjecture that every strong digraph $D$ with $π(D)=ρ(D)$ is regular. We present an infinite family of non-regular strong digraphs $D$ such that $π(D)=ρ(D).$ We describe such a family for undirected graphs as well.

A Multivariate Approach for Checking Resiliency in Access Control

In recent years, several combinatorial problems were introduced in the area of access control. Typically, such problems deal with an authorization policy, seen as a relation $UR \subseteq U \times R$ , where $(u, r) \in UR$ means that user $u$ is authorized to access resource $r$ . Li, Tripunitara and Wang (2009) introduced the Resiliency Checking Problem (RCP), in which we are given an authorization policy, a subset of resources $P \subseteq R$ , as well as integers $s \ge 0$ , $d \ge 1$ and $t \geq 1$ . It asks whether upon removal of any set of at most $s$ users, there still exist $d$ pairwise disjoint sets of at most $t$ users such that each set has collectively access to all resources in $P$ . This problem possesses several parameters which appear to take small values in practice. We thus analyze the parameterized complexity of RCP with respect to these parameters, by considering all possible combinations of $|P|, s, d, t$ . In all but one case, we are able to settle whether the problem is in FPT, XP, W[2]-hard, para-NP-hard or para-coNP-hard. We also consider the restricted case where $s=0$ for which we determine the complexity for all possible combinations of the parameters.

Acyclicity in Edge-Colored Graphs

A walk $W$ in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in $W$ is of different color. We introduce and study five types of PC acyclicity in edge-colored graphs such that graphs of PC acyclicity of type $i$ is a proper superset of graphs of acyclicity of type $i+1$ , $i=1,2,3,4.$ The first three types are equivalent to the absence of PC cycles, PC trails, and PC walks, respectively. While graphs of types 1, 2 and 3 can be recognized in polynomial time, the problem of recognizing graphs of type 4 is, somewhat surprisingly, NP-hard even for 2-edge-colored graphs (i.e., when only two colors are used). The same problem with respect to type 5 is polynomial-time solvable for all edge-colored graphs. Using the five types, we investigate the border between intractability and tractability for the problems of finding the maximum number of internally vertex disjoint PC paths between two vertices and the minimum number of vertices to meet all PC paths between two vertices.

Chinese Postman Problem on Edge-Colored Multigraphs

It is well-known that the Chinese postman problem on undirected and directed graphs is polynomial-time solvable. We extend this result to edge-colored multigraphs. Our result is in sharp contrast to the Chinese postman problem on mixed graphs, i.e., graphs with directed and undirected edges, for which the problem is NP-hard.

Cryptographic Enforcement of Information Flow Policies without Public Information via Tree Partitions

We may enforce an information flow policy by encrypting a protected resource and ensuring that only users authorized by the policy are able to decrypt the resource. In most schemes in the literature that use symmetric cryptographic primitives, each user is assigned a single secret and derives decryption keys using this secret and publicly available information. Recent work has challenged this approach by developing schemes, based on a chain partition of the information flow policy, that do not require public information for key derivation, the trade-off being that a user may need to be assigned more than one secret. In general, many different chain partitions exist for the same policy and, until now, it was not known how to compute an appropriate one. In this paper, we introduce the notion of a tree partition, of which chain partitions are a special case. We show how a tree partition may be used to define a cryptographic enforcement scheme and prove that such schemes can be instantiated in such a way as to preserve the strongest security properties known for cryptographic enforcement schemes. We establish a number of results linking the amount of secret material that needs to be distributed to users with a weighted acyclic graph derived from the tree partition. These results enable us to develop efficient algorithms for deriving tree and chain partitions that minimize the amount of secret material that needs to be distributed.

Odd Properly Colored Cycles in Edge-Colored Graphs

It is well-known that an undirected graph has no odd cycle if and only if it is bipartite. A less obvious, but similar result holds for directed graphs: a strongly connected digraph has no odd cycle if and only if it is bipartite. Can this result be further generalized to more general graphs such as edge-colored graphs? In this paper, we study this problem and show how to decide if there exists an odd properly colored cycle in a given edge-colored graph. As a by-product, we show how to detect if there is a perfect matching in a graph with even (or odd) number of edges in a given edge set.

Parameterized Complexity of the $k$ -Arc Chinese Postman Problem

In the Mixed Chinese Postman Problem (MCPP), given an edge-weighted mixed graph $G$ ( $G$ may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP parameterized by the number of edges was known to be fixed-parameter tractable using a simple argument. Solving an open question of van Bevern et al., we prove that the MCPP parameterized by the number of arcs is also fixed-parameter tractable. Our proof is more involved and, in particular, uses a well-known result of Marx, O'Sullivan and Razgon (2013) on the treewidth of torso graphs with respect to small separators. We obtain a small cut analog of this result, and use it to construct a tree decomposition which, despite not having bounded width, has other properties allowing us to design a fixed-parameter algorithm.

The Authorization Policy Existence Problem

Constraints such as separation-of-duty are widely used to specify requirements that supplement basic authorization policies. However, the existence of constraints (and authorization policies) may mean that a user is unable to fulfill her/his organizational duties because access to resources has been denied. In short, there is a tension between the need to protect resources (using policies and constraints) and the availability of resources. Recent work on workflow satisfiability and resiliency in access control asks whether this tension compromises the ability of an organization to achieve its objectives. In this paper, we develop a new method of specifying constraints which subsumes much related work and allows a wider range of constraints to be specified. The use of such constraints leads naturally to a range of questions related to "policy existence", where a positive answer means that an organization's objectives can be realized. We analyze the complexity of these policy existence questions and, for particular sub-classes of constraints defined by our language, develop fixed-parameter tractable algorithms to solve them.

The Bi-Objective Workflow Satisfiability Problem and Workflow Resiliency

A computerized workflow management system may enforce a security policy, specified in terms of authorized actions and constraints, thereby restricting which users can perform particular steps in a workflow. The existence of a security policy may mean it is impossible to find a valid plan (an assignment of steps to authorized users such that all constraints are satisfied). Work in the literature focuses on the workflow satisfiability problem, a \emph{decision} problem that outputs a valid plan if the instance is satisfiable (and a negative result otherwise). In this paper, we introduce the \textsc{Bi-Objective Workflow Satisfiability Problem} (\BOWSP), which enables us to solve \emph{optimization} problems related to workflows and security policies. In particular, we are able to compute a "least bad" plan when some components of the security policy may be violated. In general, \BOWSP is intractable from both the classical and parameterized complexity point of view. We prove there exists an fixed-parameter tractable (FPT) algorithm to compute a Pareto front for \BOWSP if we restrict our attention to user-independent constraints. We also present a second algorithm to compute a Pareto front which uses mixed integer programming (MIP). We compare the performance of both our algorithms on synthetic instances, and show that the FPT algorithm outperforms the MIP-based one by several orders of magnitude on most of the instances. Finally, we study the important question of workflow resiliency and prove new results establishing that known decision problems are fixed-parameter tractable when restricted to user-independent constraints. We then propose a new way of modeling the availability of users and demonstrate that many questions related to resiliency in the context of this new model may be reduced to instances of \BOWSP.

Cryptographic Enforcement of Information Flow Policies without Public Information

Cryptographic access control has been studied for over 30 years and is now a mature research topic. When symmetric cryptographic primitives are used, each protected resource is encrypted and only authorized users should have access to the encryption key. By treating the keys themselves as protected resources, it is possible to develop schemes in which authorized keys are derived from the keys explicitly assigned to the user's possession and publicly available information. It has been generally assumed that each user would be assigned a single key from which all other authorized keys would be derived. Recent work has challenged this assumption by developing schemes that do not require public information, the trade-off being that a user may require more than one key. However, these new schemes, which require a chain partition of the partially ordered set on which the access control policy is based, have some disadvantages. In this paper we define the notion of a tree-based cryptographic enforcement scheme, which, like chain-based schemes, requires no public information. We establish that the strong security properties of chain-based schemes are preserved by tree-based schemes, and provide an efficient construction for deriving a tree-based enforcement scheme from a given policy that minimizes the number of keys required.

Linear-Vertex Kernel for the Problem of Packing $r$ -Stars into a Graph without Long Induced Paths

Let integers $r\ge 2$ and $d\ge 3$ be fixed. Let ${\cal G}_d$ be the set of graphs with no induced path on $d$ vertices. We study the problem of packing $k$ vertex-disjoint copies of $K_{1,r}$ ( $k\ge 2$ ) into a graph $G$ from parameterized preprocessing, i.e., kernelization, point of view. We show that every graph $G\in {\cal G}_d$ can be reduced, in polynomial time, to a graph $G'\in {\cal G}_d$ with $O(k)$ vertices such that $G$ has at least $k$ vertex-disjoint copies of $K_{1,r}$ if and only if $G'$ has. Such a result is known for arbitrary graphs $G$ when $r=2$ and we conjecture that it holds for every $r\ge 2$ .

Note on Perfect Forests

A spanning subgraph $F$ of a graph $G$ is called perfect if $F$ is a forest, the degree $d_F(x)$ of each vertex $x$ in $F$ is odd, and each tree of $F$ is an induced subgraph of $G$ . We provide a short proof of the following theorem of A.D. Scott (Graphs & Combin., 2001): a connected graph $G$ contains a perfect forest if and only if $G$ has an even number of vertices.

Note on Perfect Forests in Digraphs

A spanning subgraph $F$ of a graph $G$ is called {\em perfect} if $F$ is a forest, the degree $d_F(x)$ of each vertex $x$ in $F$ is odd, and each tree of $F$ is an induced subgraph of $G$ . Alex Scott (Graphs \& Combin., 2001) proved that every connected graph $G$ contains a perfect forest if and only if $G$ has an even number of vertices. We consider four generalizations to directed graphs of the concept of a perfect forest. While the problem of existence of the most straightforward one is NP-hard, for the three others this problem is polynomial-time solvable. Moreover, every digraph with only one strong component contains a directed forest of each of these three generalization types. One of our results extends Scott's theorem to digraphs in a non-trivial way.

On the Workflow Satisfiability Problem with Class-Independent Constraints

A workflow specification defines sets of steps and users. An authorization policy determines for each user a subset of steps the user is allowed to perform. Other security requirements, such as separation-of-duty, impose constraints on which subsets of users may perform certain subsets of steps. The \emph{workflow satisfiability problem} (WSP) is the problem of determining whether there exists an assignment of users to workflow steps that satisfies all such authorizations and constraints. An algorithm for solving WSP is important, both as a static analysis tool for workflow specifications, and for the construction of run-time reference monitors for workflow management systems. Given the computational difficulty of WSP, it is important, particularly for the second application, that such algorithms are as efficient as possible. We introduce class-independent constraints, enabling us to model scenarios where the set of users is partitioned into groups, and the identities of the user groups are irrelevant to the satisfaction of the constraint. We prove that solving WSP is fixed-parameter tractable (FPT) for this class of constraints and develop an FPT algorithm that is useful in practice. We compare the performance of the FPT algorithm with that of SAT4J (a pseudo-Boolean SAT solver) in computational experiments, which show that our algorithm significantly outperforms SAT4J for many instances of WSP. User-independent constraints, a large class of constraints including many practical ones, are a special case of class-independent constraints for which WSP was proved to be FPT (Cohen {\em et al.}, J. Artif. Intel. Res. 2014). Thus our results considerably extend our knowledge of the fixed-parameter tractability of WSP.

Optimal Constructions for Chain-based Cryptographic Enforcement of Information Flow Policies

The simple security property in an information flow policy can be enforced by encrypting data objects and distributing an appropriate secret to each user. A user derives a suitable decryption key from the secret and publicly available information. A chain-based enforcement scheme provides an alternative method of cryptographic enforcement that does not require any public information, the trade-off being that a user may require more than one secret. For a given information flow policy, there will be many different possible chain-based enforcement schemes. In this paper, we provide a polynomial-time algorithm for selecting a chain-based scheme which uses the minimum possible number of keys. We also compute the number of secrets that will be required and establish an upper bound on the number of secrets required by any user.

Pattern Backtracking Algorithm for the Workflow Satisfiability Problem

The workflow satisfiability problem (WSP) asks whether there exists an assignment of authorised users to the steps in a workflow specification, subject to certain constraints on the assignment. (Such an assignment is called valid.) The problem is NP-hard even when restricted to the large class of user-independent constraints. Since the number of steps $k$ is relatively small in practice, it is natural to consider a parametrisation of the WSP by $k$ . We propose a new fixed-parameter algorithm to solve the WSP with user-independent constraints. The assignments in our method are partitioned into equivalence classes such that the number of classes is exponential in $k$ only. We show that one can decide, in polynomial time, whether there is a valid assignment in an equivalence class. By exploiting this property, our algorithm reduces the search space to the space of equivalence classes, which it browses within a backtracking framework, hence emerging as an efficient yet relatively simple-to-implement or generalise solution method. We empirically evaluate our algorithm against the state-of-the-art methods and show that it clearly wins the competition on the whole range of our test problems and significantly extends the domain of practically solvable instances of the WSP.

Structural Parameterizations of the Mixed Chinese Postman Problem

In the Mixed Chinese Postman Problem (MCPP), given a weighted mixed graph $G$ ( $G$ may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP parameterized by the number of edges in $G$ or the number of arcs in $G$ is fixed-parameter tractable as proved by van Bevern {\em et al.} (in press) and Gutin, Jones and Sheng (ESA 2014), respectively. In this paper, we consider the unweighted version of MCPP. Solving an open question of van Bevern {\em et al.} (in press), we show that somewhat unexpectedly MCPP parameterized by the (undirected) treewidth of $G$ is W[1]-hard. In fact, we prove that even the MCPP parameterized by the pathwidth of $G$ is W[1]-hard. On the positive side, we show that the unweighted version of MCPP parameterized by tree-depth is fixed-parameter tractable. We are unaware of any natural graph parameters between pathwidth and tree-depth and so our results provide a dichotomy of the complexity of MCPP. Furthermore, we believe that MCPP is the first problem known to be W[1]-hard with respect to treewidth but FPT with respect to tree-depth.

Tight Lower Bounds for the Workflow Satisfiability Problem Based on the Strong Exponential Time Hypothesis

The Workflow Satisfiability Problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification, subject to certain constraints on the assignment. The problem is NP-hard even when restricted to just not equals constraints. Since the number of steps $k$ is relatively small in practice, Wang and Li (2010) introduced a parametrisation of WSP by $k$ . Wang and Li (2010) showed that, in general, the WSP is W[1]-hard, i.e., it is unlikely that there exists a fixed-parameter tractable (FPT) algorithm for solving the WSP. Crampton et al. (2013) and Cohen et al. (2014) designed FPT algorithms of running time $O^*(2^{k})$ and $O^*(2^{k\log_2 k})$ for the WSP with so-called regular and user-independent constraints, respectively. In this note, we show that there are no algorithms of running time $O^*(2^{ck})$ and $O^*(2^{ck\log_2 k})$ for the two restrictions of WSP, respectively, with any $c<1$ , unless the Strong Exponential Time Hypothesis fails.

Iterative Plan Construction for the Workflow Satisfiability Problem

The \emph{Workflow Satisfiability Problem (WSP)} is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a \emph{plan} -- an assignment of tasks to authorized users -- such that all constraints are satisfied. Several bespoke algorithms have been constructed for solving the WSP, optimised to deal with constraints (business rules) of particular types. It is natural to see the WSP as a subclass of the {\em Constraint Satisfaction Problem (CSP)} in which the variables are tasks and the domain is the set of users. What makes the WSP distinctive as a CSP is that we can assume that the number of tasks is very small compared to the number of users. This is in sharp contrast with traditional CSP models where the domain is small and the number of variables is very large. As such, it is appropriate to ask for which constraint languages the WSP is fixed-parameter tractable (FPT), parameterized by the number of tasks. We have identified a new FPT constraint language, user-independent constraint, that includes many of the constraints of interest in business processing systems. We are also able to prove that the union of FPT languages remains FPT if they satisfy a simple compatibility condition. In this paper we present our generic algorithm, in which plans are grouped into equivalence classes, each class being associated with a \emph{pattern}. We demonstrate that our generic algorithm has running time $O^*(2^{k\log k})$ , where $k$ is the number of tasks, for the language of user-independent constraints. We also show that there is no algorithm of running time $O^*(2^{o(k\log k)})$ for user-independent constraints unless the Exponential Time Hypothesis fails.

Parameterized Algorithms for Load Coloring Problem

One way to state the Load Coloring Problem (LCP) is as follows. Let $G=(V,E)$ be graph and let $f:V\rightarrow \{{\rm red}, {\rm blue}\}$ be a 2-coloring. An edge $e\in E$ is called red (blue) if both end-vertices of $e$ are red (blue). For a 2-coloring $f$ , let $r'_f$ and $b'_f$ be the number of red and blue edges and let $μ_f(G)=\min\{r'_f,b'_f\}$ . Let $μ(G)$ be the maximum of $μ_f(G)$ over all 2-colorings. We introduce the parameterized problem $k$ -LCP of deciding whether $μ(G)\ge k$ , where $k$ is the parameter. We prove that this problem admits a kernel with at most $7k$ . Ahuja et al. (2007) proved that one can find an optimal 2-coloring on trees in polynomial time. We generalize this by showing that an optimal 2-coloring on graphs with tree decomposition of width $t$ can be found in time $O^*(2^t)$ . We also show that either $G$ is a Yes-instance of $k$ -LCP or the treewidth of $G$ is at most $2k$ . Thus, $k$ -LCP can be solved in time $O^*(4^k).$

Parameterized Directed $k$ -Chinese Postman Problem and $k$ Arc-Disjoint Cycles Problem on Euler Digraphs

In the Directed $k$ -Chinese Postman Problem ( $k$ -DCPP), we are given a connected weighted digraph $G$ and asked to find $k$ non-empty closed directed walks covering all arcs of $G$ such that the total weight of the walks is minimum. Gutin, Muciaccia and Yeo (Theor. Comput. Sci. 513 (2013) 124--128) asked for the parameterized complexity of $k$ -DCPP when $k$ is the parameter. We prove that the $k$ -DCPP is fixed-parameter tractable. We also consider a related problem of finding $k$ arc-disjoint directed cycles in an Euler digraph, parameterized by $k$ . Slivkins (ESA 2003) showed that this problem is W[1]-hard for general digraphs. Generalizing another result by Slivkins, we prove that the problem is fixed-parameter tractable for Euler digraphs. The corresponding problem on vertex-disjoint cycles in Euler digraphs remains W[1]-hard even for Euler digraphs.

Parameterized Rural Postman Problem

The Directed Rural Postman Problem (DRPP) can be formulated as follows: given a strongly connected directed multigraph $D=(V,A)$ with nonnegative integral weights on the arcs, a subset $R$ of $A$ and a nonnegative integer $\ell$ , decide whether $D$ has a closed directed walk containing every arc of $R$ and of total weight at most $\ell$ . Let $k$ be the number of weakly connected components in the the subgraph of $D$ induced by $R$ . Sorge et al. (2012) ask whether the DRPP is fixed-parameter tractable (FPT) when parameterized by $k$ , i.e., whether there is an algorithm of running time $O^*(f(k))$ where $f$ is a function of $k$ only and the $O^*$ notation suppresses polynomial factors. Sorge et al. (2012) note that this question is of significant practical relevance and has been open for more than thirty years. Using an algebraic approach, we prove that DRPP has a randomized algorithm of running time $O^*(2^k)$ when $\ell$ is bounded by a polynomial in the number of vertices in $D$ . We also show that the same result holds for the undirected version of DRPP, where $D$ is a connected undirected multigraph.

Parameterized TSP: Beating the Average

In the Travelling Salesman Problem (TSP), we are given a complete graph $K_n$ together with an integer weighting $w$ on the edges of $K_n$ , and we are asked to find a Hamilton cycle of $K_n$ of minimum weight. Let $h(w)$ denote the average weight of a Hamilton cycle of $K_n$ for the weighting $w$ . Vizing (1973) asked whether there is a polynomial-time algorithm which always finds a Hamilton cycle of weight at most $h(w)$ . He answered this question in the affirmative and subsequently Rublineckii (1973) and others described several other TSP heuristics satisfying this property. In this paper, we prove a considerable generalisation of Vizing's result: for each fixed $k$ , we give an algorithm that decides whether, for any input edge weighting $w$ of $K_n$ , there is a Hamilton cycle of $K_n$ of weight at most $h(w)-k$ (and constructs such a cycle if it exists). For $k$ fixed, the running time of the algorithm is polynomial in $n$ , where the degree of the polynomial does not depend on $k$ (i.e., the generalised Vizing problem is fixed-parameter tractable with respect to the parameter $k$ ).

Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem

The Workflow Satisfiability Problem (WSP) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan -- an assignment of tasks to authorized users -- such that all constraints are satisfied. The WSP is, in fact, the conservative Constraint Satisfaction Problem (i.e., for each variable, here called task, we have a unary authorization constraint) and is, thus, NP-complete. It was observed by Wang and Li (2010) that the number k of tasks is often quite small and so can be used as a parameter, and several subsequent works have studied the parameterized complexity of WSP regarding parameter k. We take a more detailed look at the kernelization complexity of WSP(Γ) when Γ denotes a finite or infinite set of allowed constraints. Our main result is a dichotomy for the case that all constraints in Γ are regular: (1) We are able to reduce the number n of users to n' <= k. This entails a kernelization to size poly(k) for finite Γ, and, under mild technical conditions, to size poly(k+m) for infinite Γ, where m denotes the number of constraints. (2) Already WSP(R) for some R \in Γ allows no polynomial kernelization in k+m unless the polynomial hierarchy collapses.

Betweenness Parameterized Above Tight Lower Bound

We study ordinal embedding relaxations in the realm of parameterized complexity. We prove the existence of a quadratic kernel for the {\sc Betweenness} problem parameterized above its tight lower bound, which is stated as follows. For a set $V$ of variables and set $\mathcal C$ of constraints " $v_i$ \mbox{is between} $v_j$ \mbox{and} $v_k$ ", decide whether there is a bijection from $V$ to the set $\{1,\ldots,|V|\}$ satisfying at least $|\mathcal C|/3 + κ$ of the constraints in $\mathcal C$ . Our result solves an open problem attributed to Benny Chor in Niedermeier's monograph "Invitation to Fixed-Parameter Algorithms." The betweenness problem is of interest in molecular biology. An approach developed in this paper can be used to determine parameterized complexity of a number of other optimization problems on permutations parameterized above or below tight bounds.

Constraint Expressions and Workflow Satisfiability

A workflow specification defines a set of steps and the order in which those steps must be executed. Security requirements and business rules may impose constraints on which users are permitted to perform those steps. A workflow specification is said to be satisfiable if there exists an assignment of authorized users to workflow steps that satisfies all the constraints. An algorithm for determining whether such an assignment exists is important, both as a static analysis tool for workflow specifications, and for the construction of run-time reference monitors for workflow management systems. We develop new methods for determining workflow satisfiability based on the concept of constraint expressions, which were introduced recently by Khan and Fong. These methods are surprising versatile, enabling us to develop algorithms for, and determine the complexity of, a number of different problems related to workflow satisfiability.

On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem

A workflow specification defines a set of steps and the order in which those steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of those steps. A workflow specification is said to be satisfiable if there exists an assignment of users to workflow steps that satisfies all the constraints. An algorithm for determining whether such an assignment exists is important, both as a static analysis tool for workflow specifications, and for the construction of run-time reference monitors for workflow management systems. Finding such an assignment is a hard problem in general, but work by Wang and Li in 2010 using the theory of parameterized complexity suggests that efficient algorithms exist under reasonable assumptions about workflow specifications. In this paper, we improve the complexity bounds for the workflow satisfiability problem. We also generalize and extend the types of constraints that may be defined in a workflow specification and prove that the satisfiability problem remains fixed-parameter tractable for such constraints. Finally, we consider preprocessing for the problem and prove that in an important special case, in polynomial time, we can reduce the given input into an equivalent one, where the number of users is at most the number of steps. We also show that no such reduction exists for two natural extensions of this case, which bounds the number of users by a polynomial in the number of steps, provided a widely-accepted complexity-theoretical assumption holds.

Parameterizations of Test Cover with Bounded Test Sizes

In the {\sc Test Cover} problem we are given a hypergraph $H=(V, \mathcal{E})$ with $|V|=n, |\mathcal{E}|=m$ , and we assume that $\mathcal{E}$ is a test cover, i.e. for every pair of vertices $x_i, x_j$ , there exists an edge $e \in \mathcal{E}$ such that $|{x_i,x_j}\cap e|=1$ . The objective is to find a minimum subset of $\mathcal{E}$ which is a test cover. The problem is used for identification across many areas, and is NP-complete. From a parameterized complexity standpoint, many natural parameterizations of {\sc Test Cover} are either $W[1]$ -complete or have no polynomial kernel unless $coNP\subseteq NP/poly$ , and thus are unlikely to be solveable efficiently. However, in practice the size of the edges is often bounded. In this paper we study the parameterized complexity of {\sc Test- $r$ -Cover}, the restriction of {\sc Test Cover} in which each edge contains at most $r \ge 2$ vertices. In contrast to the unbounded case, we show that the following below-bound parameterizations of {\sc Test- $r$ -Cover} are fixed-parameter tractable with a polynomial kernel: (1) Decide whether there exists a test cover of size $n-k$ , and (2) decide whether there exists a test cover of size $m-k$ , where $k$ is the parameter. In addition, we prove a new lower bound $\lceil \frac{2(n-1)}{r+1} \rceil$ on the minimum size of a test cover when the size of each edge is bounded by $r$ . {\sc Test- $r$ -Cover} parameterized above this bound is unlikely to be fixed-parameter tractable; in fact, we show that it is para-NP-complete, as it is NP-hard to decide whether an instance of {\sc Test- $r$ -Cover} has a test cover of size exactly $\frac{2(n-1)}{r+1}$ .

Parameterized Complexity of k-Chinese Postman Problem

We consider the following problem called the $k$ -Chinese Postman Problem ( $k$ -CPP): given a connected edge-weighted graph $G$ and integers $p$ and $k$ , decide whether there are at least $k$ closed walks such that every edge of $G$ is contained in at least one of them and the total weight of the edges in the walks is at most $p$ ? The problem $k$ -CPP is NP-complete, and van Bevern et al. (to appear) and Sorge (2013) asked whether the $k$ -CPP is fixed-parameter tractable when parameterized by $k$ . We prove that the $k$ -CPP is indeed fixed-parameter tractable. In fact, we prove a stronger result: the problem admits a kernel with $O(k^2\log k)$ vertices. We prove that the directed version of $k$ -CPP is NP-complete and ask whether the directed version is fixed-parameter tractable when parameterized by $k$ .

A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application

Let F be a CNF formula with n variables and m clauses. F is 3-satisfiable if for any 3 clauses in F, there is a truth assignment which satisfies all of them. Lieberherr and Specker (1982) and, later, Yannakakis (1994) proved that in each 3-satisfiable CNF formula at least 2/3 of its clauses can be satisfied by a truth assignment. We improve this result by showing that every 3-satisfiable CNF formula F contains a subset of variables U, such that some truth assignment $τ$ will satisfy at least $2m/3+ m_U/3+ρn'$ clauses, where m is the number of clauses of F, m_U is the number of clauses of F containing a variable from U, n' is the total number of variables in clauses not containing a variable in U, and ρis a positive absolute constant. Both U and $τ$ can be found in polynomial time. We use our result to show that the following parameterized problem is fixed-parameter tractable and, moreover, has a kernel with a linear number of variables. In 3-S-MAXSAT-AE, we are given a 3-satisfiable CNF formula F with m clauses and asked to determine whether there is an assignment which satisfies at least 2m/3 + k clauses, where k is the parameter.

Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound

An oriented graph is a directed graph without directed 2-cycles. Poljak and Turzík (1986) proved that every connected oriented graph $G$ on $n$ vertices and $m$ arcs contains an acyclic subgraph with at least $\frac{m}{2}+\frac{n-1}{4}$ arcs. Raman and Saurabh (2006) gave another proof of this result and left it as an open question to establish the parameterized complexity of the following problem: does $G$ have an acyclic subgraph with least $\frac{m}{2}+\frac{n-1}{4}+k$ arcs, where $k$ is the parameter? We answer this question by showing that the problem can be solved by an algorithm of runtime $(12k)!n^{O(1)}$ . Thus, the problem is fixed-parameter tractable. We also prove that there is a polynomial time algorithm that either establishes that the input instance of the problem is a Yes-instance or reduces the input instance to an equivalent one of size $O(k^2)$ .

Efficient Local Search Algorithms for Known and New Neighborhoods for the Generalized Traveling Salesman Problem

The Generalized Traveling Salesman Problem (GTSP) is a well-known combinatorial optimization problem with a host of applications. It is an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into so-called clusters, and the salesman has to visit every cluster exactly once. While the GTSP is a very important combinatorial optimization problem and is well studied in many aspects, the local search algorithms used in the literature are mostly basic adaptations of simple TSP heuristics. Hence, a thorough and deep research of the neighborhoods and local search algorithms specific to the GTSP is required. We formalize the procedure of adaptation of a TSP neighborhood for the GTSP and classify all other existing and some new GTSP neighborhoods. For every neighborhood, we provide efficient exploration algorithms that are often significantly faster than the ones known from the literature. Finally, we compare different local search implementations empirically.

Hypercontractive Inequality for Pseudo-Boolean Functions of Bounded Fourier Width

A function $f:\ \{-1,1\}^n\rightarrow \mathbb{R}$ is called pseudo-Boolean. It is well-known that each pseudo-Boolean function $f$ can be written as $f(x)=\sum_{I\in {\cal F}}\hat{f}(I)χ_I(x),$ where ${\cal F}\subseteq \{I:\ I\subseteq [n]\}$ , $[n]=\{1,2,...,n\}$ , and $χ_I(x)=\prod_{i\in I}x_i$ and $\hat{f}(I)$ are non-zero reals. The degree of $f$ is $\max \{|I|:\ I\in {\cal F}\}$ and the width of $f$ is the minimum integer $ρ$ such that every $i\in [n]$ appears in at most $ρ$ sets in $\cal F$ . For $i\in [n]$ , let $\mathbf{x}_i$ be a random variable taking values 1 or -1 uniformly and independently from all other variables $\mathbf{x}_j$ , $j\neq i.$ Let $\mathbf{x}=(\mathbf{x}_1,...,\mathbf{x}_n)$ . The $p$ -norm of $f$ is $||f||_p=(\mathbb E[|f(\mathbf{x})|^p])^{1/p}$ for any $p\ge 1$ . It is well-known that $||f||_q\ge ||f||_p$ whenever $q> p\ge 1$ . However, the higher norm can be bounded by the lower norm times a coefficient not directly depending on $f$ : if $f$ is of degree $d$ and $q> p>1$ then $||f||_q\le (\frac{q-1}{p-1})^{d/2}||f||_p.$ This inequality is called the Hypercontractive Inequality. We show that one can replace $d$ by $ρ$ in the Hypercontractive Inequality for each $q> p\ge 2$ as follows: $||f||_q\le ((2r)!ρ^{r-1})^{1/(2r)}||f||_p,$ where $r=\lceil q/2\rceil$ . For the case $q=4$ and $p=2$ , which is important in many applications, we prove a stronger inequality: $||f||_4\le (2ρ+1)^{1/4}||f||_2.$

Note on Existence and Non-Existence of Large Subsets of Binary Vectors with Similar Distances

We consider vectors from $\{0,1\}^n$ . The weight of such a vector $v$ is the sum of the coordinates of $v$ . The distance ratio of a set $L$ of vectors is ${\rm dr}(L):=\max \{ρ(x,y):\ x,y \in L\}/ \min \{ρ(x,y):\ x,y \in L,\ x\neq y\},$ where $ρ(x,y)$ is the Hamming distance between $x$ and $y$ . We prove that (a) for every constant $λ>1$ there are no positive constants $α$ and $C$ such that every set $K$ of at least $λ^p$ vectors with weight $p$ contains a subset $K'$ with $|K'|\ge |K|^α$ and ${\rm dr}(K')\le C$ , % even when $|K|\ge λ$ , (b) For a set $K$ of vectors with weight $p$ , and a constant $C>2$ , there exists $K'\subseteq K$ such that ${\rm dr}(K')\le C$ and $|K'| \ge |K|^α$ , where $α= 1/ \lceil \log(p/2)/\log(C/2) \rceil$ .

All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Kernels with Quadratic Numbers of Variables

A ternary Permutation-CSP is specified by a subset $Π$ of the symmetric group $\mathcal S_3$ . An instance of such a problem consists of a set of variables $V$ and a multiset of constraints, which are ordered triples of distinct variables of $V.$ The objective is to find a linear ordering $α$ of $V$ that maximizes the number of triples whose ordering (under $α$ ) follows a permutation in $Π$ . We prove that all ternary Permutation-CSPs parameterized above average have kernels with quadratic numbers of variables.

Kernels for Below-Upper-Bound Parameterizations of the Hitting Set and Directed Dominating Set Problems

In the {\sc Hitting Set} problem, we are given a collection $\cal F$ of subsets of a ground set $V$ and an integer $p$ , and asked whether $V$ has a $p$ -element subset that intersects each set in $\cal F$ . We consider two parameterizations of {\sc Hitting Set} below tight upper bounds: $p=m-k$ and $p=n-k$ . In both cases $k$ is the parameter. We prove that the first parameterization is fixed-parameter tractable, but has no polynomial kernel unless coNP $\subseteq$ NP/poly. The second parameterization is W[1]-complete, but the introduction of an additional parameter, the degeneracy of the hypergraph $H=(V,{\cal F})$ , makes the problem not only fixed-parameter tractable, but also one with a linear kernel. Here the degeneracy of $H=(V,{\cal F})$ is the minimum integer $d$ such that for each $X\subset V$ the hypergraph with vertex set $V\setminus X$ and edge set containing all edges of $\cal F$ without vertices in $X$ , has a vertex of degree at most $d.$ In {\sc Nonblocker} ({\sc Directed Nonblocker}), we are given an undirected graph (a directed graph) $G$ on $n$ vertices and an integer $k$ , and asked whether $G$ has a set $X$ of $n-k$ vertices such that for each vertex $y\not\in X$ there is an edge (arc) from a vertex in $X$ to $y$ . {\sc Nonblocker} can be viewed as a special case of {\sc Directed Nonblocker} (replace an undirected graph by a symmetric digraph). Dehne et al. (Proc. SOFSEM 2006) proved that {\sc Nonblocker} has a linear-order kernel. We obtain a linear-order kernel for {\sc Directed Nonblocker}.

Parameterized Complexity of MaxSat Above Average

In MaxSat, we are given a CNF formula $F$ with $n$ variables and $m$ clauses and asked to find a truth assignment satisfying the maximum number of clauses. Let $r_1,..., r_m$ be the number of literals in the clauses of $F$ . Then $asat(F)=\sum_{i=1}^m (1-2^{-r_i})$ is the expected number of clauses satisfied by a random truth assignment (the truth values to the variables are distributed uniformly and independently). It is well-known that, in polynomial time, one can find a truth assignment satisfying at least $asat(F)$ clauses. In the parameterized problem MaxSat-AA, we are to decide whether there is a truth assignment satisfying at least $asat(F)+k$ clauses, where $k$ is the parameter. We prove that MaxSat-AA is para-NP-complete and, thus, MaxSat-AA is not fixed-parameter tractable unless P $=$ NP. This is in sharp contrast to MaxLin2-AA which was recently proved to be fixed-parameter tractable by Crowston et al. (arXiv:1104.1135v3). In fact, we consider a more refined version of {\sc MaxSat-AA}, {\sc Max- $r(n)$ -Sat-AA}, where $r_j\le r(n)$ for each $j$ . Alon {\em et al.} (SODA 2010) proved that if $r=r(n)$ is a constant, then {\sc Max- $r$ -Sat-AA} is fixed-parameter tractable. We prove that {\sc Max- $r(n)$ -Sat-AA} is para-NP-complete for $r(n)=\lceil \log n\rceil.$ We also prove that assuming the exponential time hypothesis, {\sc Max- $r(n)$ -Sat-AA} is not in XP already for any $r(n)\ge \log \log n +ϕ(n)$ , where $ϕ(n)$ is any unbounded strictly increasing function. This lower bound on $r(n)$ cannot be decreased much further as we prove that {\sc Max- $r(n)$ -Sat-AA} is (i) in XP for any $r(n)\le \log \log n - \log \log \log n$ and (ii) fixed-parameter tractable for any $r(n)\le \log \log n - \log \log \log n - ϕ(n)$ , where $ϕ(n)$ is any unbounded strictly increasing function. The proof uses some results on {\sc MaxLin2-AA}.

Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming

The NP-hard general factor problem asks, given a graph and for each vertex a list of integers, whether the graph has a spanning subgraph where each vertex has a degree that belongs to its assigned list. The problem remains NP-hard even if the given graph is bipartite with partition U+V, and each vertex in U is assigned the list {1}; this subproblem appears in the context of constraint programming as the consistency problem for the extended global cardinality constraint. We show that this subproblem is fixed-parameter tractable when parameterized by the size of the second partite set V. More generally, we show that the general factor problem for bipartite graphs, parameterized by |V|, is fixed-parameter tractable as long as all vertices in U are assigned lists of length 1, but becomes W[1]-hard if vertices in U are assigned lists of length at most 2. We establish fixed-parameter tractability by reducing the problem instance to a bounded number of acyclic instances, each of which can be solved in polynomial time by dynamic programming.

Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments

In the problem {\sc Min-DESC}, we are given a digraph $D$ and an integer $k$ , and asked if there exists a set $A'$ of at most $k$ arcs in $D$ , such that if we remove the arcs of $A'$ , in the resulting digraph every strong component is Eulerian. {\sc Min-DESC} is NP-hard; Cechlárová and Schlotter (IPEC 2010) asked if the problem is fixed-parameter tractable when parameterized by $k$ . We consider the subproblem of{\sc Min-DESC} when $D$ is a tournament. We show that this problem is fixed-parameter tractable with respect to $k$ .

Solving MAX-r-SAT Above a Tight Lower Bound

We present an exact algorithm that decides, for every fixed $r \geq 2$ in time $O(m) + 2^{O(k^2)}$ whether a given multiset of $m$ clauses of size $r$ admits a truth assignment that satisfies at least $((2^r-1)m+k)/2^r$ clauses. Thus \textsc{Max- $r$ -Sat} is fixed-parameter tractable when parameterized by the number of satisfied clauses above the tight lower bound $(1-2^{-r})m$ . This solves an open problem of Mahajan et al. (J. Comput. System Sci., 75, 2009). Our algorithm is based on a polynomial-time data reduction procedure that reduces a problem instance to an equivalent algebraically represented problem with $O(k^2)$ variables. This is done by representing the instance as an appropriate polynomial, and by applying a probabilistic argument combined with some simple tools from Harmonic analysis to show that if the polynomial cannot be reduced to one of size $O(k^2)$ , then there is a truth assignment satisfying the required number of clauses. We introduce a new notion of bikernelization from a parameterized problem to another one and apply it to prove that the above-mentioned parameterized \textsc{Max- $r$ -Sat} admits a polynomial-size kernel. Combining another probabilistic argument with tools from graph matching theory and signed graphs, we show that if an instance of \textsc{Max-2-Sat} with $m$ clauses has at least $3k$ variables after application of certain polynomial time reduction rules to it, then there is a truth assignment that satisfies at least $(3m+k)/4$ clauses. We also outline how the fixed-parameter tractability and polynomial-size kernel results on \textsc{Max- $r$ -Sat} can be extended to more general families of Boolean Constraint Satisfaction Problems.

A characterization of horizontal visibility graphs and combinatorics on words

An Horizontal Visibility Graph (for short, HVG) is defined in association with an ordered set of non-negative reals. HVGs realize a methodology in the analysis of time series, their degree distribution being a good discriminator between randomness and chaos [B. Luque, et al., Phys. Rev. E 80 (2009), 046103]. We prove that a graph is an HVG if and only if outerplanar and has a Hamilton path. Therefore, an HVG is a noncrossing graph, as defined in algebraic combinatorics [P. Flajolet and M. Noy, Discrete Math., 204 (1999) 203-229]. Our characterization of HVGs implies a linear time recognition algorithm. Treating ordered sets as words, we characterize subfamilies of HVGs highlighting various connections with combinatorial statistics and introducing the notion of a visible pair. With this technique we determine asymptotically the average number of edges of HVGs.

A New Approach to Population Sizing for Memetic Algorithms: A Case Study for the Multidimensional Assignment Problem

Memetic Algorithms are known to be a powerful technique in solving hard optimization problems. To design a memetic algorithm one needs to make a host of decisions; selecting a population size is one of the most important among them. Most algorithms in the literature fix the population size to a certain constant value. This reduces the algorithm's quality since the optimal population size varies for different instances, local search procedures and running times. In this paper we propose an adjustable population size. It is calculated as a function of the running time of the whole algorithm and the average running time of the local search for the given instance. Note that in many applications the running time of a heuristic should be limited and therefore we use this limit as a parameter of the algorithm. The average running time of the local search procedure is obtained during the algorithm's run. Some coefficients which are independent with respect to the instance or the local search are to be tuned before the algorithm run; we provide a procedure to find these coefficients. The proposed approach was used to develop a memetic algorithm for the Multidimensional Assignment Problem (MAP or s-AP in the case of s dimensions) which is an extension of the well-known assignment problem. MAP is NP-hard and has a host of applications. We show that using adjustable population size makes the algorithm flexible to perform well for instances of very different sizes and types and for different running times and local searches. This allows us to select the most efficient local search for every instance type. The results of computational experiments for several instance families and sizes prove that the proposed algorithm performs efficiently for a wide range of the running times and clearly outperforms the state-of-the art 3-AP memetic algorithm being given the same time.

Lin-Kernighan Heuristic Adaptations for the Generalized Traveling Salesman Problem

The Lin-Kernighan heuristic is known to be one of the most successful heuristics for the Traveling Salesman Problem (TSP). It has also proven its efficiency in application to some other problems. In this paper we discuss possible adaptations of TSP heuristics for the Generalized Traveling Salesman Problem (GTSP) and focus on the case of the Lin-Kernighan algorithm. At first, we provide an easy-to-understand description of the original Lin-Kernighan heuristic. Then we propose several adaptations, both trivial and complicated. Finally, we conduct a fair competition between all the variations of the Lin-Kernighan adaptation and some other GTSP heuristics. It appears that our adaptation of the Lin-Kernighan algorithm for the GTSP reproduces the success of the original heuristic. Different variations of our adaptation outperform all other heuristics in a wide range of trade-offs between solution quality and running time, making Lin-Kernighan the state-of-the-art GTSP local search.

Note on Maximal Bisection above Tight Lower Bound

In a graph $G=(V,E)$ , a bisection $(X,Y)$ is a partition of $V$ into sets $X$ and $Y$ such that $|X|\le |Y|\le |X|+1$ . The size of $(X,Y)$ is the number of edges between $X$ and $Y$ . In the Max Bisection problem we are given a graph $G=(V,E)$ and are required to find a bisection of maximum size. It is not hard to see that $\lceil |E|/2 \rceil$ is a tight lower bound on the maximum size of a bisection of $G$ . We study parameterized complexity of the following parameterized problem called Max Bisection above Tight Lower Bound (Max-Bisec-ATLB): decide whether a graph $G=(V,E)$ has a bisection of size at least $\lceil |E|/2 \rceil+k,$ where $k$ is the parameter. We show that this parameterized problem has a kernel with $O(k^2)$ vertices and $O(k^3)$ edges, i.e., every instance of Max-Bisec-ATLB is equivalent to an instance of Max-Bisec-ATLB on a graph with at most $O(k^2)$ vertices and $O(k^3)$ edges.

A Memetic Algorithm for the Generalized Traveling Salesman Problem

The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The recent studies on this subject consider different variations of a memetic algorithm approach to the GTSP. The aim of this paper is to present a new memetic algorithm for GTSP with a powerful local search procedure. The experiments show that the proposed algorithm clearly outperforms all of the known heuristics with respect to both solution quality and running time. While the other memetic algorithms were designed only for the symmetric GTSP, our algorithm can solve both symmetric and asymmetric instances.

A Memetic Algorithm for the Multidimensional Assignment Problem

The Multidimensional Assignment Problem (MAP or s-AP in the case of s dimensions) is an extension of the well-known assignment problem. The most studied case of MAP is 3-AP, though the problems with larger values of s have also a number of applications. In this paper we propose a memetic algorithm for MAP that is a combination of a genetic algorithm with a local search procedure. The main contribution of the paper is an idea of dynamically adjusted generation size, that yields an outstanding flexibility of the algorithm to perform well for both small and large fixed running times. The results of computational experiments for several instance families show that the proposed algorithm produces solutions of very high quality in a reasonable time and outperforms the state-of-the art 3-AP memetic algorithm.

Empirical evaluation of construction heuristics for the multidimensional assignment problem

The multidimensional assignment problem (MAP) (abbreviated s-AP in the case of s dimensions) is an extension of the well-known assignment problem. The most studied case of MAP is 3-AP, though the problems with larger values of s have also a number of applications. In this paper we consider four fast construction heuristics for MAP. One of the heuristics is new. A modification of the heuristics is proposed to optimize the access to slow computer memory. The results of computational experiments for several instance families are provided and discussed.

Generalized Traveling Salesman Problem Reduction Algorithms

The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The aim of this paper is to present a problem reduction algorithm that deletes redundant vertices and edges, preserving the optimal solution. The algorithm's running time is O(N^3) in the worst case, but it is significantly faster in practice. The algorithm has reduced the problem size by 15-20% on average in our experiments and this has decreased the solution time by 10-60% for each of the considered solvers.