Locally Defined Independence Systems on Graphs

The maximization for independence system is one of the most fundamental combinatrial optimization problems [1, 2, 3]. An independence system is a pair $(E,\mathcal{I})$ of a finite set $E$ and a family $\mathcal{I}\subseteq 2^{E}$ that satisfies

Here a member $I$ in $\mathcal{I}$ is called an independent set. The property (2) means that $\mathcal{I}$ is downward closed. The maximization problem for an independence system is to find an independent set with the maximum cardinality. This problem includes, as a special case, the maximum independent set of a graph, the maximum matching, the maximum set packing and the matroid (intersection) problems [4, 1, 3].

In this paper, we consider the following independence systems defined on graphs. Let $G=(V,E)$ be a graph with a vertex set $V$ and an edge set $E$. For a vertex $v$ in $V$, let $E_{v}$ denotes the set of edges incident to $v$. In our problem setting, each vertex $v$ has a local independence system $(E_{v},\mathcal{I}_{v})$, i.e., $\mathcal{I}_{v}\subseteq 2^{E_{v}}$, and we consider the independence system $(E,\mathcal{I})$ defined by

Namely, $(E,\mathcal{I})$ is obtained by concatenating local independence systems $(E_{v},\mathcal{I}_{v})$, and is called an independence system defined on a graph $G$. We assume without loss of generality that $\{e\}\in\mathcal{I}$ holds for any $e\in E$, since otherwise the underlying graph $G$ can be replaced by $G^{\prime}=(V,E\setminus\{e\})$. In this paper, we consider the maximization problem for it, i.e., for a given graph $G=(V,E)$ with local independence systems $(E_{v},\mathcal{I}_{v})$, our problem is described as

Note that any independence system $(E,\mathcal{I})$ is viewed as an independence system defined on a star. As an example of the problem (4), for $b:V\to\mathbb{Z}_{+}$, let $\mathcal{I}_{v}=\{I\subseteq E_{v}\mid|I|\leq b(v)\}$, i.e., $\mathcal{I}_{v}$ is $b(v)$-bounded for every $v$ in $V$. Then (3) denotes the family of $b$-matchings in $G$. In particular, if $b\equiv 1$, it corresponds to the family of matchings in $G$ [5]. More generally, if $(E_{v},\mathcal{I}_{v})$ is a matroid for every $v$ in $V$, then the family (3) is a so-called matchoid [6].

The maximum $b$-matching and matchoid problems are well-studied combinatorial optimization problems [5, 6]. It is known that the maximum matchoid problem is NP-hard [7] and it is $3/2$-approximable [8, 9].

The unweighted maximum satisfiability problem (MAX-SAT) is another example of the problem (4). The unweighted MAX-SAT is the problem to find a variable assignment that maximizes the number of the satisfied clauses in a given conjunctive normal form (CNF). For a variable set $X$, let $\varphi=\bigwedge_{c\in C}c$ be a CNF, where $C$ denotes a set of clauses with variables in $X$. Define a bipartite graph $G=(V=X\cup C,E)$ and local independence systems $(E_{v},\mathcal{I}_{v})$ by

where, for a variable $x\in X$, $C_{+}(x)$ and $C_{-}(x)$ respectively denote the sets of clauses in $C$ that contain literals $x$ and $\overline{x}$. Therefore the unweighted MAX-SAT is an example of the problem (4). As is well-known, the unweighted MAX-SAT is NP-hard and approximable in ratio $1.255$ [10].

(Edge-)temporal graphs [11] were introduced to model dynamic network topologies where the edge set vary with time. Namely, a temporal graph is a graph $G=(V,E)$ with given time labels $L_{e}\subseteq T$ for all $e$ in $E$, where $T$ is a given finite set of time labels. For a temporal graph, a subset $M$ of $E$ is a timed matching if $L_{e}$ and $L_{f}$ are disjoint for any adjacent pair of edges $e$ and $f$ in $M$. By defining local independence systems $(E_{v},\mathcal{I}_{v})$ by $\mathcal{I}_{v}=\{I\subseteq E_{v}\mid L_{e}\cap L_{f}=\emptyset\ \text{for all}\ e,f\in I\}$, the maximum timed matching can be formulated as the problem (4). It is known that the maximum timed matching problem is NP-hard even if the given graph $G$ is bipartite, and is solvable in polynomial time if $G$ is a tree and every $L_{e}$ is represented as an interval for a given order of time labels [12].

In this paper, we consider the problem (4) by making use of local oracles $\mathcal{A}_{v}$ for each $v$ in $V$. The oracle $\mathcal{A}_{v}$ computes an $\alpha$-approximate independent set $I$ of $(F,\mathcal{I}_{v}[F])$ for a given set $F\subseteq E_{v}$, where $\mathcal{I}_{v}[F]$ is the restriction of $\mathcal{I}_{v}$ to $F$, i.e., $\mathcal{I}_{v}[F]=\{I\cap F\mid I\in\mathcal{I}_{v}\}$. That is, the oracle $\mathcal{A}_{v}:2^{E_{v}}\to 2^{E_{v}}$ satisfies

We call $\mathcal{A}_{v}$ an $\alpha$-approximation local oracle. It is also called an exact local oracle if $\alpha=1$. In this paper, we assume the monotonicity of $\mathcal{A}_{v}$, i.e., $|\mathcal{A}_{v}(S)|\leq|\mathcal{A}_{v}(T)|$ holds for the subsets $S\subseteq T\subseteq E_{v}$, which is a natural assumption on the oracle since it deals with independence system. We study this oracle model to investigate the global approximability of the problem (4) by using the local approximability. The oracle model was used in [13] for the maximum coverage problem with group constraints, where the oracle model is regarded as a generalization of greedy algorithms. It is shown that the maximum coverage problem is $(\alpha+1)$-approximable in this oracle model. We remark here that a greedy algorithm for the maximum cardinality matching problem can be viewed as a $2$-approximation algorithm under the exact local oracle model.

For the above reductions of the maximum matchoid problem and the unweighted MAX-SAT, their local maximization problems for $(E_{v},\mathcal{I}_{v})$ can be solved exactly, while their global maximization problems are NP-hard. This means that the problem (4) seems to be intractable, even if exact local oracles are given.

In this paper, we first propose two natural algorithms for the problem (4), where the first one applies local oracles $\mathcal{A}_{v}$ in the order of the vertices $v$ that is fixed in advance, while the second one applies local oracles in the greedy order of vertices $v_{1},\dots,v_{n}$, where $n=|V|$ and

Here the subset $F^{(i)}\subseteq E$ is a set of available edges during the $i$-th iteration.

We show that the first algorithm guarantees an approximation ratio $(\alpha+n-2)$, and the second algorithm guarantees an approximation ratio $\rho(\alpha,n)$, where $\rho$ is the function of $\alpha$ and $n$ defined as

We also show that both of approximation ratios are almost tight for these algorithms.

We then consider two subclasses of the problem (4). We provide two approximation algorithms for the $k$-degenerate graphs, whose approximation ratios are $\alpha+2k-2$ and $\alpha k$. Here, a graph is $k$-degenerate if any subgraph has a vertex of degree at most $k$. This implies for example that the algorithms finds an $\alpha$-approximate independent set for the problem if a given graph is a tree. This is best possible, because the local maximization is not approximable with $c\ (<\alpha)$. We also show that the second algorithm can be generalized to the hypergraph setting.

We next provide an $(\alpha+k)$-approximation algorithm for the problem when a given graph is bipartite and local independence systems for one side are all $k$-systems with independence oracles. Here an independence system $(E,\mathcal{I})$ is called a $k$-system if for any subset $F\subseteq E$, any two maximal independent sets $I$ and $J$ in $\mathcal{I}[F]$ satisfy $k|I|\geq|J|$, and its independence oracle is to decide if a given subset $J\subseteq E$ belongs to $\mathcal{I}$ or not.

The rest of the paper is organized as follows. In Section 2, we describe two natural algorithms for the problem (4) and analyze their approximation ratios. Section 3 provides approximation algorithms for the problem in which a given graph $G$ has bounded degeneracy. Section 4 also provides an approximation algorithm for the problem in which a given graph $G$ is bipartite, and all the local independence systems of the one side of vertices are $k$-systems. Section 5 defines independence systems defined on hypergraphs and generalizes algorithms to the hypergraph case.

In this section, we first define local subpartitons of edges and analyze two natural algorithms for the problem (4). Local subpartitons of edges is used for constructing and analyzing approximation algorithms for the problem.

By definition, for a local subpartition $\mathcal{P}=\{P_{v}\mid v\in V\}$, the set $P_{v}$ may be empty for some $v$ in $V$. Let $\mathcal{P}=\{P_{v}\mid v\in V\}$ be a local subpartition of $E$, and for every $v\in V$, let $I_{v}\in\mathcal{I}_{v}[P_{v}]$ be a subset of $P_{v}$ which is independent in $\mathcal{I}_{v}$. Then the union $I=\bigcup_{v\in V}I_{v}$ may not be an independent set of $\mathcal{I}$. If it is independent, we have the following lemma, where we recall that $\mathcal{A}_{v}\ (v\in V)$ denotes an $\alpha$-approximate local oracle.

All the algorithms proposed in this paper construct local subpartitons of edges, and Lemma 2 is used to analyze their approximation ratio.

Let us then see the following two simple algorithms which cannot guarantee any constant approximation ratio, even if exact local oracles are available. The first one called FixedOrder makes use of local oracles $\mathcal{A}_{v}$ in the order of the vertices $v\in V$ that is fixed in advance.

Algorithm FixedOrder constructs a local subpartition $\mathcal{P}=\{P_{v}\mid v\in V\}$ and the residual edge set $R$ of $\mathcal{P}$, which will be proven in the next theorem. In order to ensure that $I=\bigcup_{v\in V}\mathcal{A}_{v}(P_{v})$ is independent in Lemma 2, the algorithm maintains $F$ as a candidate edge set during the iteration. The following theorem provides the approximation ratio of the algorithm, which is almost tight for the algorithm. In fact, it is tight if $\alpha$ is an integer.

The second algorithm called Greedy makes use of local oracles $\mathcal{A}_{v}$ in a greedy order of vertices $v_{1},\dots,v_{n}$, where

Here the subset $F^{(i)}\subseteq E$ is the candidate edge set in the $i$-th round of Greedy.

For the analysis of Greedy, we use the following lemma which is slightly different from Lemma 2.

The following theorem provides the approximation ratio of Greedy, which is almost tight for the algorithm. In fact, it is tight if $(\alpha-1)(n-1)<\alpha$.

In this section, we present approximation algorithms for the problem (4). Our first algorithm called OrderedApprox makes use of a linear order $\prec$ of vertices $V$. Different from FixedOreder and Greedy in Section 2, the algorithm tries to minimize the size of $R$. In fact, we have $R=\emptyset$ if $G$ is a tree. More precisely, for each $v\in V$, we initialize $P_{v}=D_{v}$, where $D_{v}$ is the set of downward edges of $v$, i.e., $D_{v}=\{(u,v)\in E_{v}\mid u\prec v\}$, and compute $\mathcal{A}_{v}(P_{v})$ and $\mathcal{A}_{v}(P_{v}\cup\{e\})$ for each $e\in U_{v}$, where $U_{v}$ is the set of upward edges of $v$, i.e., $U_{v}=\{(u,v)\in E_{v}\mid v\prec u\}$. Based on these outputs of local oracle and their values, we consider four cases, each of which we update $P_{v}$ and construct $I_{v}=\mathcal{A}_{v}(P_{v})$ and $R_{v}$ accordingly. Here $P_{v}$ and $R=\bigcup_{v\in V}R_{v}$ correspond to those in Lemma 2. We then modify $P_{w}$ for vertices $w$ with $v\prec w$, in such a way that the set $I=\mathcal{A}_{w}(P_{w})\cup\bigcup_{u\in V:u\preceq v}I_{v}$ is an independent set in $\mathcal{I}$. The second algorithm first decomposes edge set $E$ into forests $E_{1},\ldots,E_{\gamma}$, for each forest $E_{i}$, applies OrderedApprox to compute an independent set $I_{i}$, and chooses a maximum independent set among them.

We first define the upward and downward edge sets with respect to a linear order.