We investigate congested assignment problems where agents have preferences over both resources and their associated congestion levels. These agents are \emph{averse} towards congestion, i.e., consistently preferring lower congestion for identical resources. Such scenarios are ubiquitous across domains including traffic management and school choice, where fair resource allocation is essential. We focus on the concept of \emph{competitiveness}, recently introduced by Bogomolnaia and Moulin [6], and contribute a polynomial-time algorithm that determines competitiveness, resolving their open question. Additionally, we explore two optimization variants of congested assignments by examining the problem of finding envy-free or maximally competitive assignments that guarantee a certain amount of social welfare for every agent, termed \emph{top-guarantees} [6]. While we prove that both problems are NP-hard, we develop parameterized algorithms with respect to the number of agents or resources.

Surface offsetting is a crucial operation in digital geometry processing and computer-aided design, where an offset is defined as an iso-value surface of the distance field. A challenge emerges as even smooth surfaces can exhibit sharp features in their offsets due to the non-differentiable characteristics of the underlying distance field. Prevailing approaches to the offsetting problem involve approximating the distance field and then extracting the iso-surface. However, even with dual contouring (DC), there is a risk of degrading sharp feature points/lines due to the inaccurate discretization of the distance field. This issue is exacerbated when the input is a piecewise-linear triangle mesh. This study is inspired by the observation that a triangle-based distance field, unlike the complex distance field rooted at the entire surface, remains smooth across the entire 3D space except at the triangle itself. With a polygonal surface comprising n triangles, the final distance field for accommodating the offset surface is determined by minimizing these n triangle-based distance fields. In implementation, our approach starts by tetrahedralizing the space around the offset surface, enabling a tetrahedron-wise linear approximation for each triangle-based distance field. The final offset surface within a tetrahedral range can be traced by slicing the tetrahedron with planes. As illustrated in the teaser figure, a key advantage of our algorithm is its ability to precisely preserve sharp features. Furthermore, this paper addresses the problem of simplifying the offset surface's complexity while preserving sharp features, formulating it as a maximal-clique problem.

The Maximal Strip Recovery problem (MSR) and its complementary (CMSR) are well-studied NP-hard problems in computational genomics. The input of these dual problems are two signed permutations. The goal is to delete some gene markers from both permutations, such that, in the remaining permutations, each gene marker has at least one common neighbor. Equivalently, the resulting permutations could be partitioned into common strips of length at least two. Then MSR is to maximize the number of remaining genes, while the objective of CMSR is to delete the minimum number of gene markers. In this paper, we present a new approximation algorithm for the Complementary Maximal Strip Recovery (CMSR) problem. Our approximation factor is 2, improving the currently best 7/3-approximation algorithm. Although the improvement on the factor is not huge, the analysis is greatly simplified by a compensating method, commonly referred to as the non-oblivious local search technique. In such a method a substitution may not always increase the value of the current solution (it sometimes may even decrease the solution value), though it always improves the value of another function seemingly unrelated to the objective function.

A short swap switches two elements with at most one element caught between them. Sorting permutation by short swaps asks to find a shortest short swap sequence to transform a permutation into another. A short swap can eliminate at most three inversions. It is still open for whether a permutation can be sorted by short swaps each of which can eliminate three inversions. In this paper, we present a polynomial time algorithm to solve the problem, which can decide whether a permutation can be sorted by short swaps each of which can eliminate 3 inversions in O(n) time, and if so, sort the permutation by such short swaps in O(n^2) time, where n is the number of elements in the permutation. A short swap can cause the total length of two element vectors to decrease by at most 4. We further propose an algorithm to recognize a permutation which can be sorted by short swaps each of which can cause the element vector length sum to decrease by 4 in O(n) time, and if so, sort the permutation by such short swaps in O(n^2) time. This improves upon the O(n^2) algorithm proposed by Heath and Vergara to decide whether a permutation is so called lucky.

In many surveillance applications, capture devices are set on fixed locations to track entities, leading to valuable spatio-temporal trajectories. However, sometimes the IDs of the entities in these trajectories are incorrectly identified due to various reasons (e.g., illumination conditions and partial occlusion). Since very often the movements of the entities are constrained by certain restrictions imposed by the application (e.g., vehicles must move along the given road network), we consider how to repair the erroneous IDs using transition graphs derived from such restrictions. Roughly speaking, the occurrence of erroneous IDs can cause a valid trajectory to be broken into trajectory fragments that violate some movement constraints imposed by the transition graph, and we aim to repair them by rewriting the IDs and merging the fragments. This problem is practically challenging since it is not easy to judge which IDs in the dataset are correct, and also there may be multiple candidates as the correct value for a single error. We formulate the repair process as an optimization problem and propose a two-phase repair paradigm, which includes candidate repair generation and compatible repair selection, to maximize the quality improvement estimated by a designed objective function. Though both phases are intractable, we propose effective algorithms to solve them through exploiting the locality and sparsity of trajectories. We further devise an index structure, as well as a pruning method to make the repair process more efficient. Experiments on both real and synthetic datasets demonstrate the effectiveness and efficiency of the proposed methods. © 2018 Copyright held by the owner/author(s)

We study the complexity of the bribery problem with distance restrictions. In particular, in the bribery problem, we are given an election and a distinguished candidate p, and are asked whether we can make p win/not win the election by bribing at most k voters to recast their votes. In the bribery problem with distance restrictions, we require that the votes recast by the bribed voters are close to their original votes. To measure the closeness between two votes, we adopt the prevalent Kendall-Tau distance and the Hamming distance. We achieve a wide range of complexity results for this problem under a variety of voting correspondences, including the Borda, Condorcet, Copelandαfor every 0≤α≤1 and Maximin.

We study the computational complexity of control problems for two-stage voting rules. An example of a two-stage voting rule is the Black's procedure. The first stage of the Black's procedure selects the Condorcet winner if one exists; otherwise, in the second stage the Borda winner is selected. The computational complexity of the manipulation problem of two-stage voting rules has recently been studied by Narodytska and Walsh [20] and Fitzsimmons et al. [14]. Extending their work, we consider the control problems for similar scenarios, focusing on constructive control by adding or deleting votes, denoted as CCAV and CCDV, respectively.

Motivation: We address the problem of multiple protein-protein interaction (PPI) network alignment. Given a set of such networks for different species we might ask how much the network topology is conserved throughout evolution. Solving this problem will help to derive a subset of interactions that is conserved over multiple species thus forming a 'core interactome'. Methods: We model the problem as Topological Multiple one-to-one Network Alignment (TMNA), where we aim to minimize the total Graph Edit Distance (GED) between pairs of the input networks. Here, the GED between two graphs is the number of deleted and inserted edges that are required to make one graph isomorphic to another. By minimizing the GED we indirectly maximize the number of edges that are aligned in multiple networks simultaneously. However, computing an optimal GED value is computationally intractable. We thus propose an evolutionary algorithm and developed a software tool, GEDEVO-M, which is able to align multiple PPI networks using topological information only. We demonstrate the power of our approach by computing a maximal common subnetwork for a set of bacterial and eukaryotic PPI networks. GEDEVO-M thus provides great potential for computing the 'core interactome' of different species. Availability: http://gedevo.mpi-inf.mpg.de/multiple-network-alignment/.

The purpose of this study is to investigate the impact of using animation in a multimedia environment designed to improve students’ mathematical spatial ability. Sixth grade students (N = 44) were randomly assigned to one of the two experimental conditions with animation or non-animation as factors. The results show that participants provided with animations performed better than their peers provided with non-animations.

On the base of systematically analysing and summarizing the web-based learning of the domestic and international research, by combining the research actuality of web-based learning and teaching as well as the purpose and characteristic of this study, the article designed the interaction analysis system based on the collaborative knowledge constructing in the environment of QQ Group, and analysed the teachers' chat record of three times of online discussion in the QQ group from topic space, social relations and the process of collaborative knowledge constructing by content analysis and social network analysis, finding out the problems during the teachers’ online discussion which organized for promoting research project and the resistant factor which influence the interactive quality of online discussion, put forward a series of strategies for improving the quality of interaction and the effects of collaborative knowledge constructing. Such as make discussion topic clear and definite before online discussion, pose questions for further consideration in order to keep the discussion gradual in-depth; appoint someone as the organizer of the discussion; formulate the intervention system; carry out teacher training with the help of functional characteristics and technical characteristics of QQ group.

We start a systematic parameterized computational complexity study of three NP-hard network design problems on arc-weighted directed graphs: directed Steiner tree, strongly connected Steiner subgraph, and directed Steiner network. We investigate their parameterized complexities with respect to the three parameterizations: “number of terminals,” “an upper bound on the size of the connecting network,” and the combination of these two. We achieve several parameterized hardness results as well as some fixed-parameter tractability results, in this way extending previous results of Feldman and Ruhl [SIAM J. Comput., 36 (2006), pp. 543–561].

We perform new theoretical as well as first-time experimental studies for the NP-hard problem to find a closest ultrametric for given dissimilarity data on pairs. This is a central problem in the area of hierarchical clustering, where so far only polynomial-time approximation algorithms were known. In contrast, we develop efficient preprocessing algorithms (known as kernelization in parameterized algorithmics) with provable performance guarantees and a simple search tree algorithm. These are used to find optimal solutions. Our experiments with synthetic and biological data show the effectiveness of our algorithms and demonstrate that an approximation algorithm due to Ailon and Charikar [FOCS 2005] often gives (almost) optimal solutions.

We provide first-time fixed-parameter tractability results for the NP-hard problems MAXIMUM FULL-DEGREE SPANNING TREE (FDST) and MINIMUM-VERTEX FEEDBACK EDGE SET. These problems are dual to each other. In MAXIMUM FDST, the task is to find a spanning tree for a given graph that maximizes the number of vertices that preserve their degree. For MINIMUM-VERTEX FEEDBACK EDGE SET, the task is to minimize the number of vertices that end up with a reduced degree. Parameterized by the solution size, we exhibit that MINIMUM-VERTEX FEEDBACK EDGE SET is fixed-parameter tractable and has a problem kernel with the number of vertices linearly depending on the parameter k. Our main contribution for MAXIMUM FULL-DEGREE SPANNING TREE, which is W[1]-hard, is a linear-size problem kernel when restricted to planar graphs. Moreover, we present a dynamic programing algorithm for graphs of bounded treewidth. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Connectivity augmentation problems ask for adding a set of at most k edges (called links) whose insertion makes a given graph satisfy a specified connectivity property, such as bridge-connectivity or biconnectivity. A bridge-connected (biconnected) graph is a connected graph that does not possess an edge (a vertex) whose removal results in a disconnected graph. We show that, for bridge-connectivity and biconnectivity, the respective connectivity augmentation problems admit problem kernels with O(k2) vertices and links. Moreover, we study partial connectivity augmentation problems, naturally generalizing connectivity augmentation problems. Here, we do not require that, after adding the edges, the entire graph should satisfy the connectivity property, but a large subgraph. In this setting, three polynomial-time solvable connectivity augmentation problems behave differently, namely, the partial bridge-connectivity augmentation problem and the partial biconnectivity augmentation problem remain polynomial-time solvable, whereas the partial strong connectivity augmentation problem becomes W[2]-hard with respect to k. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

We introduce the s-Plex Cluster Editing problem as a generalization of the well-studied Cluster Editing problem; both are NP-hard and both are motivated by graph-based data clustering. Instead of transforming a given graph by a minimum number of edge modifications into a disjoint union of cliques (this is Cluster Editing), the task in the case of s-Plex Cluster Editing is to transform a graph into a cluster graph consisting of a disjoint union of so-called s-plexes. Herein, an s-plex is a vertex set S inducing a subgraph in which every vertex has degree at least $|S|-s$. Cliques are 1-plexes. The advantage of s-plexes for $s\geq2$ is that they allow us to model a more relaxed cluster notion (s-plexes instead of cliques), better reflecting inaccuracies of the input data. We develop a provably effective preprocessing based on data reduction (yielding a so-called problem kernel), a forbidden subgraph characterization of s-plex cluster graphs, and a depth-bounded search tree which is used to find optimal edge modification sets. Altogether, this yields efficient algorithms in case of moderate numbers of edge modifications; this is often a reasonable assumption under a maximum parsimony model for data clustering.

The Nemhauser-Trotter local optimization theorem applies to the NP-hard \textsc{Vertex Cover} problem and has applications in approximation as well as parameterized algorithmics. We present a framework that generalizes Nemhauser and Trotter's result to vertex deletion and graph packing problems, introducing novel algorithmic strategies based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did). We exhibit our framework using a generalization of \textsc{Vertex Cover}, called \textrm{\sc Bounded-Degree Deletion}, that has promise to become an important tool in the analysis of gene and other biological networks. For some fixed~$d\geq 0$, \textrm{\sc Bounded-Degree Deletion} asks to delete as few vertices as possible from a graph in order to transform it into a graph with maximum vertex degree at most~$d$. \textsc{Vertex Cover} is the special case of $d=0$. Our generalization of the Nemhauser-Trotter theorem implies that \textrm{\sc Bounded-Degree Deletion} has a problem kernel with a linear number of vertices for every constant~$d$. We also outline an application of our extremal combinatorial approach to the problem of packing stars with a bounded number of leaves. Finally, charting the border between (parameterized) tractability and intractability for \textrm{\sc Bounded-Degree Deletion}, we provide a W[2]-hardness result for \textrm{\sc Bounded-Degree Deletion} in case of unbounded $d$-values.

To cover the edges of a graph with a minimum number of cliques is an NP-complete problem with many applications. The state-of-the-art solving algorithm is a polynomial-time heuristic from the 1970's. We present an improvement of this heuristic. Our main contribution, however, is the development of efficient and effective polynomial-time data reduction rules that, combined with a search tree algorithm, allow for exact problem solutions in competitive time. This is confirmed by experiments with real-world and synthetic data. Moreover, we prove the fixed-parameter tractability of covering edges by cliques.

We study pattern matching for arc-annotated sequences. An O ( nm ) time algorithm is given for the problem to determine whether a length m sequence with nested arc annotation is an arc-preserving subsequence (aps) of a length n sequence with nested arc annotation, called APS(NESTED,NESTED). Arc-annotated sequences and, in particular, those with nested arc annotation are motivated by applications in RNA structure comparison. Our algorithm generalizes results for ordered tree inclusion problems and it is useful for recent fixed-parameter algorithms for LAPCS(NESTED,NESTED), which is the problem of computing a longest arc-preserving common subsequence of two sequences with nested arc annotations. In particular, the presented dynamic programming methodology implies a quadratic-time algorithm for an open problem posed by Vialette.

Abstract We study an NP‐complete (and MaxSNP‐hard) communication problem on tree networks, the so‐called MULTICUT IN TREES: given an undirected tree and some pairs of nodes of the tree, find out whether there is a set of at mostktree edges whose removal separates all given pairs of nodes. MULTICUT has been intensively studied for trees as well as for general graphs mainly from the viewpoint of polynomial time approximation algorithms. By way of contrast, we provide a simple fixed‐parameter algorithm for MULTICUT IN TREES showing fixed‐parameter tractability with respect to parameterk. Moreover, based on some polynomial time data reduction rules, which appear to be of particular interest from an applied point of view, we show a problem kernel for MULTICUT IN TREES by an intricate mathematical analysis. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(3), 124–135 2005