Abstract Low-treedepth colorings are an important tool for algorithms that exploit structure in classes of bounded expansion; they guarantee subgraphs that use few colors have bounded treedepth. These colorings have an implicit tradeoff between the total number of colors used and the treedepth bound, and prior empirical work suggests that the former dominates the run time of existing algorithms in practice. We introduce p-linear colorings as an alternative to the commonly used p-centered colorings. They can be efficiently computed in bounded expansion classes and use at most as many colors as p-centered colorings. Although a set of $$k k < p colors from a p-centered coloring induces a subgraph of treedepth at most k, the same number of colors from a p-linear coloring may induce subgraphs of larger treedepth. We establish a polynomial upper bound on the treedepth in general graphs, and give tighter bounds in trees and interval graphs via constructive coloring algorithms. We also give a co-NP-completeness reduction for recognizing p-linear colorings and discuss ways to overcome this limitation in practice.

The Flow Decomposition problem, which asks for the smallest set of weighted paths that “covers” a flow on a DAG, has recently been used as an important computational step in transcript assembly. We prove the problem is in FPT when parameterized by the number of paths by giving a practical linear fpt algorithm. Further, we implement and engineer a Flow Decomposition solver based on this algorithm, and evaluate its performance on RNA-sequence data. Crucially, our solver finds exact solutions while achieving runtimes competitive with a state-of-the-art heuristic. Finally, we contextualize our design choices with two hardness results related to preprocessing and weight recovery. Specifically, k-Flow Decomposition does not admit polynomial kernels under standard complexity assumptions, and the related problem of assigning (known) weights to a given set of paths is NP-hard.

We study the computational complexity of identifying dense substructures, namely r/2-shallow topological minors and r-subdivisions. Of particular interest is the case r = 1, when these substructures correspond to very localized relaxations of subgraphs. Since Densest Subgraph can be solved in polynomial time, we ask whether these slight relaxations also admit efficient algorithms. In the following, we provide a negative answer: Dense r/2-Shallow Topological Minor and Dense r-Subdivsion are already NP-hard for r = 1 in very sparse graphs. Further, they do not admit algorithms with running time 2^(o(tw^2)) n^O(1) when parameterized by the treewidth of the input graph for r > 2 unless ETH fails.

Growing interest in modeling large, complexnetworks has spurred significant research into generative graphmodels. Kronecker-style models (e.g. SKG and R-MAT) are oftenused due to their scalability and ability to mimic key propertiesof real-world networks. Although a few papers theoreticallyestablish these models' behavior for specific parameters, manyclaims used to justify their use are supported only empirically. In this work, we prove several results using asymptotic analysiswhich illustrate that empirical studies may not fully capture thetrue behavior of the models. Paramount to the widespread adoption of Kronecker-stylemodels was the introduction of a linear-time edge-samplingvariant (R-MAT), which existing literature typically treats asinterchangeable with SKG. We prove that although several R-MAT formulations are asymptotically equivalent, their behaviordiverges from that of SKG. Further, we show these resultsare observable even at relatively small graph sizes. Second, weconsider a case where asymptotic analysis reveals unexpectedbehavior within a given model.

Graphs are a powerful way to model interactions and relationships in data from a wide variety of application domains. In this setting, entities represented by vertices at the 'center' of the graph are often more important than those associated with vertices on the 'fringes'. For example, central nodes tend to be more critical in the spread of information or disease and play an important role in clustering/community formation. Identifying such 'core' vertices has recently received additional attention in the context of network experiments, which analyze the response when a random subset of vertices are exposed to a treatment (e.g. Inoculation, free product samples, etc). Specifically, the likelihood of having many central vertices in any exposure subset can have a significant impact on the experiment. We focus on using k-cores and core numbers to measure the extent to which a vertex is central in a graph. Existing algorithms for computing the core number of a vertex require the entire graph as input, an unrealistic scenario in many real world applications. Moreover, in the context of network experiments, the sub graph induced by the treated vertices is only known in a probabilistic sense. We introduce a new method for estimating the core number based only on the properties of the graph within a region of radius δ around the vertex, and prove an asymptotic error bound of our estimator on random graphs. Further, we empirically validate the accuracy of our estimator for small values of δ on a representative corpus of real data sets. Finally, we evaluate the impact of improved local estimation on an open problem in network experimentation posed by Ugander et al.

Community detection in real-world graphs presents a number of challenges. First, even if the number of detected communities grows linearly with the graph size, it becomes impossible to manually inspect each community for value added to the application knowledge base. Mining for communities with query nodes as knowledge priors could allow for filtering out irrelevant information and for enriching end-users knowledge associated with the problem of interest, such as discovery of genes functionally associated with the Alzheimer's (AD) biomarker genes. Second, the data-intensive nature of community enumeration challenges current approaches that often assume that the input graph and the detected communities fit in memory. As computer systems scale, DRAM memory sizes are not expected to increase linearly, while technologies such as SSD memories have the potential to provide much higher capacities at a lower power-cost point, and have a much lower latency than disks. Out-of-core algorithms and/or database-inspired indexing could provide an opportunity for different design optimizations for query-driven community detection algorithms tuned for emerging architectures. Therefore, this work addresses the need for query-driven and memory-efficient community detection. Using maximal cliques as the community definition, due to their high signal-to-noise ratio, we propose and systematically compare two contrasting methods: indexed-based and out-of-core. Both methods improve peak memory efficiency as much as 1000X compared to the state-of-the-art. However, the index-based method, which also has a 10-to-100-fold run time reduction, outperforms the out-of-core algorithm in most cases. The achieved scalability enables the discovery of diseases that are known to be or likely associated with Alzheimer's when the genome-scale network is mined with AD biomarker genes as knowledge priors.

It is the view of many computer scientists that the standard of empirical software engineering research leaves scope for improvement. However, there is also an increasing awareness in the software engineering community that empirical studies are a vital aspect in the process of improving methods and tools, for software development and maintenance. This paper presents a review of the empirical work carried out to date in the area of program comprehension and illustrates that most of the evidence from these studies derives from lab-based experiments, thus implying a degree of artificial control. The paper argues that, in order to address the methodological shortfalls of the experimental paradigm, more qualitative methods need to be applied to accompany and support these quantitative studies, thus broadening the sources of data and increasing the 'body of evidence'.

Abstract The software comprehension process has been conceptualized as being either ‘top‐down’ or ‘bottom‐up’ in nature. We formally distinguish between two comprehension processes that have previously been grouped together as ‘top‐down’. The first is ‘expectation‐based’ comprehension, where the programmer has pre‐generated expectations of the code's meaning. The second is ‘inference‐based’ comprehension, where the programmer derives meaning from clichéd implementations in the code. We identify the distinguishing features of the two variants, and use these characteristics as the basis for an empirical study. This study establishes the existence of the above‐mentioned processes, in conjunction with ‘bottom‐up’ comprehension. It also illustrates the relationship between these processes and programmers' application domain familiarity. Copyright © 2004 John Wiley & Sons, Ltd.