Maadapuzhi-Sridharan Ramanujan

In this paper, we study the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure every strongly connected component of the resulting digraph is Eulerian. This problem is a natural extension of the Directed Feedback Arc Set problem and is also known to be motivated by certain scenarios arising in the study of housing markets. The complexity of the problem, when parameterized by solution size (i.e., size of the deletion set), has remained unresolved and has been highlighted in several papers. In this work, we answer this question by ruling out (subject to the usual complexity assumptions) a fixed-parameter algorithm (FPT algorithm) for this parameter and conduct a broad analysis of the problem with respect to other natural parameterizations. We prove both positive and negative results. Among these, we demonstrate that the problem is also hard (W[1]-hard or even para-NP-hard) when parameterized by either treewidth or maximum degree alone. Complementing our lower bounds, we establish that the problem is in XP when parameterized by treewidth and FPT when parameterized either by both treewidth and maximum degree or by both treewidth and solution size. We show that on simple digraphs, these algorithms have near-optimal asymptotic dependence on the treewidth assuming the Exponential Time Hypothesis.

Majority illusion occurs in a social network when the majority of the network vertices belong to a certain type but the majority of each vertex's neighbours belong to a different type, therefore creating the wrong perception, i.e., the illusion, that the majority type is different from the actual one. From a system engineering point of view, this motivates the search for algorithms to detect and, where possible, correct this often undesirable phenomenon. In this we provide a computational study of majority illusion in social networks, paying particular attention to the problem of its verification, i.e., whether majority illusion can occur on social networks, and elimination, i.e., how can we eliminate majority illusion by social network rewiring. While we show that the problems we consider are generally NP-complete, we also provide a parameterised complexity analysis, showing FPT-algorithms for the detection problem and W[1]-hardness for the elimination problem, using natural graph-theoretic parameters.

In the Directed Feedback Vertex Set (DFVS) problem, given a digraph D and a positive integer k , the goal is to check if there exists a set of at most k vertices whose deletion from D results in a directed acyclic graph. The existence of a polynomial kernel for DFVS , parameterized by the solution size k , is a central open problem in kernelization. In this article, we give a polynomial kernel for DFVS parameterized by k plus the size of a treewidth-η modulator (of the underlying undirected graph), where η is any fixed positive integer. Since the status of the existence of a polynomial kernel for DFVS (parameterized by the solution size) has been open for a very long time now, and it is known to not admit a polynomial kernel when the parameter is the size of a treewidth-2 modulator, solution size plus the size of the treewidth-η modulator makes for an interesting choice of parameter to study. In fact, the polynomial kernelization complexity of DFVS parameterized by the size of the undirected feedback vertex set (treewidth-1 modulator) in the underlying undirected graph has already been studied in literature. Our choice of parameter strictly encompasses previous positive kernelization results on DFVS . Our result is based on a novel application of the tool of important separators embedded in state-of-the-art machinery such as protrusion decompositions.

In many real-world routing problems, decision makers must optimise over sparse graphs such as transportation networks with non-metric costs on the edges that do not obey the triangle inequality. Motivated by finding a sufficiently long running route in a city that minimises the air pollution exposure of the runner, we study the Prize-collecting Travelling Salesperson Problem (Pc-TSP) on sparse graphs with non-metric costs. Given an undirected graph with a cost function on the edges and a prize function on the vertices, the goal of Pc-TSP is to find a tour rooted at the origin that minimises the total cost such that the total prize is at least some quota. First, we introduce heuristics designed for sparse graphs with non-metric cost functions where previous work dealt with either a complete graph or a metric cost function. Next, we develop a branch & cut algorithm that employs a new cut we call the disjoint-paths cost-cover (DPCC) cut. Empirical experiments on two datasets show that our heuristics can produce a feasible solution with less cost than a state-of-the-art heuristic from the literature. On datasets with non-metric cost functions, DPCC is found to solve more instances to optimality than the baseline cutting algorithm we compare against.

In this paper, we study the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure every strongly connected component of the resulting digraph is Eulerian. This problem is a natural extension of the Directed Feedback Arc Set problem and is also known to be motivated by certain scenarios arising in the study of housing markets. The complexity of the problem, when parameterized by solution size (i.e., size of the deletion set), has remained unresolved and has been highlighted in several papers. In this work, we answer this question by ruling out (subject to the usual complexity assumptions) a fixed-parameter tractable (FPT) algorithm for this parameter and conduct a broad analysis of the problem with respect to other natural parameterizations. We prove both positive and negative results. Among these, we demonstrate that the problem is also hard (W[1]-hard or even para-NP-hard) when parameterized by either treewidth or maximum degree alone. Complementing our lower bounds, we establish that the problem is in XP when parameterized by treewidth and FPT when parameterized either by both treewidth and maximum degree or by both treewidth and solution size. We show that these algorithms have near-optimal asymptotic dependence on the treewidth assuming the Exponential Time Hypothesis.