Journal Papers

Modern applications of graph algorithms often involve the use of the output sets (usually, a subset of edges or vertices of the input graph) as inputs to other algorithms. Since the input graphs of interest are large and dynamic, it is desirable for an algorithm’s output to not change drastically when a few random edges are removed from the input graph in order to prevent issues in postprocessing. Alternately, having such a guarantee also means that one can revise the solution obtained by running the algorithm on the original graph in just a few places in order to obtain a solution for the new graph. We formalize this feature by introducing the notion of average sensitivity of graph algorithms, which is the average earth mover’s distance between the output distributions of an algorithm on a graph and its subgraph obtained by removing an edge, where the average is over the edges removed and the distance between two outputs is the Hamming distance. In this work, we initiate a systematic study of average sensitivity of graph algorithms. After deriving basic properties of average sensitivity such as composition, we provide efficient ap- proximation algorithms with low average sensitivities for concrete graph problems, including the minimum spanning forest problem, the global minimum cut problem, the minimum s-t cut problem, and the maximum matching problem. In addition, we prove that the average sensitivity of our global minimum cut algorithm is almost optimal, by showing a nearly matching lower bound. We also show that every algorithm for the 2-coloring problem has average sensitivity linear in the number of vertices. One of the main ideas involved in designing our algorithms with low average sensitivity is the following fact; if the presence of a vertex or an edge in the solution output by an algorithm can be decided locally, then the algorithm has a low average sensitivity, allowing us to reuse the analyses of known sublinear-time algorithms and local computation algorithms. Using this fact in conjunction with our average sensitivity lower bound for 2-coloring, we show that every local computation algorithm for 2-coloring has query complexity linear in the number of vertices, thereby answering an open question.

Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is large gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat \(1-1/e\) in the single-pass streaming model. Let \(n\) be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio \(2-\sqrt{2}+\epsilon\) requires \(\Omega(n/K)\) space for any \(\epsilon>0\), where \(K\) is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio \(K/(2K-1)+\epsilon\) requires \(\Omega(n/K^2)\) space for any \(\epsilon>0\), where \(K\) is the rank of the given matroid. In addition, we give streaming algorithms that assume access to the objective function via a weak oracle that can only be used to evaluate function values on feasible sets. Specifically, we show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios \(K/(2K-1)\) and \(1/2\), respectively, whose space complexity is exponential in \(K\) but is independent of \(n\). The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of \(K/(2K-1)\) for a matroid constraint, which almost settles the approximation ratio for a matroid constraint that can be obtained by a streaming algorithm whose space complexity is independent of \(n\).

For a size parameter \(s:\mathbb{N}\to\mathbb{N}\), the Minimum Circuit Size Problem (denoted by \(\mathrm{MCSP}[s(n)]\)) is the problem of deciding whether the minimum circuit size of a given function \(f : \{0,1\}^n \to \{0,1\}\) (represented by a string of length \(N := 2^n\)) is at most a threshold \(s(n)\). A recent line of work exhibited ``hardness magnification'' phenomena for MCSP: A very weak lower bound for MCSP implies a breakthrough result in complexity theory. For example, McKay, Murray, and Williams (STOC 2019) implicitly showed that, for some constant \(\mu_1 > 0\), if \(\mathrm{MCSP}[2^{\mu_1\cdot n}]\) cannot be computed by a one-tape Turing machine (with an additional one-way read-only input tape) running in time \(N^{1.01}\), then \(\mathrm{P}\neq\mathrm{NP}\).

In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs:

• A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute \(\mathrm{MCSP}[2^{\mu_2\cdot n}]\) in time \(N^{1.99}\), for some constant \(\mu_2 > \mu_1\).
• A non-deterministic (or parity) branching program of size \(o(N^{1.5}/\log N)\) cannot compute MKTP, which is a time-bounded Kolmogorov complexity analogue of MCSP. This is shown by directly applying the Ne\v{c}iporuk method to MKTP, which previously appeared to be difficult.
• The size of any non-deterministic, co-non-deterministic, or parity branching program computing MCSP is at least \(N^{1.5-o{1}}\).

These results are the first non-trivial lower bounds for MCSP and MKTP against one-tape Turing machines and non-deterministic branching programs, and essentially match the best-known lower bounds for any explicit functions against these computational models.

The first result is based on recent constructions of pseudorandom generators for read-once oblivious branching programs (ROBPs) and combinatorial rectangles (Forbes and Kelley, FOCS 2018; Viola 2019). En route, we obtain several related results:

• There exists a (local) hitting set generator with seed length \(\widetilde{O}(\sqrt{N})\) secure against read-once polynomial-size non-deterministic branching programs on \(N\)-bit inputs.
• Any read-once co-non-deterministic branching program computing MCSP must have size at least \(2^{\widetilde{\Omega}(N)}\).

Cheeger’s inequality states that a tightly connected subset can be ex- tracted from a graph \(G\) using an eigenvector of the normalized Laplacian associated with \(G\). More specifically, we can compute a vertex subset in \(G\) with conductance \(O(\sqrt{\phi_G})\), where \(\phi_G\) is the minimum conductance of \(G\). It has recently been shown that Cheeger’s inequality can be extended to hypergraphs. However, as the normalized Laplacian of a hypergraph is no longer a matrix, we can only approximate its eigenvectors; this causes a loss in the conductance of the obtained subset. To address this problem, we here consider the heat equation on hypergraphs, which is a differential equation exploiting the normalized Laplacian. We show that the heat equation has a unique global solution and that we can extract a subset with conductance \(\sqrt{\phi_G}\) from the solution under a mild condition. An analogous result also holds for directed graphs.

We present a polynomial-time online algorithm for maximizing the conditional value at risk (CVaR) of a monotone stochastic submodular function. Given \(T\) i.i.d.\ samples from an underlying distribution arriving online, our algorithm produces a sequence of solutions that converges to a (\(1-1/e\))-approximate solution with a convergence rate of \(O(T^{-1/4})\) for monotone continuous DR-submodular functions. Compared with previous offline algorithms, which require \(\Omega(T)\) space, our online algorithm only requires \(O(\sqrt{T})\) space. We extend our online algorithm to portfolio optimization for monotone submodular set functions under a matroid constraint. Experiments conducted on real-world datasets demonstrate that our algorithm can rapidly achieve CVaRs that are comparable to those obtained by existing offline algorithms.

Let \(G=(V,E)\) be an undirected graph, \(L_G\in \mathbb{R}^{V \times V}\) be the associated Laplacian matrix, and \({\bf b} \in \mathbb{R}^V\) be a vector. Solving the Laplacian system \(L_G {\bf x} = {\bf b}\) has numerous applications in theoretical computer science, machine learning, and network analysis. Recently, the notion of the Laplacian operator \(L_F\colon \mathbb{R}^V \to 2^{\mathbb{R}^V}\) for a submodular transformation \(F\colon 2^V \to \mathbb{R}_+^E\) was introduced, which can handle undirected graphs, directed graphs, hypergraphs, and joint distributions in a unified manner. In this study, we show that the submodular Laplacian system \(L_F({\bf x}) \ni {\bf b}\) can be solved in polynomial time. Furthermore, we prove that even when the submodular Laplacian system has no solution, we can solve its regression form in polynomial time. Finally, we discuss potential applications of submodular Laplacian systems in machine learning and network analysis.

Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is large gap in our knowledge, even though several approximation algorithms have been proposed in the literature.

In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat \(1 - 1/e\) in the single-pass streaming model. Let n be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio \(2 - \sqrt{2} + \epsilon\) requires \(\Omega(\frac{n}{K^2})\) space for any \(\epsilon > 0\), where \(K\) is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio \(K + \epsilon\) requires \(\Omega(\frac{n}{K^2})\) space for any \(\epsilon > 0\), where \(K\) is the rank of the given matroid.

In addition, we give streaming algorithms that assume access to the objective function via a weak oracle that can only be used to evaluate function values on feasible sets. Specifically, we show weak- oracle streaming algorithms for cardinality and matroid constraints with approximation ratios \(\frac{K}{2K −1}\) and \(\frac{1}{2}\), respectively, whose space complexity is exponential in K but is independent of \(n\). The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of \(\frac{K}{2K −1}\) for a matroid constraint, which almost settles the approximation ratio for a matroid constraint that can be obtained by a streaming algorithm whose space complexity is independent of \(n\).

In this paper, we study the problem of accelerating the linear average consensus algorithm over complex networks. We specifically present a data-driven approach for tuning the weights of temporal (i.e., time-varying) networks by using deep learning techniques. Given a finite-time window, this approach first unfolds the linear average consensus protocol to obtain a feedforward signal-flow graph, which is regarded as a neural network. The edge weights of the obtained neural network are then trained by using standard deep learning technique to minimize the consensus error over a given finite-time window. As a result of the training, we obtain a set of optimized time-varying weights for faster consensus in the complex network. We also show the approach can be extended for infinite-time window problems. Numerical experiments showed that our approach can achieve a significantly smaller consensus error than the baseline strategies.

We consider the subspace proximity problem: Given a vector \(x \in \mathbb{R}^n\) and a basis matrix \(V \in \mathbb{R}^{n \times m}\), the objective is to determine whether \(x\) is close to the subspace spanned by \(V\). Although the problem is solvable by linear programming, it is time consuming especially when \(n\) is large. In this paper, we propose a quick tester that solves the problem correctly with high probability. Our tester runs in time independent of \(n\) and can be used as a sieve before computing the exact distance between \(x\) and the subspace. The number of coordinates of \(x\) queried by our tester is \(O(\frac{m}{\epsilon}\log\frac{m}{\epsilon})\), where \(\epsilon\) is an error parameter, and we show almost matching lower bounds. By experiments, we demonstrate the scalability and applicability of our tester using synthetic and real data sets.

In this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access only to a small fraction of the data stored in primary memory. For this problem, we propose a \((0.363 - \epsilon)\)-approximation algorithm, requiring only a single pass through the data; moreover, we propose a \((0.4-\epsilon)\)-approximation algorithm requiring a constant number of passes through the data. The required memory space of both algorithms depends only on the size of the knapsack capacity and \(\epsilon\).

We consider the problem of maximizing a monotone submodular function under a knapsack constraint. We show that, for any fixed \(\epsilon > 0\), there exists a polynomial-time algorithm with an approximation ratio \(1 - c/e - \epsilon\), where \(c \in [0, 1]\) is the (total) curvature of the input function. This approximation ratio is tight up to \(\epsilon\) for any \(c \in [0,1]\). To the best of our knowledge, this is the first result for a knapsack constraint that incorporates the curvature to obtain an approximation ratio better than \(1 - 1/e\), which is tight for general submodular functions. As an application of our result, we present a polynomial-time algorithm for the budget allocation problem with an improved approximation ratio.

For each finite relational structure \(\mathbf{A}\), let \(\mathrm{CSP}(\mathbf{A})\) denote the CSP instances whose constraint relations are taken from \(\mathbf{A}\). The resulting family of problems \(\mathrm{CSP}(\mathbf{A})\) has been considered heavily in a variety of computational contexts. In this article, we consider this family from the perspective of property testing: given a CSP instance and query access to an assignment, one wants to decide whether the assignment satisfies the instance, or is far from doing so. While previous work on this scenario studied concrete templates or restricted classes of structures, this article presents a comprehensive classification theorem.

Our main contribution is a dichotomy theorem completely characterizing the finite structures \(\mathbf{A}\) such that \(\mathrm{CSP}(\mathbf{A})\) is constant-query testable: - If \(\mathbf{A}\) has a majority polymorphism and a Maltsev polymorphism, then \(\mathrm{CSP}(\mathbf{A})\) is constant-query testable with one-sided error. - Else, testing \(\mathrm{CSP}(\mathbf{A})\) requires a super-constant number of queries.

The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice.

Suppose that a non-negative monotone submodular function \(f:\mathbb{Z}_+^n \to \mathbb{R}_+\) is given via an evaluation oracle. Assume further that \(f\) satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Given this, we design polynomial-time \((1-1/e-\epsilon)\)-approximation algorithms for a cardinality constraint, a polymatroid constraint, and a knapsack constraint. For a cardinality constraint, we also provide a \((1-1/e-\epsilon)\)-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property.

We characterize the set of properties of Boolean-valued functions \(f: \mathcal{X} \to \{0, 1\}\) on a finite domain \(\mathcal{X}\) that are testable with a constant number of samples \((x, f (x))\) with \(x\) drawn uniformly at random from \(\mathcal{X}\). Specifically, we show that a property \(P\) is testable with a constant number of samples if and only if it is (essentially) a \(k\)-part symmetric property for some constant \(k\), where a property is \(k\)-part symmetric if there is a partition \(X_1,\ldots, X_k\) of \(\mathcal{X}\) such that whether \(f:\mathcal{X} \to \{0,1\}\) satisfies the property is determined solely by the densities of \(f\) on \(X_1,\ldots,X_k\). We use this characterization to show that symmetric properties are essentially the only graph properties and affine-invariant properties that are testable with a constant number of samples and that for every constant \(d \geq 1\), monotonicity of functions on the d-dimensional hypergrid is testable with a constant number of samples.

Given an \(n\)-vertex undirected graph \(G = (V , E )\) and positive edge weights \(\{w_e\}_{e \in E}\) , a linear arrangement is apermutation \(\pi:V \to \{1,2,\ldots,n\}\). The value of the arrangement is \(\mathrm{val}(G,π):= \frac{1}{n} \sum_{e=\{u,v\} \in E} w_e|\pi(u)-\pi(v)|\). In the minimum linear arrangement problem, the goal is to find a linear arrangement \(\pi^*\) that achieves \(\mathrm{val}(G, \pi^*) = \mathrm{MLA}(G) := \min_{\pi} \mathrm{val}(G, \pi)\). In this paper, we show that for any \(\epsilon > 0\) and positive integer \(r\), there is an \(n^{O(r/\epsilon)}\)-time randomized algorithm that, given a graph \(G\), returns a linear arrangement \(\pi\) such that \(\mathrm{val}(G,\pi) \leq \Bigl(1+\frac{2}{(1-\epsilon)\lambda_r(L)}\Bigr) \mathrm{MLA}(G)+O(\sqrt{\frac{\log n}{n}}\sum_{e \in E w_e})\) with high probability, where \(L\) is the normalized Laplacian of \(G\) and \(\lambda_r(L)\) is the \(r\)th smallest eigenvalue of \(L\). Our algorithm gives a constant factor approximation for regular graphs that are weak expanders.

This paper studies property testing for NP optimization problems with parameter \(k\) under the general graph model with an augmentation of random edge sampling capability. It is shown that a variety of such problems, including \(k\)-Vertex Cover, \(k\)-Feedback Vertex Set, \(k\)-Multicut, \(k\)-Path-Free and \(k\)-Dominating Set, are constant-query testable if \(k\) is constant. It should be noted that the first four problems are fixed parameter tractable (FPT) and it turns out that algorithmic techniques for their FPT algorithms (branch-and-bound search, color coding, etc.) are also useful for our testers. \(k\)-Dominating Set is \(W[2]\)-hard, but we can still test the property with a constant number of queries since the definition of \(\epsilon\)-farness makes the problem trivial for non-sparse graphs that are the source of hardness for the original optimization problem. We also consider \koct, which is another well-known FPT problem, but we only give a sublinear-query tester when \(k\) is a constant.

Measuring the similarity between two sentences is often difficult due to their small lexical overlap. Instead of focusing on the sets of features in two given sentences between which we must measure similarity, we propose a sentence similarity method that considers two types of constraints that must be satisfied by all pairs of sentences in a given corpus. Namely, (a) if two sentences share many features in common, then it is likely that the remaining features in each sentence are also related, and (b) if two sentences contain many related features, then those two sentences are themselves similar. The two constraints are utilized in an iterative bootstrapping procedure that simultaneously updates both word and sentence similarity scores. Experimental results on SemEval 2015 Task 2 dataset show that the proposed iterative approach for measuring sentence semantic similarity is significantly better than the non-iterative counterparts.

In the List \(H\)-Homomorphism Problem, for a graph \(H\) that is a parameter of the problem, an instance consists of an undirected graph \(G\) with a list constraint \(L(v) \subseteq V(H)\) for each variable \(v \in V(G)\), and the objective is to determine whether there is a list \(H\)-homomorphism \(f:V(G) \to V(H)\), that is, \(f(v) \in L(v)\) for every \(v \in V(G)\) and \((f(u),f(v)) \in E(H)\) whenever \((u,v) \in E(G)\). We consider the problem of testing list \(H\)-homomorphisms in the following weighted setting: An instance consists of an undirected graph \(G\), list constraints \(L\), weights imposed on the vertices of \(G\), and a map \(f:V(G) \to V(H)\) given as an oracle access. The objective is to determine whether \(f\) is a list \(H\)-homomorphism or far from any list \(H\)-homomorphism. The farness is measured by the total weight of vertices \(v \in V(G)\) for which \(f(v)\) must be changed so as to make \(f\) a list \(H\)-homomorphism. In this paper, we classify graphs H with respect to the number of queries to \(f\) required to test the list \(H\)-homomorphisms. Specifically, we show that (i) list \(H\)-homomorphisms are testable with a constant number of queries if and only if \(H\) is a reflexive complete graph or an irreflexive complete bipartite graph and (ii) list \(H\)-homomorphisms are testable with a sublinear number of queries if and only if \(H\) is a bi-arc graph.

When we represent real-world systems as networks, the directions of links often convey valuable information. Finding module structures that respect link directions is one of the most important tasks for analysing directed networks. Although many notions of a directed module have been proposed, no consensus has been reached. This lack of consensus results partly because there might exist distinct types of modules in a single directed network, whereas most previous studies focused on an independent criterion for modules. To address this issue, we propose a generic notion of the so-called truss structures in directed networks. Our definition of truss is able to extract two distinct types of trusses, named the cycle truss and the flow truss, from a unified framework. By applying the method for finding trusses to empirical networks obtained from a wide range of research fields, we find that most real networks contain both cycle and flow trusses. In addition, the abundance of (and the overlap between) the two types of trusses may be useful to characterize module structures in a wide variety of empirical networks. Our findings shed light on the importance of simultaneously considering different types of modules in directed networks.

We study testing properties of functions on finite groups. First we consider functions of the form math formula, where \(G\) is a finite group. We show that conjugate invariance, homomorphism, and the property of being proportional to an irreducible character is testable with a constant number of queries to \(f\), where a character is a crucial notion in representation theory. Our proof relies on representation theory and harmonic analysis on finite groups. Next we consider functions of the form math formula, where \(d\) is a fixed constant and math formula is the family of \(d\) by \(d\) matrices with each element in math formula. For a function math formula, we show that the unitary isomorphism to \(g\) is testable with a constant number of queries to \(f\), where we say that \(f\) and \(g\) are unitary isomorphic if there exists a unitary matrix \(U\) such that math formula for any math formula.

A recent trend in parameterized algorithms is the application of polytope tools to fixed-parameter tractable (FPT) algorithms [e.g., Cygan et al., 2011; Narayanaswamy et al., 2012]. Although this approach has yielded significant speedups for a range of important problems, it requires the underlying polytope to have very restrictive properties, including half-integrality and Nemhauser--Trotter-style persistence properties. To date, these properties are essentially known to hold only for two classes of polytopes, covering the cases of Vertex Cover [Nemhauser and Trotter, 1975] and Node Multiway Cut [Garg et al., 2004]. Taking a slightly different approach, we view half-integrality as a discrete relaxation of a problem, e.g., a relaxation of the search space from \(\{0,1\}^V\) to \(\{0,1/2,1\}^V\) such that the new problem admits a polynomial-time exact solution. Using tools from constraint satisfaction problems [in particular Thapper and Živný, 2012] to study the existence of such relaxations, we are able to provide a much broader class of half-integral polytopes with the required properties. Our results unify and significantly extend the previously known cases, and yield a range of new and improved FPT algorithms, including an \(O^*(|\Sigma|^{2k})\)-time algorithm for node-deletion Unique Label Cover and an \(O^*(4^k)\)-time algorithm for Group Feedback Vertex Set where the group is given by oracle access. The latter result also implies the first single-exponential time FPT algorithm for Subset Feedback Vertex Set, answering an open question of Cygan et al., 2016]. Additionally, we propose a network-flow-based approach to solve several cases of the relaxation problem. This gives the first linear-time FPT algorithm to edge-deletion Unique Label Cover.

Structure of real networked systems, such as social relationship, can be modeled as temporal networks in which each edge appears only at the prescribed time. Understanding the structure of temporal networks requires quantifying the importance of a temporal vertex, which is a pair of vertex index and time. In this paper, we define two centrality measures of a temporal vertex based on the fastest temporal paths which use the temporal vertex. The definition is free from parameters and robust against the change in time scale on which we focus. In addition, we can efficiently compute these centrality values for all temporal vertices. Using the two centrality measures, we reveal that distributions of these centrality values of real-world temporal networks are heterogeneous. For various datasets, we also demonstrate that a majority of the highly central temporal vertices are located within a narrow time window around a particular time. In other words, there is a bottleneck time at which most information sent in the temporal network passes through a small number of temporal vertices, which suggests an important role of these temporal vertices in spreading phenomena.

We present an efficient algorithm for testing outerplanarity of graphs in the bounded-degree model. In this model, given a graph \(G\) with degree bound \(d\), we should distinguish with high probability the case that \(G\) is outerplanar from the case that modifying at least an \(\epsilon\)-fraction of the edge set is necessary to make \(G\) outerplanar. Our algorithm runs in time polynomial in \(d\) and \(1/\epsilon\) only. To achieve the time complexity, we exploit the tree-like structure inherent to an outerplanar graph using the microtree/macrotree decomposition of a tree. As a corollary, we show that the property of being a cactus is testable in time polynomial in \(d\) and \(1/\epsilon\).

Long Code testing is a fundamental problem in the area of property testing and hardness of approximation. In this paper, we study how small the soundness s of the Long Code test with perfect completeness can be by using non-adaptive \(q\) queries. We show that \(s = (2q + 3)/2^q\) is possible, where \(q\) is of the form \(2^k-1\) for any integer \(k > 2\).

Given a Boolean function \(f\), the \(f\)-isomorphism testing problem requires a randomized algorithm to distinguish functions that are identical to \(f\) up to relabeling of the input variables from functions that are far from being so. An important open question in property testing is to determine for which functions \(f\) we can test \(f\)-isomorphism with a constant number of queries. Despite much recent attention to this question, essentially only two classes of functions were known to be efficiently isomorphism testable: symmetric functions and juntas. We unify and extend these results by showing that all partially symmetric functions---functions invariant to the reordering of all but a constant number of their variables---are efficiently isomorphism testable. This class of functions, first introduced by Shannon, includes symmetric functions, juntas, and many other functions as well. We conjecture that these functions are essentially the only functions efficiently isomorphism-testable. To prove our main result, we also show that partial symmetry is efficiently testable. In turn, to prove this result we had to revisit the junta testing problem. We provide a new proof of correctness of the nearly optimal junta tester. Our new proof replaces the Fourier machinery of the original proof with a purely combinatorial argument that exploits the connection between sets of variables with low influence and intersecting families. Another important ingredient in our proofs is a new notion of symmetric influence. We use this measure of influence to prove that partial symmetry is efficiently testable and also to construct an efficient sample extractor for partially symmetric functions. We then combine the sample extractor with the testing-by-implicit-learning approach to complete the proof that partially symmetric functions are efficiently isomorphism testable.

For a function \(f:2^V \to \mathbb{Z}_+\) on a finite set \(V\) with \(f(\emptyset)=f(V)=0\), a digraph \(D=(V,A)\) is called \(f\)-connected if it satisfies the \(f\)-cut condition, that is, \(\delta_D(X) \geq f(X)\) for any \(X \subseteq V\), where \(\delta_D(X)\) is the number of arcs from \(X\) to \(V \setminus X\). We show that, for any crossing supermodular function \(f\), the \(f\)-connectivity can be tested with a constant number of queries in the general digraph model with average degree bound. As immediate corollaries, we obtain constant-time testers for \(k\)-edge-connectivity, rooted-\((k,l)\)-edge-connectivity, and the property of having \(k\) arc-disjoint arborescences. We also give a corresponding result for the undirected case.

Three men, each with a sister, must cross a river using a boat that can carry only two people in such a way that a sister is never left in the company of another man if her brother is not present. This very famous problem appeared in the Latin book “Problems to Sharpen the Young,” one of the earliest collections of recreational mathematics. This paper considers a generalization of such “river crossing problems” and provides a new formulation that can treat wide variations. The main result is that, if there is no upper bound on the number of transportations (river crossings), a large class of subproblems can be solved in polynomial time even when the passenger capacity of the boat is arbitrarily large. The authors speculated this fact at FUN 2012. On the other hand, this paper also demonstrates that, if an upper bound on the number of transportations is given, the problem is NP-hard even when the boat capacity is three, although a large class of subproblems can be solved in polynomial time if the boat capacity is two.

To control infection spreading on networks, we investigate the effect of observer nodes that recognize infection in a neighboring node and make the rest of the neighbor nodes immune. We numerically show that random placement of observer nodes works better on networks with clustering than on locally treelike networks, implying that our model is promising for realistic social networks. The efficiency of several heuristic schemes for observer placement is also examined for synthetic and empirical networks. In parallel with numerical simulations of epidemic dynamics, we also show that the effect of observer placement can be assessed by the size of the largest connected component of networks remaining after removing observer nodes and links between their neighboring nodes.

Huber, Krokhin, and Powell (2013) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain. In this paper we consider a natural generalization of the concept of skew bisubmodularity and show a connection between the generalized skew bisubmodularity and a convex extension over rectangles. We also analyze the dual polyhedra, called skew bisubmodular polyhedra, associated with generalized skew bisubmodular functions and derive a min-max theorem that characterizes the minimum value of a generalized skew bisubmodular function in terms of a minimum-norm point in the associated skew bisubmodular polyhedron.