Algorithms and Discrete Applied Mathematics

We prove that the product version of the 1-2-3 Conjecture, raised by Skowronek-Kaziów in 2012, is true. Namely, for every connected graph with order at least 3, we can assign labels 1, 2, 3 to the edges so that no two adjacent vertices are incident to the same product of labels.

The class of \(2K_2\)-free graphs has been well studied in various contexts in the past. It is known that the class of \(\{2K_2,2K_1+K_p\}\)-free graphs and \(\{2K_2,(K_1\cup K_2)+K_p\}\)-free graphs admits a linear \(\chi \)-binding function. In this paper, we study the classes of \((P_3\cup P_2)\)-free graphs which is a superclass of \(2K_2\)-free graphs. We show that \(\{P_3\cup P_2,2K_1+K_p\}\)-free graphs and \(\{P_3\cup P_2,(K_1\cup K_2)+K_p\}\)-free graphs also admits a linear \(\chi \)-binding function. In addition, we give tight chromatic bounds for \(\{P_3\cup P_2,HVN\}\)-free graphs and \(\{P_3\cup P_2,diamond\}\)-free graphs, and it can be seen that the latter is an improvement of the existing bound given by A. P. Bharathi and S. A. Choudum [1].

The complexity of the list homomorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees [1] and reflexive signed graphs [18]. Irreflexive signed graphs are the heart of the problem, and Kim and Siggers have formulated a conjectured classification for these signed graphs. We focus on a special case of irreflexive signed graphs, namely those in which the unicoloured edges form a spanning path or cycle, and classify the complexity of list homomorphisms to these signed graphs. In particular, our results confirm the conjecture of Kim and Siggers for this class of signed graphs.

The general position problem for graphs stems from a puzzle of Dudeney and the general position problem from discrete geometry. The general position number of a graph G is the size of the largest set of vertices S such that no geodesic of G contains more than two elements of S. The monophonic position number of a graph is defined similarly, but with ‘induced path’ in place of ‘geodesic’. In this abstract we discuss the smallest possible order of a graph with given general and monophonic position numbers, determine the asymptotic order of the largest size of a graph with given order and position numbers and finally determine the possible diameters of a graph with given order and monophonic position number.

Comparability graphs and cover-incomparability graphs (C-I graphs) are two interesting classes of graphs from posets. Comparability graph of a poset \(P=(V,\le )\) is a graph with vertex set V and two vertices u and v are adjacent in V if u and v are comparable in P. A C-I graph is a graph from P with vertex set V, and the edge-set is the union of edge sets of the cover graph and the incomparability graph of the poset. C-I graphs have interesting implications on both graphs and posets. In this paper, the C-I graphs, which are also comparability graphs are studied. We identify the class of comparability C-I graphs, which are Ptolemaic graphs, cographs, chordal cographs, distance-hereditary and bisplit graphs. We also determine the posets of these C-I graphs.

For a graph \(G=(V,E)\), a subset D of vertex set V, is a dominating set of G if every vertex not in D is adjacent to atleast one vertex of D. A dominating set D of a graph G with no isolated vertices is called a paired dominating set (PD-set), if G[D], the subgraph induced by D in G has a perfect matching. The Min-PD problem requires to compute a PD-set of minimum cardinality. The decision version of the Min-PD problem remains NP-complete even when G belongs to restricted graph classes such as bipartite graphs, chordal graphs etc. On the positive side, the problem is efficiently solvable for many graph classes including intervals graphs, strongly chordal graphs, permutation graphs etc. In this paper, we study the complexity of the problem in AT-free graphs and planar graph. The class of AT-free graphs contains cocomparability graphs, permutation graphs, trapezoid graphs, and interval graphs as subclasses. We propose a polynomial-time algorithm to compute a minimum PD-set in AT-free graphs. In addition, we also present a linear-time 2-approximation algorithm for the problem in AT-free graphs. Further, we prove that the decision version of the problem is NP-complete for planar graphs, which answers an open question asked by Lin et al. (in Theor. Comput. Sci., \(591 (2015): 99-105\) and Algorithmica, \( 82 (2020): 2809-2840\)).

A k-star colouring of a graph G is a function \(f:V(G)\rightarrow \{0,1,\dots ,k-1\}\) such that \(f(u)\ne f(v)\) for every edge uv of G, and G does not contain a 4-vertex path bicoloured by f as a subgraph. For \(k\in \mathbb {N}\), the problem k-Star Colourability takes a graph G as input and asks whether G is k-star colourable. By the construction of Coleman and Moré (SIAM J. Numer. Anal., 1983), for all \(k\ge 3\), k-Star Colourability is NP-complete for graphs of maximum degree \(d=k(k-1+\lceil \sqrt{k} \rceil )\). For \(k=4\) and \(k=5\), the maximum degree in this NP-completeness result is \(d=20\) and \(d=35\) respectively. We reduce the maximum degree to \(d=4\) in both cases: i.e., 4-Star Colourability and 5-Star Colourability are NP-complete for graphs of maximum degree four. We also show that for all \(k\ge 3\) and \(d<k\), the time complexity of k-Star Colourability is the same for graphs of maximum degree d and d-regular graphs (i.e., the problem is either in P for both classes or NP-complete for both classes).

A natural constraint in real-world applications is to avoid conflicting elements in the solution of problems. Given an undirected graph \(G=(V, E)\) where each edge \(e\in E\) has a positive integer weight \(\omega (e)\), and a conflict graph \(\hat{G}=(\hat{V}, \hat{E})\) such that \(\hat{V}\subseteq E\) and each edge \(\hat{e}=(e_1, e_2) \in \hat{E}\) represents a conflict between two edges \(e_1, e_2 \in E\), in the Minimum Conflict-Free Spanning Tree (MCFST) problem we are asked to find (if any) a spanning tree avoiding pairs of conflicting edges (conflict-free) with minimum cost, i.e., a minimum solution among spanning trees T such that E(T) is an independent set of \(\hat{G}\). A spanning tree T of G is a feasible solution for an instance \(I=(G,\hat{G})\) of MCFST if E(T) is an independent set of \(\hat{G}\). In contrast to the polynomial-time solvability of Minimum Spanning Tree, to determine whether an instance \(I=(G,\hat{G})\) of MCFST admits a feasible solution is \(\mathcal {NP}\)-complete. In this paper, we present a multivariate complexity analysis of MCFST by considering particular classes of graphs G and \(\hat{G}\). In particular, we show that the problem of determining whether an instance \(I=(G,\hat{G})\) of MCFST has a feasible solution is \(\mathcal {NP}\)-complete even if G is a bipartite planar subcubic graph, and \(\hat{G}\) is a disjoint union of paths of size three (\(P_3\)). Moreover, we show that whether G is a complete graph and \(\hat{G}\) is a disjoint union of stars, then a feasible solution for \(I=(G,\hat{G})\) can be found in polynomial time. In addition, we present (in)approximability results for MCFST on complete graphs G, and an FPT algorithm parameterized by the distance to \(\mathcal F\) of the conflict graph \(\hat{G}\), where \(\mathcal F\) is a hereditary graph class such that MCFST on conflict graphs \(\hat{G}\in \mathcal F\) can be solved in polynomial time.

B\(_{0}\)-VPG graphs are intersection graphs of axis-parallel line segments in the plane. We show that all AT-free outerplanar graphs are B\(_{0}\)-VPG. In the course of the argument, we show that any AT-free outerplanar graph can be identified as an induced subgraph of a 2-connected outerplanar graph whose weak dual is a path. Our B\(_{0}\)-VPG drawing procedure works for such graphs and has the potential to be extended to larger classes of outerplanar graphs.

We investigate the complexity of finding a minimum Steiner tree in new subclasses of split graphs namely tree-convex split graphs and circular-convex split graphs. It is known that the Steiner tree problem (STREE) is NP-complete on split graphs [1]. To strengthen this result, we introduce convex ordering on one of the partitions (clique or independent set), and prove that STREE is polynomial-time solvable for tree-convex split graphs with convexity on clique (K), whereas STREE is NP-complete on tree-convex split graphs with convexity on independent set (I). Further, we show that STREE is polynomial-time solvable for path (triad)-convex split graphs with convexity on I, and circular-convex split graphs. Finally, we show that STREE can be used as a framework for the dominating set problem in split graphs, and hence the complexity of STREE and the dominating set problem is the same for all these graph classes.

A k-cd-coloring of a graph G is a partition of the vertex set of G into k independent sets \(V_1,\ldots ,V_k\), where each \(V_i\) is dominated by some vertex of G. The least integer k such that G admits a k-cd-coloring is called the cd-chromatic number, \(\chi _{cd}(G)\), of G. We say that \(S \subseteq V(G)\) is a subclique in G if \(d_G(x,y)\ne 2\) for every \(x,y \in S\). The cardinality of a maximum subclique in G is called the subclique number, \(\omega _s(G)\), of G. Given a graph G and \(k\in \mathbb {N}\), the problem cd-Colorability checks whether \(\chi _{cd}(G)\le k\). The problem cd-Colorability is NP-complete for \(K_4\)-free graphs [Merounane et al., 2014], \(P_5\)-free graphs, and chordal graphs [Shalu et al., 2020]. In this paper, we show that the problem cd-Colorability is \(O(n^2)\)-time solvable in the intersection of the above graph classes (\(\{P_5,K_4\}\)-free chordal graphs). The problem Subclique takes a graph G and \(k \in \mathbb {N}\) as inputs and checks whether \(\omega _s(G)\ge k\). The Subclique problem is NP-complete for \(P_6\)-free graphs and bipartite gaphs [Shalu et al., 2017]. We prove that the problem Subclique is \(O(n^3)\)-time solvable in the class of \(P_6\)-free chordal bipartite graphs (a subclass of \(P_6\)-free bipartite graphs). In addition, we show that the cd-chromatic number and the subclique number are equal in these two graph classes.

First, we present a new algorithm for the single-source shortest paths problem (SSSP) in edge-weighted directed graphs, with n vertices, m edges, and both positive and negative real edge weights. Given a positive integer parameter t,  in O(tm) time the algorithm finds for each vertex v a path distance from the source to v not exceeding that yielded by the shortest path from the source to v among the so called \(t+\)light paths. A directed path between two vertices is \(t+\)light if it contains at most t more edges than the minimum edge-cardinality directed path between these vertices. For \(t=O(n)\), our algorithm yields an O(nm)-time solution to SSSP in directed graphs with real edge weights matching that of Bellman and Ford.

Our main contribution is a new, output-sensitive algorithm for the all-pairs shortest paths problem (APSP) in directed acyclic graphs (DAGs) with positive and negative real edge weights. The running time of the algorithm depends on such parameters as the number of leaves in (lexicographically first) shortest-paths trees, and the in-degrees in the input graph. If the trees are sufficiently thin on the average, the algorithm is substantially faster than the best known algorithm.

Finally, we discuss an extension of hypothetical improved upper time-bounds for APSP in non-negatively edge-weighted DAGs to include directed graphs with a polynomial number of large directed cycles.

Finding densest subgraphs is a fundamental problem in graph mining, with several applications in different fields. In this paper, we consider two variants of the problem of covering a graph with k densest subgraphs, where \(k \ge 2\). The first variant aims to find a collection of k subgraphs of maximum density, the second variant asks for a set of k subgraphs such that they maximize an objective function that includes the sum of the subgraphs densities and a distance function, in order to differentiate the computed subgraphs. We show that the first variant of the problem is solvable in polynomial time, for any \(k \ge 2\). For the second variant, which is NP-hard for \(k \ge 3\), we present an approximation algorithm that achieves a factor of \(\frac{2}{5}\).

We present an algorithm for computing \(\varepsilon \)-coresets for \((k, \ell )\)-median clustering of polygonal curves in \(\mathbb {R}^d\) under the Fréchet distance. This type of clustering is an adaption of Euclidean k-median clustering: we are given a set of n polygonal curves in \(\mathbb {R}^d\), each of complexity (number of vertices) at most m, and want to compute k median curves such that the sum of distances from the given curves to their closest median curve is minimal. Additionally, we restrict the complexity of the median curves to be at most \(\ell \) each, to suppress overfitting, a problem specific for sequential data. Our algorithm has running time linear in n, sub-quartic in m and quadratic in \(\varepsilon ^{-1}\). With high probability it returns \(\varepsilon \)-coresets of size quadratic in \(\varepsilon ^{-1}\) and logarithmic in n and m. We achieve this result by applying the improved \(\varepsilon \)-coreset framework by Langberg and Feldman to a generalized k-median problem over an arbitrary metric space. Later we combine this result with the recent result by Driemel et al. on the VC dimension of metric balls under the Fréchet distance. Furthermore, our framework yields \(\varepsilon \)-coresets for any generalized k-median problem where the range space induced by the open metric balls of the underlying space has bounded VC dimension, which is of independent interest. Finally, we show that our \(\varepsilon \)-coresets can be used to improve the running time of an existing approximation algorithm for \((1,\ell )\)-median clustering.

The paper is devoted to the study of geodetic convex hulls in graphs from a theoretical and practical perspective. The notion of convexity can be transferred from continuous geometry to discrete graph structures by defining a node subset to be (geodetically) convex if all shortest paths between its members do not leave the subset. The geodetic convex hull of a node set W is the smallest convex superset of W. The hull number of a graph is then defined as the size of the smallest node subset S (called hull set) whose convex hull contains all graph nodes. In contrast to the geometric setting, where the point subset on the boundary of the convex hull can be computed in polynomial time, it is NP-hard to decide whether a graph has a hull set of size at most \(s \in \mathbb {N}\). We establish novel theoretical bounds for graph parameters related to convex graph structures, and also design practical algorithms for upper and lower bounding the hull number. We evaluate the quality of our bounds as well as the performance of the proposed algorithms on road networks and wireless sensor networks of varying size.

In this paper, we study the single-round geodesic Voronoi games on various classes of polygons and polyhedra for two players. We prove some tight bounds on the payoffs, that is, the number of clients served by both the first player, Alice, and the second player, Bob, for orthogonal convex polygons and polyhedra for the \(\mathbb {L} _1\) metric.

For a given integer \(k\ge 2\), partitioning a connected graph into k vertex-disjoint connected subgraphs of similar (or fixed) orders is a classical problem that has been intensively investigated since late seventies. A connected k-partition of a graph is a partition of its vertex set into classes such that each one induces a connected subgraph. Given a connected graph \(G = (V, E)\) and a weight function \(w : V \rightarrow \mathbb {Q}_\ge \), the balanced connected k-partition problem looks for a connected k-partition of G into classes of roughly the same weight. To model this concept of balance, we seek connected k-partitions that either maximize the weight of a lightest class \((\textsc {max}\hbox {-}\textsc {min\,\,BCP}_k)\) or minimize the weight of a heaviest class \((\textsc {min}\hbox {-}\textsc {max\,\,BCP}_k)\). These problems, known to be NP-hard, are equivalent only when \(k=2\). We present a simple pseudo-polynomial \(\frac{k}{2}\)-approximation algorithm for \(\textsc {min}\hbox {-}\textsc {max\,\,BCP}_k\) that runs in time \(\mathcal {O}(W|V||E|)\), where \(W = \sum _{v \in V} w(v)\); then, using a scaling technique, we obtain a (polynomial) \((\frac{k}{2} +{\varepsilon })\)-approximation with running-time \(\mathcal {O}(|V|^3|E|/{\varepsilon })\), for any fixed \({\varepsilon }>0\). Additionally, we propose a fixed-parameter tractable algorithm for the unweighted \(\textsc {max}\hbox {-}\textsc {min\,\,BCP}\) (where k is part of the input) parameterized by the size of a vertex cover.

In the online car-sharing (a.k.a. ride-sharing) problem, we are given a set of m available car, and n requests arrive sequentially in T periods, in which each request consists of a pick-up location and a drop-off location. In each period, we must immediately and irrevocably assign free cars to serve arrived requests, such that two requests share one car. The goal is to find an online algorithm to process all requests while minimizing the total travel distance of cars.

We give the first algorithm for this problem under the adversarial model and the random arrival model. For the adversarial model, we give a \(2T+1/2\)-competitive algorithm, then we show this can be further improved to 2T-competitive by a carefully designed edge cost function. This almost matches the known \(2T-1\) lower bound in this model. For the random arrival model, our algorithm is \(3H_T-1/2+o(1)\)-competitive, where \(H_T\) is the T-th harmonic number. All the above three results are based on one single algorithm that runs in \(O(n^3)\) time.

Given \((a_1, \dots , a_n, t) \in \mathbb {Z}_{\ge 0}^{n + 1}\), the Subset Sum problem (\(\mathsf {SSUM}\)) is to decide whether there exists \(S \subseteq [n]\) such that \(\sum _{i \in S} a_i = t\). Bellman (1957) gave a pseudopolynomial time dynamic programming algorithm which solves the Subset Sum in O(nt) time and O(t) space.

In this work, we present search algorithms for variants of the Subset Sum problem. Our algorithms are parameterized by k, which is a given upper bound on the number of realisable sets (i.e. number of solutions, summing exactly t). We show that \(\mathsf {SSUM}\) with a unique solution is already \(\mathsf {NP}\)-hard, under randomized reduction. This makes the regime of parametrized algorithms, in terms of k, very interesting.

Subsequently, we present an \(\tilde{O}(k\cdot (n+t))\) time deterministic algorithm, which finds the hamming weight of all the realisable sets for a subset sum instance. We also give a \({\mathsf {poly}}(knt)\)-time and \(O(\log (knt))\)-space deterministic algorithm that finds all the realisable sets for a subset sum instance. Our algorithms use analytic and number-theoretic techniques.

We study several key variants of SMTI - Stable Marriage problem in which the preference lists may contain ties and may be incomplete. A matching is called weakly stable unless there is a man and a woman such that they are currently not matched with each other but if they get matched with each other, then both of them become better off. The COM SMTI problem is to decide whether there exists a complete (in which all men and women are matched) weakly stable matching in an SMTI instance. It is known that the COM SMTI problem is NP-complete. We strengthen this result by proving that this problem remains NP-complete even for the instance SMTI-C, instance where members in each preference list are consecutive with respect to some orderings of the set of men and set of women. On the positive side, we give a polynomial time algorithm for COM SMTI problem for the instance SMTI-STEP, where the preference lists admit step-property, that is, preference list of every man \(m_i\) is the set of all women \(w_j\) such that \(j \le i\) for some ordering of men and some ordering of women. Further, DECIDE_MAX SMTI (resp. DECIDE_MIN SMTI) is the decision version of MAX SMTI (resp. MIN SMTI), the problem of finding a weakly stable matching of maximum (resp. minimum) cardinality in an SMTI instance. Both DECIDE_MAX SMTI and DECIDE_MIN SMTI problems are known to be NP-complete. We improve these results by showing that DECIDE_MAX SMTI and DECIDE_MIN SMTI problems remain NP-complete even for the case where the preference lists admit inclusion ordering and even for the case where the preference lists admit step-property, respectively. Finally, we present a 3/2-approximation algorithm for the MIN SMTI problem with inclusion ordering.

We study the computational complexity of finding fair allocations of indivisible goods in the setting where a social network on the agents is given. Notions of fairness in this context are “localized”, that is, agents are only concerned about the bundles allocated to their neighbors, rather than every other agent in the system. We comprehensively address the computational complexity of finding locally envy-free and Pareto efficient allocations in the setting where the agents have binary valuations for the goods and the underlying social network is modeled by an undirected graph. We study the problem in the framework of parameterized complexity.

We show that the problem is computationally intractable even in fairly restricted scenarios, for instance, even when the underlying graph is a path. We show NP-hardness for settings where the graph has only two distinct valuations among the agents. We demonstrate W-hardness with respect to the number of goods or the size of the vertex cover of the underlying graph. We also consider notions of proportionality that respect the structure of the underlying graph.

The Defensive Alliance problem has been studied extensively during the last twenty years. A set R of vertices of a graph is a defensive alliance if, for each element of R, the majority of its neighbours are in R. The problem of finding a defensive alliance of minimum size in a given graph is NP-hard. Fixed-parameter tractability results have been obtained for the solution size and some structural parameters such as the vertex cover number and neighbourhood diversity. For the parameter treewidth the problem is W[1]-hard. However, for the parameters pathwidth and feedback vertex set, the question of whether the problem is FPT has remained open. In this work we prove that (1) the Defensive Alliance problem is W[1]-hard when parameterized by the pathwidth of the input graph, (2) the Exact Defensive Alliance problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, treewidth and treedepth and (3) a generalization of the Defensive Alliance problem is W[1]-hard parameterized by the size of a vertex deletion set into trees of height at most 6.

In the field of transportation planning, it is often insufficient to model transportation networks by using networks with fixed arc costs. There may be additional factors that modify the time or cost of a single trip. These include turn prohibitions, fare rebates, and transfer times. Each of these factors causes the cost of a portion of the trip to depend directly on the previous portion of the trip. This dependence can be modeled using arc-dependent networks. In an arc-dependent network, the cost of an arc a depends upon the arc used to enter a. In this paper, we study the approximability of a number of negative cost cycle problems in arc-dependent networks. In a general network, the cost of an arc is a fixed constant and part of the input. Arc-dependent networks can be used to model several real-world problems, including the turn-penalty shortest path problem. Previous literature established that corresponding path problems in these networks are NP-hard. We extend that research by providing inapproximability results for several of these problems. In [7], it was established that a more general form of the shortest path problem in arc-dependent networks, known as the quadratic shortest path problem, cannot be approximated to within a constant factor. In this paper, we strengthen that result by showing NPO PB-completeness.

Broadcasting is an information dissemination problem in a connected network in which one node, called the originator, must distribute a message to all other nodes of the network by placing a series of calls along the communication lines of the network. The broadcast time of a vertex is defined to be the minimum number of time units required to broadcast the message to all vertices of the graph (network) from that vertex. Finding the broadcast time of any vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for certain tree-like graphs. In this paper we study the broadcast problem in graph of trees where broadcast algorithms for the base graph is known. In such graphs we design a linear time constant approximation algorithm to determine the broadcast time of any originator in general case. In a particular case when the base graph is the hypercube or another minimum broadcast graph (graph with minimum possible broadcast time having the smallest number of edges) containing one tree we present a linear time exact algorithm to find the broadcast time of any originator vertex. When the base graph is the hypercube graph we improve the known result by presenting a 1.5-approximation algorithm to find the broadcast time of the whole graph which runs in linear time instead of known quadratic algorithm.