Serge Gaspers

TCS Journal 2026 Journal Article

A piecewise approach for the analysis of exact algorithms

• Katie Clinch
• Serge Gaspers
• Zixu He
• Abdallah Saffidine
• Tiankuang Zhang

To analyze the worst-case running time of branching algorithms, the majority of work in exponential time algorithms focuses on designing complicated branching rules over developing better analysis methods for simple algorithms. In the mid-$2000$s, Fomin et al. [2005] introduced measure & conquer, an advanced general analysis method, sparking widespread adoption for obtaining tighter worst-case running time upper bounds for many fundamental NP-complete problems. Yet, much potential in this direction remains untapped, as most subsequent work applied it without further advancement. Motivated by this, we present piecewise analysis, a new general method that analyzes the running time of branching algorithms. Our approach is to define a similarity ratio that divides instances into groups and then analyze the running time within each group separately. The similarity ratio is a scale between two parameters of an instance I. Instead of relying on a single measure and a single analysis for the whole instance space, our method allows to take advantage of different intrinsic properties of instances with different similarity ratios. To showcase its potential, we reanalyze two $17$-year-old algorithms from Fomin et al. [2007] that solve $4$-Coloring and #$3$-Coloring respectively. The original analysis in their paper gave running times of $O(1. 7272^n)$ and $O(1. 6262^n)$ respectively for these algorithms, our analysis improves these running times to $O(1. 7207^n)$ and $O(1. 6225^n)$.

AAAI Conference 2022 Conference Paper

Faster Algorithms for Weak Backdoors

• Serge Gaspers
• Andrew Kaploun

A weak backdoor, or simply a backdoor, for a Boolean SAT formula φ into a class of SAT formulae C is a partial truth assignment τ such that φ[τ] ∈ C and satisfiability is preserved. The problem of finding a backdoor from class C1 into class C2, or WB(C1, C2), can be stated as follows: Given a formula φ ∈ C1, and a natural number k, determine whether there exists a backdoor for φ into C2 assigning at most k variables. The class 0-VAL contains all Boolean formulae with at least one negative literal in each clause. We design a new algorithm for WB(3CNF, 0-VAL) by reducing it to a local search variant of 3-SAT. We show that our algorithm runs in time O∗ (2. 562k ), improving on the previous state-of-the-art of O∗ (2. 85k ). Here, the O∗ notation is a variant of the big-O notation that allows to omit polynomial factors in the input size. Next, we look at WB(3CNF, NULL), where NULL is the class consisting of the empty formula. This problem was known to have a trivial running time upper bound of O∗ (6k ) and can easily be solved in O∗ (3k ) time. We use a reduction to CONFLICT FREE d-HITTING SET to prove an upper bound of O∗ (2. 2738k ), and also prove a lower bound of 2o(k) assuming the Exponential Time Hypothesis. Finally, HORN is the class of formulae with at most one positive literal per clause. We improve the previous O∗ (4. 54k ) running time for WB(3CNF, HORN) problem to O∗ (4. 17k ), by exploiting the structure of the SAT instance to give a novel proof of the non-existence of the slowest cases after a slight restructuring of the branching priorities.

TCS Journal 2022 Journal Article

Stable matching with uncertain pairwise preferences

• Haris Aziz
• Péter Biró
• Tamás Fleiner
• Serge Gaspers
• Ronald de Haan
• Nicholas Mattei
• Baharak Rastegari

We study a two-sided matching problem under preferences, where the agents have independent pairwise comparisons on their possible partners and these preferences may be uncertain. Preferences may be intransitive and agents may even have cycles in their preferences; e. g. an agent a may prefer b to c, c to d, and d to b, all with probability one. If an instance has such a cycle, then there may not exist any matching that is stable with positive probability. We focus on the computational problems of checking the existence of possibly and certainly stable matchings, i. e. , matchings whose probability of being stable is positive or one, respectively. We show that finding possibly stable matchings is NP-hard, even if only one side can have cyclic preferences. On the other hand we show that the problem of finding a certainly stable matching is polynomial-time solvable if only one side can have cyclic preferences and the other side has transitive preferences, but that this problem becomes NP-hard when both sides can have cyclic preferences.

IJCAI Conference 2020 Conference Paper

Mechanism Design for School Choice with Soft Diversity Constraints

• Haris Aziz
• Serge Gaspers
• Zhaohong Sun

We study the controlled school choice problem where students may belong to overlapping types and schools have soft target quotas for each type. We formalize fairness concepts for the setting that extend fairness concepts considered for restricted settings without overlapping types. Our central contribution is presenting a new class of algorithms that takes into account the representations of combinations of student types. The algorithms return matchings that are non-wasteful and satisfy fairness for same types. We further prove that the algorithms are strategyproof for the students and yield a fair outcome with respect to the induced quotas for type combinations. We experimentally compare our algorithms with two existing approaches in terms of achieving diversity goals and satisfying fairness.

MFCS Conference 2019 Conference Paper

Enumeration of Preferred Extensions in Almost Oriented Digraphs

• Serge Gaspers
• Ray Li

In this paper, we present enumeration algorithms to list all preferred extensions of an argumentation framework. This task is equivalent to enumerating all maximal semikernels of a directed graph. For directed graphs on n vertices, all preferred extensions can be enumerated in O^*(3^{n/3}) time and there are directed graphs with Omega(3^{n/3}) preferred extensions. We give faster enumeration algorithms for directed graphs with at most 0. 8004 * n vertices occurring in 2-cycles. In particular, for oriented graphs (digraphs with no 2-cycles) one of our algorithms runs in time O(1. 2321^n), and we show that there are oriented graphs with Omega(3^{n/6}) > Omega(1. 2009^n) preferred extensions. A combination of three algorithms leads to the fastest enumeration times for various proportions of the number of vertices in 2-cycles. The most innovative one is a new 2-stage sampling algorithm, combined with a new parameterized enumeration algorithm, analyzed with a combination of the recent monotone local search technique (STOC 2016) and an extension thereof (ICALP 2017).

IJCAI Conference 2019 Conference Paper

Fair Online Allocation of Perishable Goods and its Application to Electric Vehicle Charging

• Enrico H. Gerding
• Alvaro Perez-Diaz
• Haris Aziz
• Serge Gaspers
• Antonia Marcu
• Nicholas Mattei
• Toby Walsh

We consider mechanisms for the online allocation of perishable resources such as energy or computational power. A main application is electric vehicle charging where agents arrive and leave over time. Unlike previous work, we consider mechanisms without money, and a range of objectives including fairness and efficiency. In doing so, we extend the concept of envy-freeness to online settings. Furthermore, we explore the trade-offs between different objectives and analyse their theoretical properties both in online and offline settings. We then introduce novel online scheduling algorithms and compare them in terms of both their theoretical properties and empirical performance.

AAMAS Conference 2019 Conference Paper

From Matching with Diversity Constraints to Matching with Regional Quotas

• Haris Aziz
• Serge Gaspers
• Zhaohong Sun
• Toby Walsh

In the past few years, several new matching models have been proposed and studied that take into account complex distributional constraints. Relevant lines of work include (1) school choice with diversity constraints where students have (possibly overlapping) types and (2) hospital-doctor matching where various regional quotas are imposed. In this paper, we present a polynomial-time reduction to transform an instance of (1) to an instance of (2) and we show how the feasibility and stability of corresponding matchings are preserved under the reduction. Our reduction provides a formal connection between two important strands of work on matching with distributional constraints. We then apply the reduction in two ways. Firstly, we show that it is NP-complete to check whether a feasible and stable outcome for (1) exists. Due to our reduction, these NP-completeness results carry over to setting (2). In view of this, we help unify some of the results that have been presented in the literature. Secondly, if we have positive results for (2), then we have corresponding results for (1). One key conclusion of our results is that further developments on axiomatic and algorithmic aspects of hospital-doctor matching with regional quotas will result in corresponding results for school choice with diversity constraints.

AAAI Conference 2019 Conference Paper

Optimal Surveillance of Covert Networks by Minimizing Inverse Geodesic Length

• Serge Gaspers
• Kamran Najeebullah

The inverse geodesic length (IGL) is a well-known and widely used measure of network performance. It equals the sum of the inverse distances of all pairs of vertices. In network analysis, IGL of a network is often used to assess and evaluate how well heuristics perform in strengthening or weakening a network. We consider the edge-deletion problem MINIGL- ED. Formally, given a graph G, a budget k, and a target inverse geodesic length T, the question is whether there exists a subset of edges X with |X| ≤ ck, such that the inverse geodesic length of G − X is at most T. In this paper, we design algorithms and study the complexity of MINIGL-ED. We show that it is NP-complete and cannot be solved in subexponential time even when restricted to bipartite or split graphs assuming the Exponential Time Hypothesis. In terms of parameterized complexity, we consider the problem with respect to various parameters. We show that MINIGL-ED is fixed-parameter tractable for parameter T and vertex cover by modeling the problem as an integer quadratic program. We also provide FPT algorithms parameterized by twin cover and neighborhood diversity combined with the deletion budget k. On the negative side we show that MINIGL-ED is W[1]-hard for parameter tree-width.

AAMAS Conference 2018 Conference Paper

Defender Stackelberg Game with Inverse Geodesic Length as Utility Metric

• Haris Aziz
• Serge Gaspers
• Edward J. Lee
• Kamran Najeebullah

The inverse geodesic length (IGL) is a well-known and widely used measure of network performance. It equals the sum of the inverse distances of all pairs of vertices in the network. A Stackelberg game is a strategic game in which one player commits to a strategy while taking into account that other players will respond accordingly. We propose a natural defender-attacker Stackelberg game on a network in which the defender wants to maximize the IGL level of the network and commits to protecting parts of the network while having knowledge of the strength of an attacker that wants to weaken the network. We present several algorithmic and complexity results concerning the problem of finding the optimal commitment for the defender. Some of our computational hardness results also answer open problems posed in prior work on IGL.

AIJ Journal 2018 Journal Article

Fixing balanced knockout and double elimination tournaments

• Haris Aziz
• Serge Gaspers
• Simon Mackenzie
• Nicholas Mattei
• Paul Stursberg
• Toby Walsh

Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. We consider the computational problem of finding the optimal draw for a particular player in such a tournament. The problem has generated considerable research within AI in recent years. We prove that checking whether there exists a draw in which a player wins is NP-complete, thereby settling an outstanding open problem. Our main result has a number of interesting implications on related counting and approximation problems. We present a memoization-based algorithm for the problem that is faster than previous approaches. Moreover, we highlight two natural cases that can be solved in polynomial time. All of our results also hold for the more general problem of counting the number of draws in which a given player is the winner. Finally, we show that our main NP-completeness result extends to a variant of balanced knockout tournaments called double-elimination tournaments.

AAAI Conference 2018 Conference Paper

Minesweeper with Limited Moves

• Serge Gaspers
• Stefan Rümmele
• Abdallah Saffidine
• Kevin Tran

We consider the problem of playing Minesweeper with a limited number of moves: Given a partially revealed board, a number of available clicks k, and a target probability p, can we win with probability p. We win if we do not click on a mine, and, after our sequence of at most k clicks (which reveal information about the neighboring squares) can correctly identify the placement of all mines. We make the assumption, that, at all times, all placements of mines consistent with the currently revealed squares are equiprobable. Our main results are that the problem is PSPACE-complete, and it remains PSPACE-complete when p is a constant, in particular when p = 1. When k = 0 (i. e. , we are not allowed to click anywhere), the problem is PP-complete in general, but co-NP-complete when p is a constant, and in particular when p = 1.

AAMAS Conference 2018 Conference Paper

Stability and Pareto Optimality in Refugee Allocation Matchings

• Haris Aziz
• Jiayin Chen
• Serge Gaspers
• Zhaohong Sun

We focus on the refugee matching problem—a general “two-sided matching under preferences” model with multi-dimensional feasibility constraints. We propose a taxonomy of stability concepts for the problem; identify relations between them; and show that even for two natural weakenings of the standard stability concept, non-existence and NP-hardness results persist. We then identify several natural weaker stability concepts for which we present a polynomial-time and strategy-proof algorithm that returns a stable matching. We also examine the complexity of computing and testing Pareto optimal matchings.

AAMAS Conference 2017 Conference Paper

Stable Matching with Uncertain Pairwise Preferences

• Haris Aziz
• Pé ter Biró
• Tamá s Fleiner
• Serge Gaspers
• Ronald de Haan
• Nicholas Mattei
• Baharak Rastegari

We study a two-sided matching problem where the agents have independent pairwise preferences on their possible partners and these preferences may be uncertain. In this case, the certainly preferred part of an agent’s preferences may admit a cycle and there may not even exist a matching that is stable with non-zero probability. We focus on the computational problems of checking the existence of possibly and certainly stable matchings, i. e. , matchings whose probability of being stable is positive or one, respectively. We show that finding a possibly stable matching is NP-hard, even if only one side can have cyclic preferences. On the other hand we show that the problem of finding a certainly stable matching is polynomial-time solvable if only one side can have cyclic preferences and the other side has transitive preferences, but that this problem becomes NP-hard when both sides can have cyclic preferences. The latter complexity result also implies the hardness of finding a kernel in a special class of directed graphs. CCS Concepts •Theory of computation! Design and analysis of algorithms; •Computing methodologies! Multi-agent systems; •Applied computing! Economics;

IJCAI Conference 2017 Conference Paper

Weakening Covert Networks by Minimizing Inverse Geodesic Length

• Haris Aziz
• Serge Gaspers
• Kamran Najeebullah

We consider the problem of deleting nodes in a covert network to minimize its performance. The inverse geodesic length (IGL) is a well-known and widely used measure of network performance. It equals the sum of the inverse distances of all pairs of vertices. In the MinIGL problem the input is a graph $G$, a budget $k$, and a target IGL $T$, and the question is whether there exists a subset of vertices $X$ with $|X|=k$, such that the IGL of $G-X$ is at most $T$. In network analysis, the IGL is often used to evaluate how well heuristics perform in strengthening or weakening a network. In this paper, we undertake a study of the classical and parameterized complexity of the MinIGL problem. The problem is NP-complete even if $T=0$ and remains both NP-complete and $W[1]$-hard for parameter $k$ on bipartite and on split graphs. On the positive side, we design several multivariate algorithms for the problem. Our main result is an algorithm for MinIGL parameterized by the twin cover number.

STOC Conference 2016 Conference Paper

Exact algorithms via monotone local search

• Fedor V. Fomin
• Serge Gaspers
• Daniel Lokshtanov
• Saket Saurabh 0001

We give a new general approach for designing exact exponential-time algorithms for subset problems . In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to determine whether the family contains at least one set. A typical example of a subset problem is Weighted d -SAT. Here, the input is a CNF-formula with clauses of size at most d , and an integer W . The universe is the set of variables and the variables have integer weights. The family contains all the subsets S of variables such that the total weight of the variables in S does not exceed W , and setting the variables in S to 1 and the remaining variables to 0 satisfies the formula. Our approach is based on “monotone local search”, where the goal is to extend a partial solution to a solution by adding as few elements as possible. More formally, in the extension problem we are also given as input a subset X of the universe and an integer k . The task is to determine whether one can add at most k elements to X to obtain a set in the (implicitly defined) family. Our main result is that a c k n O (1) time algorithm for the extension problem immediately yields a randomized algorithm for finding a solution of any size with running time O ((2−1/ c ) n ).

IJCAI Conference 2016 Conference Paper

Interdependent Scheduling Games

• Andres Abeliuk
• Haris Aziz
• Gerardo Berbeglia
• Serge Gaspers
• Petr Kalina
• Nicholas Mattei
• Dominik Peters
• Paul Stursberg

We propose a model of interdependent scheduling games in which each player controls a set of services that they schedule independently. A player is free to schedule his own services at any time; however, each of these services only begins to accrue reward for the player when all predecessor services, which may or may not be controlled by the same player, have been activated. This model, where players have interdependent services, is motivated by the problems faced in planning and coordinating large-scale infrastructures, e. g. , restoring electricity and gas to residents after a natural disaster or providing medical care in a crisis when different agencies are responsible for the delivery of staff, equipment, and medicine. We undertake a game-theoretic analysis of this setting and in particular consider the issues of welfare maximization, computing best responses, Nash dynamics, and existence and computation of Nash equilibria.

Highlights Conference 2016 Conference Abstract

On the Complexity of Grammar-Based Compression over Fixed Alphabets

• Katrin Casel
• Henning Fernau
• Serge Gaspers
• Benjamin Gras
• Markus L. Schmid

This talk is based on the following paper: Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid. On the Complexity of Grammar-Based Compression over Fixed Alphabets. 43rd International Colloquium on Automata, Languages, and Programming 2016, ICALP 2016. We investigate the complexity of grammar-based compression, i. e. , to compress a word by a context-free grammar. It is shown that the shortest-grammar problem remains NP-complete if the alphabet is fixed and has a size of at least 24 (which settles an open question). On the other hand, this problem can be solved in polynomial-time, if the number of nonterminals is bounded, which is shown by encoding the problem as a problem on graphs with interval structure. Furthermore, we present an O(3^n) exact exponential-time algorithm, based on dynamic programming. Similar results are also given for 1-level grammars, i. e. , grammars for which only the start rule contains nonterminals on the right side (thus, investigating the impact of the “hierarchical depth” on the complexity of the shortest-grammar problem).

IJCAI Conference 2015 Conference Paper

Equilibria Under the Probabilistic Serial Rule

• Haris Aziz
• Serge Gaspers
• Simon Mackenzie
• Nicholas Mattei
• Nina Narodytska
• Toby Walsh

The probabilistic serial (PS) rule is a prominent randomized rule for assigning indivisible goods to agents. Although it is well known for its good fairness and welfare properties, it is not strategyproof. In view of this, we address several fundamental questions regarding equilibria under PS. Firstly, we show that Nash deviations under the PS rule can cycle. Despite the possibilities of cycles, we prove that a pure Nash equilibrium is guaranteed to exist under the PS rule. We then show that verifying whether a given profile is a pure Nash equilibrium is coNP-complete, and computing a pure Nash equilibrium is NP-hard. For two agents, we present a linear-time algorithm to compute a pure Nash equilibrium which yields the same assignment as the truthful profile. Finally, we conduct experiments to evaluate the quality of the equilibria that exist under the PS rule, finding that the vast majority of pure Nash equilibria yield social welfare that is at least that of the truthful profile.

AIJ Journal 2015 Journal Article

Fair assignment of indivisible objects under ordinal preferences

• Haris Aziz
• Serge Gaspers
• Simon Mackenzie
• Toby Walsh

We consider the discrete assignment problem in which agents express ordinal preferences over objects and these objects are allocated to the agents in a fair manner. We use the stochastic dominance relation between fractional or randomized allocations to systematically define varying notions of proportionality and envy-freeness for discrete assignments. The computational complexity of checking whether a fair assignment exists is studied for these fairness notions. We also characterize the conditions under which a fair assignment is guaranteed to exist. For a number of fairness concepts, polynomial-time algorithms are presented to check whether a fair assignment exists. Our algorithmic results also extend to the case of unequal entitlements of agents. Our NP-hardness result, which holds for several variants of envy-freeness, answers an open question posed by Bouveret, Endriss, and Lang (ECAI 2010). We also propose fairness concepts that always suggest a non-empty set of assignments with meaningful fairness properties. Among these concepts, optimal proportionality and optimal weak proportionality appear to be desirable fairness concepts.

TCS Journal 2015 Journal Article

On finding optimal polytrees

• Serge Gaspers
• Mikko Koivisto
• Mathieu Liedloff
• Sebastian Ordyniak
• Stefan Szeider

We study the NP-hard problem of finding a directed acyclic graph (DAG) on a given set of nodes so as to maximize a given scoring function. The problem models the task of inferring a probabilistic network from data, which has been studied extensively in the fields of artificial intelligence and machine learning. Several variants of the problem, where the output DAG is constrained in several ways, are NP-hard as well, for example when the DAG is required to have bounded in-degree, or when it is required to be a polytree. Polynomial-time algorithms are known only for rare special cases, perhaps most notably for branchings, that is, polytrees in which the in-degree of every node is at most one. In this paper, we generalize this polynomial-time result to polytrees that can be turned into a branching by deleting a constant number of arcs. Our algorithm stems from a matroid intersection formulation. As the order of the polynomial time bound depends on the number of deleted arcs, the algorithm does not establish fixed-parameter tractability when parameterized by that number. We show that certain additional constraints on the sought polytree render the problem fixed-parameter tractable. We contrast this positive result by showing that if we parameterize by the number of deleted nodes, a somewhat more powerful parameter, the problem is not fixed-parameter tractable, subject to a complexity-theoretic assumption.

IJCAI Conference 2015 Conference Paper

Online Fair Division: Analysing a Food Bank Problem

• Martin Damyanov Aleksandrov
• Haris Aziz
• Serge Gaspers
• Toby Walsh

We study an online model of fair division designed to capture features of a real world charity problem. We consider two simple mechanisms for this model in which agents simply declare what items they like. We analyse axiomatic properties of these mechanisms such as strategy-proofness and envy freeness. Finally, we perform a competitive analysis and compute the price of anarchy.

IJCAI Conference 2015 Conference Paper

Welfare Maximization in Fractional Hedonic Games

• Haris Aziz
• Serge Gaspers
• Joachim Gudmundsson
• Julian Mestre
• Hanjo Taubig

We consider the computational complexity of computing welfare maximizing partitions for fractional hedonic games—a natural class of coalition formation games that can be succinctly represented by a graph. For such games, welfare maximizing partitions constitute desirable ways to cluster the vertices of the graph. We present both intractability results and approximation algorithms for computing welfare maximizing partitions.

AAAI Conference 2014 Conference Paper

Backdoors into Heterogeneous Classes of SAT and CSP

• Serge Gaspers
• Neeldhara Misra
• Sebastian Ordyniak
• Stefan Szeider
• Stanislav Zivny

Backdoor sets represent clever reasoning shortcuts through the search space for SAT and CSP. By instantiating the backdoor variables one reduces the given instance to several easy instances that belong to a tractable class. The overall time needed to solve the instance is exponential in the size of the backdoor set, hence it is a challenging problem to find a small backdoor set if one exists; over the last years this problem has been subject of intensive research. In this paper we extend the classical notion of a strong backdoor set by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. Backdoor sets to heterogeneous base classes can be much smaller than backdoor sets to homogeneous ones, hence they are much more desirable but possibly harder to find. We draw a detailed complexity landscape for the problem of detecting strong backdoor sets into heterogeneous base classes for SAT and CSP. We provide algorithms that establish fixedparameter tractability under natural parameterizations, and we contrast the tractability results with hardness results that pinpoint the theoretical limits. Our results apply to the current state-of-the-art of tractable classes of CSP and SAT that are definable by restricting the constraint language.

AAAI Conference 2014 Conference Paper

Fixing a Balanced Knockout Tournament

• Haris Aziz
• Serge Gaspers
• Simon Mackenzie
• Nicholas Mattei
• Paul Stursberg
• Toby Walsh

Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. We consider the computational problem of finding the optimal draw for a particular player in such a tournament. The problem has generated considerable research within AI in recent years. We prove that checking whether there exists a draw in which a player wins is NP-complete, thereby settling an outstanding open problem. Our main result has a number of interesting implications on related counting and approximation problems. We present a memoization-based algorithm for the problem that is faster than previous approaches. Moreover, we highlight two natural cases that can be solved in polynomial time. All of our results also hold for the more general problem of counting the number of draws in which a given player is the winner.

AIJ Journal 2014 Journal Article

Guarantees and limits of preprocessing in constraint satisfaction and reasoning

• Serge Gaspers
• Stefan Szeider

We present a first theoretical analysis of the power of polynomial-time preprocessing for important combinatorial problems from various areas in AI. We consider problems from Constraint Satisfaction, Global Constraints, Satisfiability, Nonmonotonic and Bayesian Reasoning under structural restrictions. All these problems involve two tasks: (i) identifying the structure in the input as required by the restriction, and (ii) using the identified structure to solve the reasoning task efficiently. We show that for most of the considered problems, task (i) admits a polynomial-time preprocessing to a problem kernel whose size is polynomial in a structural problem parameter of the input, in contrast to task (ii) which does not admit such a reduction to a problem kernel of polynomial size, subject to a complexity theoretic assumption. As a notable exception we show that the consistency problem for the AtMost-NValue constraint admits a polynomial kernel consisting of a quadratic number of variables and domain values. Our results provide a firm worst-case guarantees and theoretical boundaries for the performance of polynomial-time preprocessing algorithms for the considered problems.

TCS Journal 2013 Journal Article

An exponential time 2-approximation algorithm for bandwidth

• Martin Fürer
• Serge Gaspers
• Shiva Prasad Kasiviswanathan

The bandwidth of a graph G on n vertices is the minimum b such that the vertices of G can be labeled from 1 to n such that the labels of every pair of adjacent vertices differ by at most b. In this paper, we present a 2-approximation algorithm for the Bandwidth problem that takes worst-case O ( 1. 979 7 n ) = O ( 3 0. 6217 n ) time and uses polynomial space. This improves both the previous best 2- and 3-approximation algorithms of Cygan et al. which have O ∗ ( 3 n ) and O ∗ ( 2 n ) worst-case running time bounds, respectively. Our algorithm is based on constructing bucket decompositions of the input graph. A bucket decomposition partitions the vertex set of a graph into ordered sets (called buckets) of (almost) equal sizes such that all edges are either incident to vertices in the same bucket or to vertices in two consecutive buckets. The idea is to find the smallest bucket size for which there exists a bucket decomposition. The algorithm uses a divide-and-conquer strategy along with dynamic programming to achieve the improved time bound.

IJCAI Conference 2013 Conference Paper

On the Complexity of Global Scheduling Constraints under Structural Restrictions

• Geoffrey Chu
• Serge Gaspers
• Nina Narodytska
• Andreas Schutt
• Toby Walsh

This paper investigates the manpower allocation problem with time windows and job-teaming constraints (MAPTWTC), a practical scheduling and routing problem that tries to synchronize workers’ schedules to complete all tasks. We first provide an integer programming model for the problem and discuss its properties. Next, we show that tree data structure can be used to represent the MAPTWTC solutions, and its optimal solution can be obtained from one of trees by solving a minimum cost flow model for each worker type. Consequently, we develop for the problem a novel tabu search algorithm employing search operators based on the tree data structure. Finally, we prove the effectiveness of the tabu search algorithm by computational experiments on two sets of instances.

IJCAI Conference 2013 Conference Paper

On the Complexity of Global Scheduling Constraints under Structural Restrictions

• Geoffrey Chu
• Serge Gaspers
• Nina Narodytska
• Andreas Schutt
• Toby Walsh

We investigate the computational complexity of two global constraints, CUMULATIVE and INTERDISTANCE. These are key constraints in modeling and solving scheduling problems. Enforcing domain consistency on both is NP-hard. However, restricted versions of these constraints are often sufficient in practice. Some examples include scheduling problems with a large number of similar tasks, or tasks sparsely distributed over time. Another example is runway sequencing problems in air-traffic control, where landing periods have a regular pattern. Such cases can be characterized in terms of structural restrictions on the constraints. We identify a number of such structural restrictions and investigate how they impact the computational complexity of propagating these global constraints. In particular, we prove that such restrictions often make propagation tractable.

AAMAS Conference 2013 Conference Paper

Possible and Necessary Winner Problem in Social Polls

• Serge Gaspers
• Victor Naroditskiy
• Nina Narodytska
• Toby Walsh

Social networks are increasingly being used to conduct polls. We introduce a simple model of such social polling. We suppose agents vote sequentially, but the order in which agents choose to vote is not necessarily fixed. We also suppose that an agent’s vote is influenced by the votes of their friends who have already voted. Despite its simplicity, this model provides useful insights into a number of areas including social polling, sequential voting, and manipulation. We prove that the number of candidates and the network structure affect the computational complexity of computing which candidate necessarily or possibly can win in such a social poll. For social networks with bounded treewidth and a bounded number of candidates, we provide polynomial algorithms for both problems. In other cases, we prove that computing which candidates necessarily or possibly win are computationally intractable.

FOCS Conference 2013 Conference Paper

Strong Backdoors to Bounded Treewidth SAT

• Serge Gaspers
• Stefan Szeider

There are various approaches to exploiting “hidden structure” in instances of hard combinatorial problems to allow faster algorithms than for general unstructured or random instances. For SAT and its counting version #SAT, hidden structure has been exploited in terms of decomposability and strong backdoor sets. Decomposability can be considered in terms of the treewidth of a graph that is associated with the given CNF formula, for instance by considering clauses and variables as vertices of the graph, and making a variable adjacent with all the clauses it appears in. On the other hand, a strong backdoor set of a CNF formula is a set of variables such that each assignment to this set moves the formula into a fixed class for which (#)SAT can be solved in polynomial time. In this paper we combine the two above approaches. In particular, we study the algorithmic question of finding a small strong backdoor set into the class Wν≤ t of CNF formulas whose associated graphs have treewidth at most t. The main results are positive: (1) There is a cubic-time algorithm that, given a CNF formula F and two constants k, t ≥ 0, either finds a strong Wν≤ t -backdoor set of size at most 2k, or concludes that F has no strong Wν≤ t -backdoor set of size at most k. (2) There is a cubic-time algorithm that, given a CNF formula F, computes the number of satisfying assignments of F or concludes that sbt(F) > k, for any pair of constants k, t ≥ 0. Here, sbt(F) denotes the size of a smallest strong Wν≤ t -backdoor set of F. We establish both results by distinguishing between two cases, depending on whether the treewidth of the given formula is small or large. For both results the case of small treewidth can be dealt with relatively standard methods. The case of large treewidth is challenging and requires novel and sophisticated combinatorial arguments. The main tool is an auxiliary graph whose vertices represent subgraphs in F's associated graph. It captures various ways to assemble large-treewidth subgraphs in F's associated graph. This is used to show that every backdoor set of size k intersects a certain set of variables whose size is bounded by a function of k and t. For any other set of k variables, one can use the auxiliary graph to find an assignment τ to these variables such that the graph associated with F[τ] has treewidth at least t + 1. The significance of our results lies in the fact that they allow us to exploit algorithmically a hidden structure in formulas that is not accessible by any one of the two approaches (decomposability, backdoors) alone. Already a backdoor size 1 on top of treewidth 1 (i. e. , sb 1 (F) = 1) entails formulas of arbitrarily large treewidth and arbitrarily large cycle cutsets (variables whose deletion makes the instance acyclic).

AAAI Conference 2013 Conference Paper

Ties Matter: Complexity of Manipulation when Tie-Breaking with a Random Vote

• Haris Aziz
• Serge Gaspers
• Nicholas Mattei
• Nina Narodytska
• Toby Walsh

We study the impact on strategic voting of tie-breaking by means of considering the order of tied candidates within a random vote. We compare this to another non-deterministic tie-breaking rule where we simply choose candidate uniformly at random. In general, we demonstrate that there is no connection between the computational complexity of computing a manipulating vote with the two different types of tie-breaking. However, we prove that for some scoring rules, the computational complexity of computing a manipulation can increase from polynomial to NP-hard. We also discuss the relationship with the computational complexity of computing a manipulating vote when we ask for a candidate to be the unique winner, or to be among the set of co-winners.

AAAI Conference 2012 Conference Paper

Don’t Be Strict in Local Search!

• Serge Gaspers
• Eun Jung Kim
• Sebastian Ordyniak
• Saket Saurabh
• Stefan Szeider

Local Search is one of the fundamental approaches to combinatorial optimization and it is used throughout AI. Several local search algorithms are based on searching the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of finding an improved solution. However, for inputs of size n, a naı̈ve brute-force search of the k-exchange neighborhood requires nO(k) time, which is not practical even for very small values of k. Fellows et al. (IJCAI 2009) studied whether this brute-force search is avoidable and gave positive and negative answers for several combinatorial problems. They used the notion of local search in a strict sense. That is, an improved solution needs to be found in the k-exchange neighborhood even if a global optimum can be found efficiently. In this paper we consider a natural relaxation of local search, called permissive local search (Marx and Schlotter, IWPEC 2009) and investigate whether it enhances the domain of tractable inputs. We exemplify this approach on a fundamental combinatorial problem, VERTEX COVER. More precisely, we show that for a class of inputs, finding an optimum is hard, strict local search is hard, but permissive local search is tractable. We carry out this investigation in the framework of parameterized complexity.

AAAI Conference 2012 Conference Paper

On Finding Optimal Polytrees

• Serge Gaspers
• Mikko Koivisto
• Mathieu Liedloff
• Sebastian Ordyniak
• Stefan Szeider

Inferring probabilistic networks from data is a notoriously difficult task. Under various goodness-of-fit measures, finding an optimal network is NP-hard, even if restricted to polytrees of bounded in-degree. Polynomial-time algorithms are known only for rare special cases, perhaps most notably for branchings, that is, polytrees in which the in-degree of every node is at most one. Here, we study the complexity of finding an optimal polytree that can be turned into a branching by deleting some number of arcs or nodes, treated as a parameter. We show that the problem can be solved via a matroid intersection formulation in polynomial time if the number of deleted arcs is bounded by a constant. The order of the polynomial time bound depends on this constant, hence the algorithm does not establish fixed-parameter tractability when parameterized by the number of deleted arcs. We show that a restricted version of the problem allows fixed-parameter tractability and hence scales well with the parameter. We contrast this positive result by showing that if we parameterize by the number of deleted nodes, a somewhat more powerful parameter, the problem is not fixed-parameter tractable, subject to a complexity-theoretic assumption.

SAT Conference 2012 Conference Paper

Strong Backdoors to Nested Satisfiability

• Serge Gaspers
• Stefan Szeider

Abstract Knuth (1990) introduced the class of nested formulas and showed that their satisfiability can be decided in polynomial time. We show that, parameterized by the size of a smallest strong backdoor set to the base class of nested formulas, computing the number of satisfying assignments of any CNF formula is fixed-parameter tractable. Thus, for any k > 0, the satisfiability problem can be solved in polynomial time for any formula F for which there exists a set B of at most k variables such that for every truth assignment τ to B, the reduced formula F [ τ ] is nested; moreover, the degree of the polynomial is independent of k. Our algorithm uses the grid-minor theorem of Robertson and Seymour (1986) to either find that the incidence graph of the formula has bounded treewidth—a case that is solved by model checking for monadic second order logic—or to find many vertex-disjoint obstructions in the incidence graph. For the latter case, new combinatorial arguments are used to find a small backdoor set. Combining both cases leads to an approximation algorithm producing a strong backdoor set whose size is upper bounded by a function of the optimum. Going through all assignments to this set of variables and using Knuth’s algorithm, the satisfiability of the input formula can be decided. With a similar approach, one can also count the number of satisfying assignments of the given formula.

IJCAI Conference 2011 Conference Paper

Kernels for Global Constraints

• Serge Gaspers
• Stefan Szeider

Bessiere et al. (AAAI'08) showed that several intractable global constraints can be efficiently propagated when certain natural problem parameters are small. In particular, the complete propagation of a global constraint is fixed-parameter tractable in k - the number of holes in domains - whenever bound consistency can be enforced in polynomial time; this applies to the global constraints AtMost-NValue and Extended Global Cardinality (EGC). In this paper we extend this line of research and introduce the concept of reduction to a problem kernel, a key concept of parameterized complexity, to the field of global constraints. In particular, we show that the consistency problem for AtMost-NValue constraints admits a linear time reduction to an equivalent instance on O(k2) variables and domain values. This small kernel can be used to speed up the complete propagation of NValue constraints. We contrast this result by showing that the consistency problem for EGC constraints does not admit a reduction to a polynomial problem kernel unless the polynomial hierarchy collapses.

TCS Journal 2010 Journal Article

Iterative compression and exact algorithms

• Fedor V. Fomin
• Serge Gaspers
• Dieter Kratsch
• Mathieu Liedloff
• Saket Saurabh

Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard problems. We exemplify our findings with algorithms for the Maximum Independent Set problem, a parameterized and a counting version of d -Hitting Set and the Maximum Induced Cluster Subgraph problem.

SODA Conference 2009 Conference Paper

A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between

• Serge Gaspers
• Gregory B. Sorkin

MFCS Conference 2008 Conference Paper

Iterative Compression and Exact Algorithms

• Fedor V. Fomin
• Serge Gaspers
• Dieter Kratsch
• Mathieu Liedloff
• Saket Saurabh 0001

Abstract Iterative Compression has recently led to a number of breakthroughs in parameterized complexity. The main purpose of this paper is to show that iterative compression can also be used in the design of exact exponential time algorithms. We exemplify our findings with algorithms for the Maximum Independent Set problem, a counting version of k - Hitting Set and the Maximum Induced Cluster Subgraph problem.