Search

An independent set S in a graph G is k-swap-optimal if there is no independent set S ′ such that | S ′ | > | S | and | (S ′ \ S) ∪ (S \ S ′) | ≤ k . Motivated by applications in data reduction, we study whether we can determine efficiently if a given vertex v is contained in some k-swap-optimal independent set or in all k-swap-optimal independent sets. We show that these problems are NP-hard for constant values of k even on graphs with constant maximum degree. Moreover, we show that the problems are Σ 2 P -hard when k is not constant, even on graphs of constant maximum degree. We obtain similar hardness results for determining whether an edge is contained in a k-swap optimal max cut. Finally, we consider a certain type of edge-swap neighborhood for the Longest Path problem. We show that for a given edge we can decide in f (Δ + k) · n O (1) time whether it is in some k-optimal path. [ABSTRACT FROM AUTHOR]

This article studies the minimum makespan scheduling problem on parallel identical machines with the log-linear learning/ageing effect, also known as polynomial positional learning/ageing effect. To develop a Fully Polynomial Time Approximation Scheme to the problem, we start with an intermediate artificial variant that rounds the values to integers and restricts the solutions to instances sorted in the shortest/longest processing time order. To this end, we propose a dynamic programming algorithm and show that the difference between its returned value and the minimum makespan of the original problem is independent of the processing times. This then leads to an algorithm with provable guaranteed ϵ-additive approximation and pseudo-polynomial running time algorithm, resulting in the desired fully polynomial time approximation solution to the original, not restricted problem. [ABSTRACT FROM AUTHOR]

We study different domination problems of attacking and non-attacking rooks and queens on polyominoes and polycubes of all dimensions. Our main result proves that maximum independent domination is NP-complete for non-attacking queens and for non-attacking rooks on polycubes of dimension three and higher. We also analyze these problems for polyominoes and convex polyominoes, conjecture the complexity classes, and provide a computer tool for investigation. We have also computed new values for classical queen domination problems on chessboards (square polyominoes). For our computations, we have translated the problem into an integer linear programming instance. Finally, using this computational implementation and the game engine Godot, we have developed a video game of minimum domination of queens and rooks on randomly generated polyominoes. [ABSTRACT FROM AUTHOR]

We study several variants of decomposing a symmetric matrix into a sum of a low-rank positive-semidefinite matrix and a diagonal matrix. Such decompositions have applications in factor analysis, and they have been studied for many decades. On the one hand, we prove that when the rank of the positive-semidefinite matrix in the decomposition is bounded above by an absolute constant, the problem can be solved in polynomial time. On the other hand, we prove that, in general, these problems as well as their certain approximation versions are all NP-hard. Finally, we prove that many of these low-rank decomposition problems are complete in the first-order theory of the reals, i.e., given any system of polynomial equations, we can write down a low-rank decomposition problem in polynomial time so that the original system has a solution iff our corresponding decomposition problem has a feasible solution of certain (lowest) rank. [ABSTRACT FROM AUTHOR]

A b-greedy colouring is a colouring which is both a b-colouring and a greedy colouring. A z-colouring is a b-greedy colouring such that a b-vertex of the largest colour is adjacent to a b-vertex of every other colour. The b-Grundy number (resp. z-number) of a graph is the maximum number of colours in a b-greedy colouring (resp. z-colouring) of it. In this paper, we study those two parameters. We show that similarly to the z-number, the b-Grundy number is not monotone and can be arbitrarily smaller than the minimum of the Grundy number and the b-chromatic number. We also describe a polynomial-time algorithm that decides whether a given k -regular graph has b-Grundy number (resp. z-number) equal to k + 1. We also prove that every cubic graph with no induced 4-cycle has b-Grundy number and z-number exactly 4. [ABSTRACT FROM AUTHOR]

We investigate several geometric problems of finding tours and cycle covers with minimum turn cost, which have been studied in the past, with complexity, approximation results, and open problems dating back to work by Arkin et al. in 2001. Many new practical applications have spawned variants: For full coverage, all points have to be covered, for subset coverage, specific points have to be covered, and for penalty coverage, points may be left uncovered by incurring a penalty. We show that finding a minimum-turn (full) cycle cover is NP-hard even in 2-dimensional grid graphs, solving the long-standing open Problem 53 in The Open Problems Project edited by Demaine, Mitchell and O'Rourke. We also prove NP-hardness of finding a subset cycle cover of minimum turn cost in thin grid graphs, for which Arkin et al. gave a polynomial-time algorithm for full coverage; this shows that their boundary techniques cannot be applied to compute exact solutions for subset and penalty variants. We also provide a number of positive results. In particular, we establish the first constant-factor approximation algorithms for all considered subset and penalty problem variants for grid-based instances, based on LP/IP techniques. These geometric versions allow many possible edge directions (and thus, turn angles, such as in hexagonal grids or higher-dimensional variants); our approximation factors improve the combinatorial ones of Arkin et al. [ABSTRACT FROM AUTHOR]

We study the problem of placing wildlife crossings, such as green bridges, over human-made obstacles to challenge habitat fragmentation. The main task herein is, given a graph describing habitats or routes of wildlife animals and possibilities of building green bridges, to find a low-cost placement of green bridges that connects the habitats. We develop three problem models for this task and study them from a computational complexity and parameterized algorithmics perspective. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Zhejiang University (Science Edition) is the property of Journal of Zhejiang University (Science Edition) Editorial Office and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Given two permutations, a pattern σ and a text π , Parity Permutation Pattern Matching asks whether there exists a parity and order preserving embedding of σ into π . While it is known that Permutation Pattern Matching is in FPT , we show that adding the parity constraint to the problem makes it W [ 1 ] -hard, even for alternating permutations or for 4321-avoiding patterns. However, the problem remains in FPT if π avoids a fixed permutation, thanks to a recent meta-theorem on twin-width. On the other hand, as for the classical version, Parity Permutation Pattern Matching remains polynomial-time solvable when the pattern is separable, or if both permutations are 321-avoiding, but NP-hard if σ is 321-avoiding and π is 4321-avoiding. [ABSTRACT FROM AUTHOR]

This paper is devoted to a classical NP-hard problem, known as the three-index axial assignment problem. Within the corresponding framework, the problem of combining feasible solutions is posed as an assignment problem on the set of solutions containing only the components of selected feasible solutions. The issues of combining solutions for the multicriteria problem with different criteria convolutions are studied. In the general case, the combination problem turns out to be NP-hard. Polynomial solvability conditions are obtained for the combination problem. [ABSTRACT FROM AUTHOR]

The paper considers the following problem. Given a set of Euclidean vectors, find several clusters with a restriction on the maximum scatter of each cluster so that the size of the minimum cluster would be maximum. Here the scatter is the sum of squared distances from the cluster elements to its centroid. The NP-hardness of this problem is proved in the case where the dimension of the space is part of the input. [ABSTRACT FROM AUTHOR]

This paper provides an overview of the necessary and sufficient conditions for guaranteeing the unique solvability of absolute value equations. In addition to discussing the basic form of these equations, we also address several generalizations, including generalized absolute value equations and matrix absolute value equations. Our survey encompasses known results as well as novel characterizations proposed in this study. [ABSTRACT FROM AUTHOR]

Consider a set of jobs connected to a directed acyclic task graph with a fixed source and sink. The edges of this graph model precedence constraints and the jobs have to be scheduled with respect to those. We introduce the server cloud scheduling problem, in which the jobs have to be processed either on a single local machine or on one of infinitely many cloud machines. For each job, processing times both on the server and in the cloud are given. Furthermore, for each edge in the task graph, a communication delay is included in the input and has to be taken into account if one of the two jobs is scheduled on the server and the other in the cloud. The server processes jobs sequentially, whereas the cloud can serve as many as needed in parallel, but induces costs. We consider both makespan and cost minimization. The main results are an FPTAS for the makespan objective for graphs with a constant source and sink dividing cut and strong hardness for the case with unit processing times and delays. [ABSTRACT FROM AUTHOR]

We analyze the (parameterized) computational complexity of "fair" variants of bipartite many-to-one matching, where each vertex from the "left" side is matched to exactly one vertex and each vertex from the "right" side may be matched to multiple vertices. We want to find a "fair" matching, in which each vertex from the right side is matched to a "fair" set of vertices. Assuming that each vertex from the left side has one color modeling its "attribute", we study two fairness criteria. For instance, in one of them, we deem a vertex set fair if for any two colors, the difference between the numbers of their occurrences does not exceed a given threshold. Fairness is, for instance, relevant when finding many-to-one matchings between students and colleges, voters and constituencies, and applicants and firms. Here colors may model sociodemographic attributes, party memberships, and qualifications, respectively. We show that finding a fair many-to-one matching is NP-hard even for three colors and maximum degree five. Our main contribution is the design of fixed-parameter tractable algorithms with respect to the number of vertices on the right side. Our algorithms make use of a variety of techniques including color coding. At the core lie integer linear programs encoding Hall like conditions. We establish the correctness of our integer programs, based on Frank's separation theorem [Frank, Discrete Math. 1982]. We further obtain complete complexity dichotomies regarding the number of colors and the maximum degree of each side. [ABSTRACT FROM AUTHOR]

In this paper, we consider three cases of an intractable problem of searching for two subsets in a finite set of points of Euclidean space. In all three cases, it is required to maximize the minimum cluster's cardinality under constraint on each cluster's scatter. The scatter is the sum of the distances from the cluster elements to the center, which is defined differently in each of the three cases. In the first case, cluster centers are fixed points. In the second case, the centers are unknown points from the input set. In the third case, the centers are defined as the centroids (the arithmetic mean) of clusters. We propose a general scheme that allows us to build a polynomial 1/2-approximation algorithm for a generalized problem and can be used for constructing 1/2-approximation algorithms for the first two cases and for the one-dimensional third case. Also we show how, using precomputed general information, their time complexities can be reduced to the complexity of sorting. Finally, we present the results of computational experiments showing the accuracy of the proposed algorithms on randomly generated input data. [ABSTRACT FROM AUTHOR]

Privacy is a complex balancing problem between risks and utility of data. K-anonymity, a fundamental model for preserving privacy, guarantees that an item cannot be differentiated from at least k-1 other items. Due to the k-anonymity is a hard problem, which means obtaining an optimal solution within a reasonable time is not possible, researchers endeavor to create near-optimal solutions. There are some researches in the literature demonstrating the NP-Hardness of achieving k-anonymity. The problems of k-dimensional perfect matching, edge partition into triangles, minimum vertex covering, and maximum k-dimensional matching with k-occurrences are some examples of NP-Complete problems commonly used for reduction to prove the NP-Hardness of k-anonymity. However, previous proofs use large alphabet size and suppress more cells causing less utility. This study presents a significant contribution by providing a new proof for the NP-Hardness of k-anonymity and enhances both the alphabet size and the number of suppressed cells. The proof is achieved by using a reduction from the graph coloring problem, which is being provided for the first time.

Understanding the relationship between various nodes of a network is critical for building a robust and resilient network. Studying and understanding the causes of network failures is vital to prevent electric grid blackouts, mitigate supply chain failures, and keep transportation systems functional, among others. Failure of one or more nodes may cause other nodes in the network to fail as well, that is, failures are causal. In general, these failure relationships extend beyond the immediate neighborhood of failed nodes. When any of the causal failures are applied (the nodes of the causal failures are removed), the network could be disconnected. One can add edges to the original network (augmentation problem) in such a way that the network remains connected after applying each of the causal failures, or the largest connected component in the disconnected network is at least a given specified size $\alpha \times n$ ( $\alpha $ -giant component), where n is the number of nodes in the original network. By choosing this size, we guarantee that the network is active for a large population of entities represented by the nodes in the giant component. More formally, we consider the network augmentation problem when faced with causal failures as follows. Given a network $G=(V, E)$ , its complement $\bar {G}=(V, \bar {E})$ with a cost function $c: \bar {E} \rightarrow R^{+}$ and the causality set $\mathcal {C}$ , find a subset of $\bar {E}$ with a minimum total cost such that the network maintains at least one $\alpha $ -giant component when each causal failure in $\mathcal {C}$ is applied to the augmented graph. We prove the NP-hardness of this problem and present a mixed integer linear programming model to provide the exact solution to the problem. Furthermore, we design a heuristic algorithm by checking the connected components when applying each causality. Finally, experiments are conducted on synthetic Erdős-Rényi networks, and we demonstrate the efficacy and efficiency of the heuristic algorithm relative to the mixed-integer linear programming model.

We introduce a new two-sided stable matching problem that describes the summer internship matching practice of an Australian university. The model is a case between two models of Kamada and Kojima on matchings with distributional constraints. We study three solution concepts, the strong and weak stability concepts proposed by Kamada and Kojima, and a new one in between the two, called cutoff stability. Kamada and Kojima showed that a strongly stable matching may not exist in their most restricted model with disjoint regional quotas. Our first result is that checking its existence is NP-hard. We then show that a cutoff stable matching exists not just for the summer internship problem but also for the general matching model with arbitrary heredity constraints. We present an algorithm to compute a cutoff stable matching and show that it runs in polynomial time in our special case of summer internship model. However, we also show that finding a maximum size cutoff stable matching is NP-hard, but we provide a Mixed Integer Linear Program formulation for this optimisation problem. [ABSTRACT FROM AUTHOR]

Hypertree decompositions (HDs), aswell as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHDs) are hypergraph decompositionmethods successfully used for answering conjunctive queries and for solving constraint satisfaction problems. Every hypergraph H has a width relative to each of these methods: its hypertree width hw(H), its generalized hypertree width ghw(H), and its fractional hypertree width fhw(H), respectively. It is known that hw(H) ≤ k can be checked in polynomial time for fixed k, while checking ghw(H) ≤ k is NP-complete for k ≥ 3. The complexity of checking fhw(H) ≤ k for a fixed k has been open for over a decade. We settle this open problem by showing that checking fhw(H) ≤ k is NP-complete, even for k = 2. The same construction allows us to prove also the NP-completeness of checking ghw(H) ≤ k for k = 2. After that, we identify meaningful restrictions that make checking for bounded ghw or fhw tractable or allow for an efficient approximation of the fhw. [ABSTRACT FROM AUTHOR]

AbstractA restrained Italian dominating function (RID-function) on a graph [Formula: see text] is a function [Formula: see text] satisfying: (i) [Formula: see text] for every vertex [Formula: see text] with [Formula: see text], where [Formula: see text] is the set of vertices adjacent to u; (ii) the subgraph induced by the vertices assigned 0 under f has no isolated vertices. The weight of an RID-function is the sum of its function value over the whole set of vertices, and the restrained Italian domination number is the minimum weight of an RID-function on G. In this paper, we initiate the study of the restrained Italian reinforcement number [Formula: see text] of a graph G defined as the cardinality of a smallest set of edges that we must add to the graph to decrease its restrained Italian domination number. We begin by showing that the decision problem associated with the restrained Italian reinforcement problem is NP-hard for arbitrary graphs. Then several properties as well as some sharp bounds of the restrained Italian reinforcement number are presented.