Search

The fair k -center problem has been paid lots of attention recently. In the fair k -center problem, we are given a set X of points in a metric space and a parameter k ∈ Z + , where the points in X are divided into several groups, and each point is assigned a color to denote which group it is in. The goal is to partition X into k clusters such that the number of cluster centers with each color is equal to a given value, and the k -center problem objective is minimized. In this paper, we consider the fair k -center problem with outliers and capacity constraints, denoted as the fair k -center with outliers (F k CO) problem and the capacitated fair k -center (CF k C) problem, respectively. The outliers constraints allow up to z outliers to be discarded when computing the objective function, while the capacity constraints require that each cluster has size no more than L. In this paper, we design an Fixed-Parameter Tractability (FPT) approximation algorithm and a polynomial approximation algorithm for the above two problems. In particular, our algorithms give (1 + ϵ) -approximations with FPT time for the F k CO and CF k C problems in doubling metric space. Moreover, we also propose a 3-approximation algorithm in polynomial time for the F k CO problem with some reasonable assumptions. [ABSTRACT FROM AUTHOR]

A subset S of vertices of G is a total dominating set if, for any vertex v , there is a vertex in S adjacent to v. A total dominating set S is a secure total dominating set if, for any vertex v ∉ S , there is a vertex u ∈ S such that uv is an edge and (S ∖ { u }) ∪ { v } is also a total dominating set. In this paper, we design an O (m) -time algorithm for computing a minimum secure total dominating set in a proper interval graph, where m is the number of edges. [ABSTRACT FROM AUTHOR]

• We study the heterogeneous weighted delivery (HWD) problem, which was introduced in [Bärtschi et al., STACS'17]. • We efficiently 8-approximate HWD with k = O (log ⁡ n) agents, closing an open problem in [Bärtschi et al., ATMOS'17]. • We design a O (k) -approximation algorithm that runs in polynomial time regardless of the value of k. • We design a polynomial-time O ˜ (log 3 ⁡ n) -approximation algorithm. • We show that the HWD problem is 36-approximable in polynomial time when each agent has one of two possible consumption rates. We study the heterogeneous weighted delivery (HWD) problem introduced in [Bärtschi et al., STACS'17] where k heterogeneous mobile agents (e.g., robots, vehicles, etc.), initially positioned on vertices of an n -vertex edge-weighted graph G , have to deliver m messages. Each message is initially placed on a source vertex of G and needs to be delivered to a target vertex of G. Each agent can move along the edges of G and carry at most one message at any time. Each agent has a rate of energy consumption per unit of traveled distance and the goal is that of delivering all messages using the minimum overall amount of energy. This problem has been shown to be NP-hard even when k = 1 , and is 4 ρ -approximable where ρ is the ratio between the maximum and minimum energy consumption of the agents. In this paper, we provide approximation algorithms with approximation ratios independent of the energy consumption rates. First, we design a polynomial-time 8-approximation algorithm for k = O (log ⁡ n) , closing a problem left open in [Bärtschi et al., ATMOS'17]. This algorithm can be turned into an O (k) -approximation algorithm that always runs in polynomial-time, regardless of the values of k. Then, we show that HWD problem is 36-approximable in polynomial-time when each agent has one of two possible consumption rates. Finally, we design a polynomial-time O ˜ (log 3 ⁡ n) -approximation algorithm for the general case. [ABSTRACT FROM AUTHOR]

Motivated by the design of cost-efficient communication networks, the problem about Maximum Internal Spanning Tree that arises in a connected graph, is proposed to find a spanning tree with the maximum number of internal vertices. In 2018, Xingfu Li et al. presented a polynomial algorithm to find a maximum internal spanning tree in a connected interval graph. Based on the structure of normal orderings on interval graphs, we present a simple linear time algorithm that solve the problem when restricted to connected interval graphs in this paper. The proof provides additional insight about the linear time algorithm on interval graphs. • The MIST problem is solvable in a simple linear time algorithm under the restriction of connected interval graphs. • The structure of normal orderings on interval graphs is proposed to solve the Maximum Internal Spanning Tree problem. • The proof of the main results is more easy to understand with proper cases to prove. [ABSTRACT FROM AUTHOR]

The longest common palindromic subsequence (LCPS) problem is a variant of the longest common subsequence (LCS) problem. Given two input sequences A and B , the LCPS problem is to find the common subsequence of A and B such that the answer is a palindrome with the maximal length. The LCPS problem was first proposed by Chowdhury et al. (2014) [9] , who proposed a dynamic programming algorithm with O (m 2 n 2) time, where m and n denote the lengths of A and B , respectively. This paper proposes a diagonal-based algorithm for solving the LCPS problem with O (L (m − L) R log ⁡ n) time and O (R L) space, where R denotes the number of match pairs between A and B , and L denotes the LCPS length. In our algorithm, the 3-dimensional minima finding algorithm is invoked to overcome the domination problem. As experimental results show, our algorithm is efficient practically compared with some previously published algorithms. [ABSTRACT FROM AUTHOR]

A neighbor-sum-distinguishing W -edge-weighting of a graph G = (V , E) is an assignment ω of weights from a set of integers W to the set of edges E of G such that for every pair of adjacent vertices, the incident sums induced by the edge-weighting are different, where the incident sum of a vertex v induced by the edge-weighting ω is σ (v) = ∑ u ∈ N (v) ω (u v) , where N (v) is the set of neighbors of v in G. Whereas, a neighbor-sum- 2 -distinguishing W-edge-weighting of G is a neighbor-sum-distinguishing W -edge-weighting such that the incident sums of every pair of adjacent vertices differ by at least 2. A recently proposed conjecture about neighbor-sum-2-distinguishing { 1 , 3 , 5 } -edge-weighting states that any graph with no component isomorphic to K 2 admits a neighbor-sum-2-distinguishing { 1 , 3 , 5 } -edge-weighting. In this paper, we prove that deciding whether there exists a neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting is NP-complete for bipartite graphs. We present an algorithm that computes a neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting of the central graph of any graph in polynomial time and thus proves the above conjecture for the central graph of any graph. Further, we establish that if any pair of graphs G and H admit neighbor-sum-2-distinguishing edge-weightings, then so does their Cartesian product, G □ H. We study another aspect of neighbor-sum-2-distinguishing edge-weighting of a graph G , namely, the minimum number of incident sums used by a neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting, which is denoted by γ Σ > 1 , { 1 , 3 } (G). We prove that the problems of deciding whether there exists a neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting of G from a given set of sums, and deciding whether γ Σ > 1 , { 1 , 3 } (G) ≤ k are NP-complete for bipartite graphs. On the positive side, we provide both upper and lower bounds on γ Σ > 1 , { 1 , 3 } (C (G)) for central graphs of bipartite graphs and split graphs. We also propose an algorithm that computes the optimal neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting of the central graphs of cycles and paths in polynomial time. [ABSTRACT FROM AUTHOR]

The Exact Satisfiability problem asks if we can find a satisfying assignment to each clause such that exactly one literal in each clause is assigned 1, while the rest are all assigned 0. We can generalise this problem further by defining that a C j clause is solved iff exactly j of the literals in the clause are 1 and all others are 0. We now introduce the family of Generalised Exact Satisfiability problems called G i XSAT as the problem to check whether a given instance consisting of C j clauses with j ∈ { 0 , 1 , ... , i } for each clause has a satisfying assignment. In this paper, we present faster exact polynomial space algorithms, using a nonstandard measure, to solve G i XSAT, for i ∈ { 2 , 3 , 4 } , in O (1.3674 n) time, O (1.5687 n) time and O (1.6545 n) time, respectively, using polynomial space, where n is the number of variables. This improves the current state of the art for polynomial space algorithms from O (1.4203 n) time for G2XSAT by Zhou, Jiang and Yin and from O (1.6202 n) time for G3XSAT by Dahllöf and from O (1.6844 n) time for G4XSAT which was by Dahllöf as well. In addition, we present faster exact algorithms solving G2XSAT, G3XSAT and G4XSAT in O (1.3188 n) time, O (1.3407 n) time and O (1.3536 n) time respectively at the expense of using exponential space. [ABSTRACT FROM AUTHOR]

A subset M ⊆ E of edges of a graph G = (V , E) is called a matching if no two edges of M share a common vertex. An edge e ∈ E is said to dominate itself and all other edges adjacent to it. A matching M in a graph G = (V , E) is called a dominating induced matching (d.i.m.) if every edge of G is dominated by edges of M exactly once. The dominating induced matching decide (DIM-Decide) problem asks whether a graph G contains a dominating induced matching. The dominating induced matching (DIM) problem asks to compute a dominating induced matching (d.i.m.) in a graph G that admits a dominating induced matching. The DIM-Decide problem is known to be NP-complete for general graphs as well as for bipartite graphs. In this paper, we strengthen the NP-completeness result of the DIM-Decide problem by showing that this problem remains NP-complete for perfect elimination bipartite graphs, a proper subclass of bipartite graphs. On the positive side, we characterize the class of star-convex bipartite graphs admitting a d.i.m. This characterization leads to a linear time algorithm to test whether a star-convex bipartite graph admits a d.i.m. and, if so, constructs a d.i.m. in such a star-convex bipartite graph in linear time. We also propose polynomial time algorithms to construct a d.i.m. in long- k -star-convex bipartite graphs as well as in circular-convex bipartite graphs if the input graph admits a d.i.m. [ABSTRACT FROM AUTHOR]

We consider a two-stage production scheduling problem where each operation can be outsourced or processed in-house. For each operation in the same machine, the ratio of its outsourcing cost to its processing time is constant. The objective is to minimize the sum of the makespan and the total outsourcing cost. It is known that this problem is either polynomial time solvable or NP-hard according to the conditions of the ratios. Even though approximation algorithms for NP-hard cases had been developed, their tight worst-case performance ratios are still open. In this paper, we carefully analyze the approximation algorithms to identify their tight worst-case performance ratios for cases. In one case, we propose a new approximation algorithm with a better and tight worst-case performance ratio. In the process of analyzing the algorithm, we propose a technique utilizing nonlinear optimization. [ABSTRACT FROM AUTHOR]

• Study the minsum k -sink problems on dynamic flow path networks for the confluent/non-confluent flow model. • Develop algorithms which run in almost linear time regardless of the number of sinks k. • Improve upon the previous results for the same problem with the confluent flow model. • Provide the first polynomial time algorithm for the problem with the non-confluent flow model. • The main theoretical contribution is to construct novel data structures for solving subproblems in polylogarithmic time. We address the facility location problems on dynamic flow path networks. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and positive vertex weights. A path can be considered as a road, an edge length as the distance along the road and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. In the dynamic flow network, given particular points on edges or vertices, called sinks , all the people evacuate from the vertices to the sinks as quickly as possible. The problem is to find the location of sinks on a dynamic flow path network in such a way that the aggregate evacuation time (i.e., the sum of evacuation times for all the people) to sinks is minimized. We consider two models of the problem: the confluent flow model and the non-confluent flow model. In the former model, the way of evacuation is restricted so that all the people at a vertex have to evacuate to the same sink, and in the latter model, there is no such restriction. In this paper, for both the models, we develop algorithms which run in almost linear time regardless of the number of sinks. It should be stressed that for the confluent flow model, our algorithm improves upon the previous result by Benkoczi et al. [Theoretical Computer Science, 2020], and one for the non-confluent flow model is the first polynomial time algorithm. [ABSTRACT FROM AUTHOR]

The Restricted Subset Feedback Vertex Set problem (R-SFVS) takes a graph G = (V , E) , a terminal set T ⊆ V , and an integer k as the input. The task is to determine whether there exists a subset S ⊆ V ∖ T of at most k vertices, after deleting which no terminal in T is contained in a cycle in the remaining graph. R-SFVS is NP -complete even when the input graph is restricted to split graphs. In this paper, we mainly show that R-SFVS in chordal and split graphs can be solved in O (1.1550 | V |) time and exponential space or in O (1.1605 | V |) time and polynomial space, significantly improving all previous results. As a by-product, we show that the Maximum Independent Set problem parameterized by the edge clique cover number is fixed-parameter tractable. Furthermore, by using a simple reduction from R-SFVS to Vertex Cover , we obtain an O ⁎ (1.2738 k) -time parameterized algorithm and a tight O (k 2) -kernel for R-SFVS in chordal and split graphs. [ABSTRACT FROM AUTHOR]

• We analyze the approximability of the independent feedback vertex set problem. • The problem is hard to approximate on planar bipartite graphs. • There is an efficient approximation algorithm for bipartite graphs of bounded maximum degree. • The problem is solvable in polynomial time if a given bipartite graph is of maximum degree three. Given an undirected graph G with n vertices, the independent feedback vertex set problem is to find a vertex subset F of G with the minimum number of vertices such that F is both an independent set and a feedback vertex set of G , if it exists. This problem is known to be NP-hard for bipartite planar graphs of maximum degree four. In this paper, we study the approximability of the problem. We first show that, for any fixed ε > 0 , unless P = NP , there exists no polynomial-time n 1 − ε -approximation algorithm even for bipartite planar graphs. We then give an α (Δ − 1) / 2 -approximation algorithm for bipartite graphs G of maximum degree Δ, which runs in t (α , G) + O (Δ n) time, under the assumption that there is an α -approximation algorithm for the original feedback vertex set problem on bipartite graphs which runs in t (α , G) time. This algorithmic result also yields a polynomial-time (exact) algorithm for the independent feedback vertex set problem on bipartite graphs of maximum degree three. [ABSTRACT FROM AUTHOR]

A subset D ⊆ V of a graph G = (V , E) is called a global total k -dominating set of G if D is a total k -dominating set of both G and the complement G ‾ of G. The Minimum Global Total k -Domination problem is to find a global total k -dominating set of minimum cardinality of the input graph G and Decide Global Total k -Domination problem is the decision version of Minimum Global Total k -Domination problem. The Decide Global Total k -Domination problem is known to be NP -complete for general graphs as well as for bipartite graphs. In this paper, we strengthen the NP -completeness result of Decide Global Total k -Domination problem by showing that this problem remains NP -complete for perfect elimination bipartite graphs, star-convex bipartite graphs and doubly chordal graphs. On the positive side, we give a polynomial time algorithm for the Minimum Global Total k -Domination problem for chordal bipartite graphs, which is a subclass of bipartite graphs. We propose a 2 (1 + ln ⁡ | V |) -approximation algorithm for the Minimum Global Total k -Domination problem for any graph. We show that Minimum Global Total k -Domination problem cannot be approximated within (1 − ϵ) ln ⁡ | V | for any ϵ > 0 unless P = NP for any integer k ≥ 1. We further show that for bipartite graphs, Minimum Global Total k -Domination problem cannot be approximated within (1 6 − ϵ) ln ⁡ | V | for any ϵ > 0 unless P = NP for any k ≥ 1. Finally, we show that the Minimum Global Total k -Domination problem is APX -complete for bounded degree bipartite graphs for any fixed integer k ≥ 1. [ABSTRACT FROM AUTHOR]

The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We study complexity of the problem on hereditary subclasses of subcubic graphs. Each such subclass can be described by means of forbidden induced subgraphs. In case of finitely many forbidden induced subgraphs a necessary condition for polynomial-time solvability of the problem in subcubic graphs (unless P = N P) is the exclusion of the graph S i , j , k , which is a tree with three leaves of distance i , j , k from the only vertex of degree 3. Whether this condition is also sufficient is an open question, which was previously answered only for S 1 , k , k -free subcubic graphs and S 2 , 2 , 2 -free subcubic graphs. Combining various algorithmic techniques, in the present paper we generalize both results and show that the problem can be solved in polynomial time for S 2 , k , k -free subcubic graphs, for any fixed value of k. [ABSTRACT FROM AUTHOR]

The multi-service center problem is a variant of facility location problems. In the problem, we consider locating p facilities on a graph, each of which provides distinct service required by all vertices. Each vertex incurs the cost determined by the sum of the weighted distances to the p facilities. The aim of the problem is to minimize the maximum cost among all vertices. This problem is known to be NP-hard for general graphs, while it is solvable in polynomial time when p is a fixed constant. In this paper, we give sharp analyses for the complexity of the problem from the viewpoint of graph classes and weights on vertices. We first propose a polynomial-time algorithm for trees when p is a part of input. In contrast, we prove that the problem becomes strongly NP-hard even for cycles. We also show that when vertices are allowed to have negative weights, the problem becomes NP-hard for paths of only three vertices and strongly NP-hard for stars. [ABSTRACT FROM AUTHOR]

We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw a simple path in a rectangular grid graph from a start vertex to a destination vertex. The different puzzle types place different constraints on the path: preventing some edges from being visited (broken edges); forcing some edges or vertices to be visited (hexagons); forcing some cells to have certain numbers of incident path edges (triangles); or forcing the regions formed by the path to be partially monochromatic (squares), have exactly two special cells (stars), or be singly covered by given shapes (polyominoes) and/or negatively counting shapes (antipolyominoes). We show that any one of these clue types (except the first) is enough to make path finding NP-complete ("witnesses exist but are hard to find"), even for rectangular boards. Furthermore, we show that a final clue type (antibody), which necessarily "cancels" the effect of another clue in the same region, makes path finding Σ 2 -complete ("witnesses do not exist"), even with a single antibody (combined with many anti/polyominoes), and the problem gets no harder with many antibodies. On the positive side, we give a polynomial-time algorithm for monomino clues, by reducing to hexagon clues on the boundary of the puzzle, even in the presence of broken edges, and solving "subset Hamiltonian path" for terminals on the boundary of an embedded planar graph in polynomial time. [ABSTRACT FROM AUTHOR]

• We present a deterministic approximation algorithm for a #P-hard problem. • Our algorithm is a fully polynomial time approximation scheme (FPTAS). • To this end, the intersection volume of two cross-polytopes is also considered. • We propose an FPTAS also for the intersection volume of cross-polytopes. • We prove that computing the intersection volume is, surprisingly, still #P-hard. Given an n -dimensional convex body by a membership oracle in general, it is known that any polynomial-time deterministic algorithm cannot approximate its volume within ratio (n / log ⁡ n) n. There is a substantial progress on randomized approximation such as Markov chain Monte Carlo for a high-dimensional volume, and for many #P-hard problems, while only a few #P-hard problems are known to yield deterministic approximation. Motivated by the problem of deterministically approximating the volume of a V -polytope, that is a polytope with a small number of vertices and (possibly) exponentially many facets, this paper investigates the problem of computing the volume of a "knapsack dual polytope," which is known to be #P-hard due to Khachiyan (1989) [16]. We reduce an approximate volume of a knapsack dual polytope to that of the intersection of two cross-polytopes in a short distance, and give FPTASs for those volume computations. Interestingly, computing the volume of the intersection of two cross-polytopes (i.e., L 1 -balls) is #P-hard, unlike the cases of L ∞ -balls or L 2 -balls. [ABSTRACT FROM AUTHOR]

Let G be an(a) edge(vertex)-colored graph. A path P of G is called a conflict-free path if there is a color that is used on exactly one of the edges(vertices) of P. The graph G is called conflict-free (vertex-)connected if any two distinct vertices of G are connected by a conflict-free path, whereas the graph G is called strongly conflict-free connected if any two distinct vertices u , v of G are connected by a conflict-free path of length of a shortest path between u and v in G. For a connected graph G , the (strong) conflict-free connection number of G , denoted by (s c f c (G)) c f c (G) , is defined as the smallest number of colors that are required to make G (strongly) conflict-free connected. In this paper, we first investigate the question: Given a connected graph G and a coloring c : E (o r V) → { 1 , 2 , ⋯ , k } (k ≥ 1) of G , determine whether or not G is, respectively, conflict-free connected, conflict-free vertex-connected, strongly conflict-free connected under the coloring c. We solve this question by providing polynomial-time algorithms. We then show that the problem of deciding whether s c f c (G) ≤ k (k ≥ 2) for a given graph G is NP-complete. Moreover, we prove that it is NP-complete to decide whether there is a k -edge-coloring (k ≥ 2) of G such that all pairs (u , v) ∈ P (P ⊂ V × V) are strongly conflict-free connected. [ABSTRACT FROM AUTHOR]

We revisit the maximum satisfiability problem (Max-SAT) in the data stream model. In this problem, the stream consists of m clauses that are disjunctions of literals drawn from n Boolean variables. The objective is to find an assignment to the variables that maximizes the number of satisfied clauses. Chou et al. (FOCS 2020) showed that Ω (n) space is necessary to yield a 2 / 2 + ε approximation of the optimum value; they also presented an algorithm that yields a 2 / 2 − ε approximation of the optimum value using O (ε − 2 log ⁡ n) space. In this paper, we not only focus on approximating the optimum value, but also on obtaining the corresponding Boolean assignment using sublinear o (m n) space. We present randomized single-pass algorithms that w.h.p.1 yield: • A 1 − ε approximation using O ˜ (n / ε 3) space and exponential post-processing time • A 3 / 4 − ε approximation using O ˜ (n / ε) space and polynomial post-processing time. Our ideas also extend to dynamic streams. However, we show that the streaming k -SAT problem, which asks whether one can satisfy all size- k input clauses, must use Ω (n k) space. We also consider the related minimum satisfiability problem (Min-SAT), introduced by Kohli et al. (SIAM J. Discrete Math. 1994), that asks to find an assignment that minimizes the number of satisfied clauses. For this problem, we give a O ˜ (n 2 / ε 2) space algorithm, which is sublinear when m = ω (n) , that yields an α + ε approximation where α is the approximation guarantee of the offline algorithm. If each variable appears in at most f clauses, we show that a 2 f n approximation using O ˜ (n) space is possible. Finally, for the Max-AND-SAT problem where clauses are conjunctions of literals, we show that any single-pass algorithm that approximates the optimal value up to a factor better than 1/2 with success probability at least 2/3 must use Ω (m n) space. [ABSTRACT FROM AUTHOR]

To solve reachability is to determine whether there is a path from one vertex to the other in a graph. Standard graph traversal algorithms such as DFS and BFS take linear time to solve reachability; however, their space complexity is also linear. On the other hand, Savitch's algorithm takes quasipolynomial time, although the space-bound is O (log 2 ⁡ n). In this paper, we study space-efficient algorithms for deciding reachability that runs in polynomial time. We show a polynomial-time algorithm that solves reachability in directed graphs using O (w log ⁡ n) space. Our algorithm requires access to a tree decomposition of width w for the underlying undirected graph of the input. This requirement can be waived for graphs for which recursive balanced vertex separators can be computed space-efficiently. [ABSTRACT FROM AUTHOR]

Abstract: In the past, research on multiple criteria scheduling assumes that the number of available machines is fixed during the whole scheduling horizon and research on scheduling with limited machine availability assumes that there is only a single criterion that needs to be optimized. Both assumptions may not hold in real life. In this paper we simultaneously consider both bicriteria scheduling and scheduling with limited machine availability. We focus on two parallel machines’ environment and the goal is to find preemptive schedules to optimize both makespan and total completion time subject to machine availability. Our main contribution in this paper is that we showed three bicriteria scheduling problems are in P by providing polynomial time optimal algorithms. [Copyright &y& Elsevier]

The problem of graph Reachability is to decide whether there is a path from one vertex to another in a given graph. In this paper, we study the Reachability problem on three distinct graph families - intersection graphs of Jordan regions, unit contact disk graphs (penny graphs), and chordal graphs. For each of these graph families, we present space-efficient algorithms for the Reachability problem. For intersection graphs of Jordan regions, we show how to obtain a "good" vertex separator in a space-efficient manner and use it to solve the Reachability in polynomial time and O (m 1 / 2 log ⁡ n) space, where n is the number of Jordan regions, and m is the total number of crossings among the regions. We use a similar approach for chordal graphs and obtain a polynomial time and O (m 1 / 2 log ⁡ n) space algorithm, where n and m are the number of vertices and edges, respectively. However, for unit contact disk graphs (penny graphs), we use a more involved technique and obtain a better algorithm. We show that for every ϵ > 0 , there exists a polynomial time algorithm that can solve Reachability in an n vertex directed penny graph, using O (n 1 / 4 + ϵ) space. We note that the method used to solve penny graphs does not extend naturally to the class of geometric intersection graphs that include arbitrary size cliques. [ABSTRACT FROM AUTHOR]

In 2005, Goddard et al. (2005) [12] asked the computational complexity of determining the maximum cardinality of a matching whose vertex set induces a disconnected graph. In this paper, we answer this question. In fact, we consider the generalized problem of finding c-disconnected matchings ; such matchings are ones whose vertex sets induce subgraphs with at least c connected components. We show that, for every fixed c ≥ 2 , this problem is NP - complete even if we restrict the input to bounded diameter bipartite graphs, while can be solved in polynomial time if c = 1. For the case when c is part of the input, we show that the problem is NP - complete for chordal graphs, while being solvable in polynomial time for interval graphs. Finally, we explore the parameterized complexity of the problem. We present an FPT algorithm under the treewidth parameterization, and an XP algorithm for graphs with a polynomial number of minimal separators when parameterized by c. We complement these results by showing that, unless NP ⊆ coNP / poly , the related Induced Matching problem does not admit a polynomial kernel when parameterized by vertex cover and size of the matching nor when parameterized by vertex deletion distance to clique and size of the matching. As for Connected Matching , we show how to obtain a maximum connected matching in linear time given an arbitrary maximum matching in the input. • NP-complete even for bipartite graphs, for every fixed c at least 2. • NP-complete even for chordal graphs if c is part of the input. • Solvable in polynomial time for interval graphs and in FPT time when parameterized by treewidth. • Induced Matching is unlikely to admit polynomial kernels under common structural parameterizations. [ABSTRACT FROM AUTHOR]

We present efficient computational solutions to the problems of checking equality, performing multiplication, and computing minimal representatives of elements of free bands. A band is any semigroup satisfying the identity x 2 ≈ x and the free band FB (k) is the free object in the variety of k -generated bands. Radoszewski and Rytter developed a linear time algorithm for checking whether two words represent the same element of a free band. In this paper we describe an alternate linear time algorithm for the same problem. The algorithm we present utilises a representation of words as synchronous deterministic transducers that lend themselves to efficient (quadratic in the size of the alphabet) multiplication in the free band. This representation also provides a means of finding the short-lex least word representing a given free band element with quadratic complexity. [ABSTRACT FROM AUTHOR]

As the scale of interconnected networks grows, so does the number of processor failures in the network. When a processor fails, the information transmitted through the failed processor is unreliable. In fact, the higher the network's diagnosability, the more reliable it is. The t / m -diagnosis strategy was proposed [20] , the primary principle of which is to sacrifice less diagnostic accuracy to massively improve the diagnosability, with the goal of enhancing the reliability of the network. This paper presents the t / m -diagnosis algorithm and shows the t / m -diagnosability of the augmented k -ary n -cube A Q n , k , which is an extension of k -ary n -cubes and augmented cubes. In detail, we show that A Q n , k is [ 4 n (1 + m) − ⌊ 5 (1 + m) 2 2 ⌋ ] / m -diagnosable under the PMC model (n ≥ 4 , k ≥ 4 and 0 ≤ m ≤ n − 2) and under the MM* model (n ≥ 4 , k ≥ 4 and 1 ≤ m ≤ n − 2), respectively. Based on these results, we further propose the polynomial-time t / m -diagnosis algorithm on the node number of A Q n , k under the PMC and MM* models respectively. [ABSTRACT FROM AUTHOR]

The notion of Shared Risk Link Groups (SRLG) has been introduced to capture survivability issues where some links of a network fail simultaneously. In this context, the k-diverse routing problem is to find a set of k pairwise SRLG-disjoint paths between a given pair of end nodes of the network. This problem has been proven NP-complete in general and some polynomial instances have been characterized. In this paper, we investigate the k -diverse routing problem in networks where the SRLGs are localized and satisfy the star property . This property states that a link may be subject to several SRLGs, but all links subject to a given SRLG are incident to a common node. We first provide counterexamples to the polynomial time algorithm proposed by X. Luo and B. Wang (DRCN'05) for computing a pair of SRLG-disjoint paths in networks with SRLGs satisfying the star property, and then prove that this problem is in fact NP-complete. We then characterize instances that can be solved in polynomial time or are fixed parameter tractable, in particular when the number of SRLGs is constant, the maximum degree of the vertices is at most 4, and when the network is a directed acyclic graph. Finally we consider the problem of finding the maximum number of SRLG-disjoint paths in networks with SRLGs satisfying the star property. We prove that this problem is NP-hard to approximate within O ( | V | 1 − ε ) for any 0 < ε < 1 , where V is the set of nodes in the network. Then, we provide exact and approximation algorithms for relevant subcases. [ABSTRACT FROM AUTHOR]

With the fast development of social network services, network marketing of products with externalities has been attracting more and more attention from both academia and business. The extensive study on network marketing mainly concerns with positive externalities. The focus of this paper is on the much less understood counterpart for negative externalities, where a consumer has lower incentive to buy a product as the product is possessed by more social network neighbors. For a seller who markets these products, it is desirable to have a good schedule which specifies an order of consumers he approaches. We design polynomial time algorithms that find marketing schedules for products with negative externalities. The goals are two-fold: maximizing the product sale and ensuring consumer regret-free decisions. We show that the maximization is NP-hard. Our algorithms achieve satisfactory performance guarantees, approximating the maximum within constant factors in most of the cases. Two of these algorithms provide regret-proof schedules, reaching an equilibrium state where no consumers regret their previous decisions. Our work is the first attempt to address these marketing problems from an algorithmic point of view. [ABSTRACT FROM AUTHOR]

Network bargaining is a natural extension of the classical, 2-player Nash bargaining solution to the network setting. Here one is given an exchange network G connecting a set of players V in which edges correspond to potential contracts between their endpoints. In the standard model, a player may engage in at most one contract, and feasible outcomes therefore correspond to matchings in the underlying graph. Kleinberg and Tardos [STOC'08] recently proposed this model, and introduced the concepts of stability and balance for feasible outcomes. The authors characterized the class of instances that admit such solutions, and presented a polynomial-time algorithm to compute them. In this paper, we generalize the work of Kleinberg and Tardos by allowing agents to engage into more complex contracts that span more than two agents. We provide suitable generalizations of the above stability and balance notions, and show that many of the previously known results for the matching case extend to our new setting. In particular, we can show that a given instance admits a stable outcome only if it also admits a balanced one. Like Bateni et al. [ICALP'10] we exploit connections to cooperative games. We fully characterize the core of these games, and show that checking its non-emptiness is NP-complete. On the other hand, we provide efficient algorithms to compute core elements for several special cases of the problem, making use of compact linear programming formulations. [ABSTRACT FROM AUTHOR]