Search

We investigate whether algorithms based on arithmetic circuits are a viable alternative to existing solvers for Graph Inspection, a problem with direct application in robotic motion planning. Specifically, we seek to address the high memory usage of existing solvers. Aided by novel theoretical results enabling fast solution recovery, we implement a circuit-based solver for Graph Inspection which uses only polynomial space and test it on several realistic robotic motion planning datasets. In particular, we provide a comprehensive experimental evaluation of a suite of engineered algorithms for three key subroutines. While this evaluation demonstrates that circuit-based methods are not yet practically competitive for our robotics application, it also provides insights which may guide future efforts to bring circuit-based algorithms from theory to practice.

The NP-hard Odd Cycle Transversal problem asks for a minimum vertex set whose removal from an undirected input graph $G$ breaks all odd cycles, and thereby yields a bipartite graph. The problem is well-known to be fixed-parameter tractable when parameterized by the size $k$ of the desired solution. It also admits a randomized kernelization of polynomial size, using the celebrated matroid toolkit by Kratsch and Wahlstr\"{o}m. The kernelization guarantees a reduction in the total $\textit{size}$ of an input graph, but does not guarantee any decrease in the size of the solution to be sought; the latter governs the size of the search space for FPT algorithms parameterized by $k$. We investigate under which conditions an efficient algorithm can detect one or more vertices that belong to an optimal solution to Odd Cycle Transversal. By drawing inspiration from the popular $\textit{crown reduction}$ rule for Vertex Cover, and the notion of $\textit{antler decompositions}$ that was recently proposed for Feedback Vertex Set, we introduce a graph decomposition called $\textit{tight odd cycle cut}$ that can be used to certify that a vertex set is part of an optimal odd cycle transversal. While it is NP-hard to compute such a graph decomposition, we develop parameterized algorithms to find a set of at least $k$ vertices that belong to an optimal odd cycle transversal when the input contains a tight odd cycle cut certifying the membership of $k$ vertices in an optimal solution. The resulting algorithm formalizes when the search space for the solution-size parameterization of Odd Cycle Transversal can be reduced by preprocessing. To obtain our results, we develop a graph reduction step that can be used to simplify the graph to the point that the odd cycle cut can be detected via color coding.

Autonomous robotic inspection, where a robot moves through its environment and inspects points of interest, has applications in industrial settings, structural health monitoring, and medicine. Planning the paths for a robot to safely and efficiently perform such an inspection is an extremely difficult algorithmic challenge. In this work we consider an abstraction of the inspection planning problem which we term Graph Inspection. We give two exact algorithms for this problem, using dynamic programming and integer linear programming. We analyze the performance of these methods, and present multiple approaches to achieve scalability. We demonstrate significant improvement both in path weight and inspection coverage over a state-of-the-art approach on two robotics tasks in simulation, a bridge inspection task by a UAV and a surgical inspection task using a medical robot.

Large networks are useful in a wide range of applications. Sometimes problem instances are composed of billions of entities. Decomposing and analyzing these structures helps us gain new insights about our surroundings. Even if the final application concerns a different problem (such as traversal, finding paths, trees, and flows), decomposing large graphs is often an important subproblem for complexity reduction or parallelization. This report is a summary of discussions that happened at Dagstuhl seminar 23331 on "Recent Trends in Graph Decomposition" and presents currently open problems and future directions in the area of (hyper)graph decomposition.

We present fixed-parameter tractable (FPT) algorithms for two problems, Maximum Happy Set (MaxHS) and Maximum Edge Happy Set (MaxEHS)--also known as Densest k-Subgraph. Given a graph $G$ and an integer $k$, MaxHS asks for a set $S$ of $k$ vertices such that the number of $\textit{happy vertices}$ with respect to $S$ is maximized, where a vertex $v$ is happy if $v$ and all its neighbors are in $S$. We show that MaxHS can be solved in time $\mathcal{O}\left(2^\textsf{mw} \cdot \textsf{mw} \cdot k^2 \cdot |V(G)|\right)$ and $\mathcal{O}\left(8^\textsf{cw} \cdot k^2 \cdot |V(G)|\right)$, where $\textsf{mw}$ and $\textsf{cw}$ denote the $\textit{modular-width}$ and the $\textit{clique-width}$ of $G$, respectively. This resolves the open questions posed in literature. The MaxEHS problem is an edge-variant of MaxHS, where we maximize the number of $\textit{happy edges}$, the edges whose endpoints are in $S$. In this paper we show that MaxEHS can be solved in time $f(\textsf{nd})\cdot|V(G)|^{\mathcal{O}(1)}$ and $\mathcal{O}\left(2^{\textsf{cd}}\cdot k^2 \cdot |V(G)|\right)$, where $\textsf{nd}$ and $\textsf{cd}$ denote the $\textit{neighborhood diversity}$ and the $\textit{cluster deletion number}$ of $G$, respectively, and $f$ is some computable function. This result implies that MaxEHS is also fixed-parameter tractable by $\textit{twin cover number}$.

Mining groups of genes that consistently co-express is an important problem in biomedical research, where it is critical for applications such as drug-repositioning and designing new disease treatments. Recently, Cooley et al. modeled this problem as Exact Weighted Clique Decomposition (EWCD) in which, given an edge-weighted graph $G$ and a positive integer $k$, the goal is to decompose $G$ into at most $k$ (overlapping) weighted cliques so that an edge's weight is exactly equal to the sum of weights for cliques it participates in. They show EWCD is fixed-parameter-tractable, giving a $4^k$-kernel alongside a backtracking algorithm (together called cricca) to iteratively build a decomposition. Unfortunately, because of inherent exponential growth in the space of potential solutions, cricca is typically able to decompose graphs only when $k \leq 11$. In this work, we establish reduction rules that exponentially decrease the size of the kernel (from $4^k$ to $k2^k$) for EWCD. In addition, we use insights about the structure of potential solutions to give new search rules that speed up the decomposition algorithm. At the core of our techniques is a result from combinatorial design theory called Fisher's inequality characterizing set systems with restricted intersections. We deploy our kernelization and decomposition algorithms (together called DeCAF) on a corpus of biologically-inspired data and obtain over two orders of magnitude speed-up over cricca. As a result, DeCAF scales to instances with $k \geq 17$., Comment: 11 pages, 7 figures

A primary challenge in metagenomics is reconstructing individual microbial genomes from the mixture of short fragments created by sequencing. Recent work leverages the sparsity of the assembly graph to find $r$-dominating sets which enable rapid approximate queries through a dominator-centric graph partition. In this paper, we consider two problems related to reducing uncertainty and improving scalability in this setting. First, we observe that nodes with multiple closest dominators necessitate arbitrary tie-breaking in the existing pipeline. As such, we propose finding $\textit{sparse}$ dominating sets which minimize this effect via a new $\textit{congestion}$ parameter. We prove minimizing congestion is NP-hard, and give an $\mathcal{O}(\sqrt{\Delta^r})$ approximation algorithm, where $\Delta$ is the max degree. To improve scalability, the graph should be partitioned into uniformly sized pieces, subject to placing vertices with a closest dominator. This leads to $\textit{balanced neighborhood partitioning}$: given an $r$-dominating set, find a partition into connected subgraphs with optimal uniformity so that each vertex is co-assigned with some closest dominator. Using variance of piece sizes to measure uniformity, we show this problem is NP-hard iff $r$ is greater than $1$. We design and analyze several algorithms, including a polynomial-time approach which is exact when $r=1$ (and heuristic otherwise). We complement our theoretical results with computational experiments on a corpus of real-world networks showing sparse dominating sets lead to more balanced neighborhood partitionings. Further, on the metagenome $\textsf{HuSB1}$, our approach maintains high query containment and similarity while reducing piece size variance.