The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We study complexity of the problem on hereditary subclasses of ...subcubic graphs. Each such subclass can be described by means of forbidden induced subgraphs. In case of finitely many forbidden induced subgraphs a necessary condition for polynomial-time solvability of the problem in subcubic graphs (unless P=NP) is the exclusion of the graph Si,j,k, which is a tree with three leaves of distance i,j,k from the only vertex of degree 3. Whether this condition is also sufficient is an open question, which was previously answered only for S1,k,k-free subcubic graphs and S2,2,2-free subcubic graphs. Combining various algorithmic techniques, in the present paper we generalize both results and show that the problem can be solved in polynomial time for S2,k,k-free subcubic graphs, for any fixed value of k.
This paper considers the global optimization of max-plus linear systems with affine equality constraints. For both the cases that the variables are real and non-negative, the necessary and sufficient ...conditions for the existence and uniqueness of globally optimal solutions are given, respectively. The proposed approaches are constructive and yield two polynomial algorithms for checking the solvabilities of the global optimization problems and finding all globally optimal solutions, in which the analytic expressions of general solutions are presented. The global optimization is then applied in the load scheduling of distributed systems with different processor capacities. The optimal allocation scheme is designed to minimize the completion time of the overall task. Some illustrative examples are presented to demonstrate the results.
As usual λ(G) denotes the edge-connectivity of the graph G. It was shown in 2 that every graph G contains a spanning (λ(G)+1)-partite subgraph H such that λ(H)=λ(G) and one can find such a spanning ...subgraph in polynomial time. We determine the complexity of deciding, for given positive integers r,k whether a graph contains a spanning r-colourable subgraph which is k-edge-connected. We show that the problem is polynomially solvable when r>k and NP-complete otherwise. In fact, combined with the result from 2 above, this means that the problem is polynomially solvable precisely when r is such that every k-edge-connected graph has a spanning r-colourable subgraph which is k-edge-connected.
One can show that all graphs whose edge set decomposes into k edge-disjoint spanning trees are 2k-colourable. We consider the problem of deciding whether a given graph G has a collection of k edge-disjoint spanning trees whose union forms an r-colourable spanning subgraph H of G. We show that this problem is polynomially solvable when r≥2k and NP-complete for all other values of r. We also determine the complexity of the analogous problem of deciding whether a digraph D has a collection of k arc-disjoint out-branchings such that the spanning subdigraph formed by the union of the arcs in the branchings is r-colourable.
A digraph is eulerian if it is connected and every vertex has its in‐degree equal to its out‐degree. Having a spanning eulerian subdigraph is thus a weakening of having a hamiltonian cycle. In this ...paper, we first characterize the pairs (D,a) $(D,a)$ of a semicomplete digraph D $D$ and an arc a $a$ such that D $D$ has a spanning eulerian subdigraph containing a $a$. In particular, we show that if D $D$ is 2‐arc‐strong, then every arc is contained in a spanning eulerian subdigraph. We then characterize the pairs (
D
,
a
) $(D,a)$ of a semicomplete digraph D $D$ and an arc a $a$ such that D $D$ has a spanning eulerian subdigraph avoiding a $a$. In particular, we prove that every 2‐arc‐strong semicomplete digraph has a spanning eulerian subdigraph avoiding any prescribed arc. We also prove the existence of a (minimum) function f
(
k
) $f(k)$ such that every f
(
k
) $f(k)$‐arc‐strong semicomplete digraph contains a spanning eulerian subdigraph avoiding any prescribed set of k $k$ arcs. We conjecture that f
(
k
)
=
k
+
1 $f(k)=k+1$ and establish this conjecture for k
≤
3 $k\le 3$ and when the k $k$ arcs that we delete form a forest of stars. A digraph D $D$ is eulerian‐connected if for any two distinct vertices x
,
y $x,y$, the digraph D $D$ has a spanning (
x
,
y
) $(x,y)$‐trail. We prove that every 2‐arc‐strong semicomplete digraph is eulerian‐connected. All our results may be seen as arc analogues of well‐known results on hamiltonian paths and cycles in semicomplete digraphs.
Fault-tolerant networks are often modeled as s-hamiltonian graphs. Thus it is of interests to find graph families in which whether a graph is s-hamiltonian can be determined in polynomial time. An ...hourglass is a graph obtained from K5 by deleting the edges in a cycle of length 4, and an hourglass-free graph is one that has no induced subgraph isomorphic to an hourglass. Kriesell in J. Combin. Theory Ser. B, 82 (2001), 306-315 proved that every 4-connected hourglass-free line graph is Hamilton-connected, and Kaiser, Ryjáček and Vrána in Discrete Mathematics, 321 (2014) 1-11 extended it by showing that every 4-connected hourglass-free line graph is 1-Hamilton-connected. We characterize all essentially 4-edge-connected graphs whose line graph is hourglass-free. Consequently we prove that for any integer s and for any hourglass-free line graph L(G), each of the following holds.
(i) If s≥2, then L(G) is s-hamiltonian if and only if κ(L(G))≥s+2;
(ii) If s≥1, then L(G) is s-Hamilton-connected if and only if κ(L(G))≥s+3.
We study the complexity of deciding whether a given digraph D=(V,A) admits a partition (A1,A2) of its arc set such that each of the corresponding digraphs D1=(V,A1) and D2=(V,A2) satisfy some given ...prescribed property. We mainly focus on the following 15 properties: being bipartite, being connected, being strongly connected, being acyclic (spanning or not necessarily spanning), containing an in-branching, containing an out-branching, having some in-degree (or out-degree) conditions, satisfying some conditions on the number of arcs, being balanced (connected or not) or being a cycle. Combined with previous research, our work leads to a complete classification (in terms of being polynomial or NP-complete) of the complexity of 120 arc-partitioning problems on digraphs.
•The single-machine multiple-project scheduling problems.•The processing times of jobs are controllable.•The processing cost of a project includes total compression cost and total tardiness cost of ...its jobs.•Two types of problems are considered: Sum problem and Restricted problem.
This paper studies the single-machine multiple-project scheduling problem with controllable processing times, in which the cost of a project refers to the total compression cost of its jobs plus the weighted number of tardy jobs in a schedule satisfying some given precedence constraints. It involves four specific problems: (i) minimizing the total cost of an arbitrary number of projects, (ii) being the same as (i) except the jobs from the same project having a common due date, (iii) having a fixed number of projects and minimizing the cost of one project subject to the cost of each of other projects not exceeding a given threshold, and (iv) being the same as (iii) except all jobs having identical weights. We show that a special version of (i) in which each project has only two jobs and all jobs have unit weights and cannot be compressed is strongly NP-hard (it implies the strong NP-hardness of (i)), (ii) is weakly NP-hard and admits a pseudo-polynomial algorithm and a fully polynomial time approximation scheme, (iii) is pseudo-polynomially solvable by a two-phase transformation, and (iv) is weakly NP-hard even if there are only two projects and all jobs have identical maximum compression amounts and identical processing times.
A hypergraph H on n vertices and m edges is said to be nearly-intersecting if every edge of H intersects all but at most polylogarthmically many (in m and n) other edges. Given lists of colors L(v), ...for each vertex v∈V, H is said to be L-(list) colorable, if each vertex can be assigned a color from its list such that no edge in H is monochromatic. We show that list-colorability for any nearly intersecting hypergraph, and lists drawn from a set of constant size, can be checked in quasi-polynomial time in m and n.
It is required to find an optimal order of constructing the edges of a network so as to minimize the sum of the weighted connection times of relevant pairs of vertices. Construction can be performed ...anytime anywhere in the network, with a fixed overall construction speed. The problem is strongly NP-hard even on stars. We present polynomial algorithms for the problem on trees with a fixed number of leaves, and on general networks with a fixed number of relevant pairs.
PDF
