24
$\begingroup$

(This question is a bit of a "survey".)

I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural properties. The problem "feels" quite hard, and I fully expect it to be $\mathcal{NP}$-complete. For some reason I'm having a hard time even finding similar problems in literature.

An example of a problem that I would consider comparable to the one I'm dealing with:

Given a weighted tournament $G = (V,E,w)$, is there a feedback arc set in $G$ the edges of which fulfill the triangle inequality?

Note the difference to the traditional feedback arc set (DFAS) problem: I don't care about the size of the set, but I do care whether the set itself has a certain structural property.

Have you encountered any decision problems that feel similar to this? Do you remember whether they were $\mathcal{NP}$-complete or in $\mathcal{P}$? Any and all help appreciated.

Improve this question
$\endgroup$
5
  • $\begingroup$ Perhaps you can explain the structural properties of your problem, there are many experts here that are familiar with NPC proofs and instead of a reference you could get an NPC proof :-) $\endgroup$
    – Marzio De Biasi
    Commented Nov 19, 2013 at 8:50
  • $\begingroup$ @MarzioDeBiasi I would very much like to avoid being given a proof to the problem I'm dealing with; it's the first time I'm doing actual research and I'd like to see where I can get on my own :) $\endgroup$
    – G. Bach
    Commented Nov 19, 2013 at 11:31
  • 1
    $\begingroup$ To me, the question sounds too vague, and it's hard to guess what is really asked. Probably, the question should be made more specific: what you mean by "feel similar to this" and what you mean by "a feedback arc set in G the edges of which fulfill the triangle inequality"; do you want a reference on the feedback arc set problem, or on another problem? $\endgroup$
    – Yoshio Okamoto
    Commented Nov 19, 2013 at 12:51
  • 1
    $\begingroup$ @YoshioOkamoto I realize that there is some ambiguity in the question, and I hoped the example would clear some of it up. By "feedback arc set in G the edges of which fulfill the triangle inequality" I mean: if $F$ is a feedback arc set and $(a,b)$, $(b,c)$, $(a,c)$ $\in F$, then $w(a,b) + w(b,c) \ge w(a,c)$ has to hold for $F$ to fulfill that property. Previously I only ever encountered problems of the kind $|F| \le k$, but I want $F$ to have a property not related to its cardinality. $\endgroup$
    – G. Bach
    Commented Nov 19, 2013 at 12:56
  • $\begingroup$ can someone give a link/ref to "the traditional feedback arc set problem"...? $\endgroup$
    – vzn
    Commented Feb 1, 2014 at 18:05

3 Answers 3

Reset to default
21
+100
$\begingroup$

I think there are lot of similar problems. Here are two in vertex version and one in edge version:

1) Does a given graph have an independent feedback vertex set? (we don't care about the size of the set). This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in Garey, Johnson & Stockmeyer.

2) Does a given graph have a vertex cover that induces a tree? (we don't care about the size of the set). This paper gives an NP-completeness proof for this problem (Theorem 2); even for bipartite graphs.

3) Does a given graph have a dominating edge set the edges of which form an induced $1$-regular subgraph? (also known as dominating induced matching or efficient edge dominating; the vertex version is given in the second answer by Mohammad. Again, we don't care about the size of the set). This problem is NP-complete (well-known, first proved here), even for planar bipartite graphs.

The first two problems are particular examples of the problem class called stable-$\pi$: Let $\pi$ be a graph property. Does a given graph have a vertex cover satisfying $\pi$? More NP-complete cases as well as polynomially solvable cases can be found in this and in this paper (and the refs given there) .

Improve this answer
$\endgroup$
4
  • 5
    $\begingroup$ Those are exactly the kind of problems I'm looking for! $\endgroup$
    – G. Bach
    Commented Nov 19, 2013 at 15:37
  • 3
    $\begingroup$ @G.Bach Since this exactly answers your question, I suggest you accept the answer and award the bounty. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Nov 19, 2013 at 19:06
  • $\begingroup$ @MohammadAl-Turkistany I agree; for some reason, I will only be able to award the bounty in an hour. $\endgroup$
    – G. Bach
    Commented Nov 19, 2013 at 19:24
  • 4
    $\begingroup$ Thanks for your nice post. I was thinking for a while a long the same lines. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Nov 19, 2013 at 19:27
4
$\begingroup$

An $NP$-complete structural problem is to decide the existence of odd (even) hole in directed graphs. Anna Lubiw proved the $NP$-completeness of the above two problems.

A hole is chordless cycle of length greater than three. A cycle in directed graph is chordless if its length is greater than 3 and no two of its vertices are joined by an edge of the directed graph which does not belong to the cycle.

As for undirected graph, testing for the existence of odd hole passing through a given vertex is $NP$-complete. Specifically, the problem is to decide whether a graph contains an induced odd cycle of length greater than three, passing through a prescribed vertex. (Odd hole in a graph is an induced cycle of length at least five). However, the complexity of deciding the existence of odd hole is a long standing open problem (if we drop the requirement of passing through a given vertex). In contrast, the task of finding an even hole in a graph is in $P$.

The structural property of the cycle is the property of being chordless. In directed graph, this is enough for NP hardness (in addition to parity requirement) while in undirected graphs odd parity of the chordless cycle is required for $NP$-completeness.

The importance of detecting odd-hole structure in graphs is highlighted by the recent breakthrough of the Strong Perfect Graph Theorem. It shows that a graph is perfect if and only if neither it nor its complementary graph has an odd hole.

Improve this answer
$\endgroup$
2
  • $\begingroup$ A cycle is induced cycle if and only if it is chordless cycle (also called hole). $\endgroup$
    – Mohammad Al-Turkistany
    Commented Nov 19, 2013 at 4:28
  • 1
    $\begingroup$ Both of your answers sound like the kind of problem I'm looking for, thank you! $\endgroup$
    – G. Bach
    Commented Nov 19, 2013 at 15:38
4
$\begingroup$

Another example is the efficient dominating set problem also known as 1-perfect code in graphs. The problem is to determine the existence of a dominating set $C$ in undirected graph such that the shortest path between any two nodes in the dominating set $C$ is at least 3 (edges). The problem was proven to be $NP$-complete independently by many researchers. The problem remains $NP$-complete even for cubic planar graphs.

D. W. Bange, A. E. Barkauskas, and P. J. Slater. Efficient dominating sets in graphs. Applications of discrete mathematics, Proc. 3rd SIAM Conf., Clemson/South Carolina 1986, 189-199 (1988)., 1988.

Improve this answer
$\endgroup$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.